栈和队列

作者 by admin / 2022-04-28 / 暂无评论 / 79 个足迹

栈(Stack)

栈(stack)又名堆栈,它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表

特点

后进先出(LIFO即Last in First out),把栈比喻薯片桶,一开始薯片桶的空的,第一片放进去的薯片会在最底部,第二片薯片会在顶部,想要吃掉第一片薯片,就得先把第二片薯片从薯片桶里拿出来or吃掉,然后再拿第一片薯片,也就是最先进去的薯片要到最后才被吃掉。

常用方法

新建一个类

function Stack() {
    this.items = []
}

插入元素(压栈)

// 往栈插入一个元素(压栈)
Stack.prototype.push = function (element) {
    this.items.push(element)
}

删除元素(出栈)

// 删除并返回栈顶元素(出栈)
Stack.prototype.pop = function (element) {
    return this.items.pop()
}

返回栈顶元素

// 返回栈顶元素
Stack.prototype.peek = function (element) {
    return this.items[this.items.length - 1]
}

清空栈

// 清空栈
Stack.prototype.clear = function (element) {
    this.items = []
}

打印栈

// 打印栈
Stack.prototype.print = function (element) {
    console.log(this.items.toString());
}

栈大小

// 判断栈大小 
Stack.prototype.size = function (element) {
return this.items.length
}

栈是否为空

// 判断栈是否为空
Stack.prototype.isEmpty = function (element) {
    return this.items.length == 0
}

案例

十进制转二进制

采用余数法,和2取余,把得到的结果进行逆序就 是转换结果。比如十进制的10转换为二进制,
第一次:10除以2得5余0
第二次:5除以2得2余1
第三次:2除以2得1余0
第四次:1除以2得0余1

栈实现

进制转换的实现可以比喻成栈,最后计算的结果最先输出,最先计算的结果最后输出(栈也是后进先出)

// 进制转换(栈实现)
function transform(num) {
    var stack = new Stack()
    var str = ""
    while (num > 0) {
        var yushu = num % 2 //余数
        stack.push(yushu)    //入栈
        num = Math.floor(num / 2) //每次取余的结果
    }
   while (!stack.isEmpty()) {
        str += stack.pop() + ""    //出栈
    }
    return str
}
console.log(transform(10))    //1010

队列(Queue)

队列是一种先进先出(First in First Out)的线性表,简称FIFO。允许插入的一端称为队尾,允许删除的一端称为队头。

特点

先进先出(First in First Out),可以把队列比喻成公交车站前面的排队,排队的人们可以看做队列,先排队的人先上车

常用方法

    function Queue() {
        this.item = []
    }
    
    // 入列
    Queue.prototype.enqueue = function (ele) {
        this.item.push(ele)
    }
    
    // 出列
    Queue.prototype.dequeue = function () {
        return this.item.shift()
    }
    
    // 查看队列头
    Queue.prototype.front = function () {
        return this.item[0]
    }
    
    // 检查队列是否为空
    Queue.prototype.isEmpty = function () {
        return this.item.length == 0
    }

// 检查队列大小
Queue.prototype.size = function () {
    return this.item.length
}

案例

击鼓传花
// 击鼓传花,给定一个数比如3,一个花,一群人坐在一圈里,一个人拿花喊1,
// 然后把花传给第二个人喊2,第二个人再把花传给第三个人,第三个人喊3并淘汰,
// 继续把花传给下一个人,继续数,继续淘汰,最后一个人是赢家
// 要求,给定一个数和一群人,返回赢家
function game(num, list) {
    var queue = new Queue()
    for (var i = 0; i < list.length; i++) {
        queue.enqueue(list[i])
    }
    var y = 1
    while (queue.size() > 1) { //如果当前队列人数大于1
        // 手里有花的且喊的不是num的人往队列最后移
        for (var j = 0; j < num - 1; j++) {
            queue.enqueue(queue.dequeue())
        }
        var taotai = queue.dequeue() //花到手且喊num的人里就淘汰
        console.log('第' + y + '轮淘汰了:', taotai)
        y++
    }
    return queue.dequeue()
}
//赢家是: a
console.log('赢家是:', game(3, ['a', 'b', 'c', 'd', 'e', 'f']))

优先级队列

普通的队列是一种先进先出(First in First Out)的数据结构,元素在队列尾追加,而从队列头删除。在优先队列中,元素被赋予优先级。当访问元素时,具有最高优先级的元素最先删除。优先队列具有最高级先出 (first in, largest out)的行为特征

实现

// 优先级队列
function FirstQueue() {
    this.item = []
}
FirstQueue.prototype.enqueue = function (ele, level) {
    function QueueItem(ele, level) {
        this.ele = ele
        this.level = level
    }
    var quequItem = new QueueItem(ele, level)
    var isMin = true
    for (var i = 0; i < this.item.length; i++) {
        if (this.item[i].level < quequItem.level) {
            this.item.splice(i, 0, quequItem)
            isMin = false
            break
        }
    }
    if (isMin) {
        this.item.push(quequItem)
    }
}
var firstQueue = new FirstQueue()
console.log(firstQueue)
console.log(firstQueue.enqueue('存10', 1))
console.log(firstQueue.enqueue('存300', 3))
console.log(firstQueue.enqueue('存100000', 10))
console.log(firstQueue.enqueue('存200', 2))
console.log(firstQueue)

独特见解