栈和队列

栈(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)