队列

队列数据结构

队列是遵循先进先出的一组有序的项。

创建队列

function Queue() {}

首先用数组存储队列中元素的数据结构：

let items = []

向队列添加元素

this.enqueue = function(element) {
     items.push(element);
};

从队列移除元素

this.dequeue = function() {
     return items.shift();
};

查看队列头元素

this.front = function() {
        return items[0]
    }

检查队列是否为空

this.isEmpty = function() {
    return items.length == 0;
};
this.size = function() {
    return items.length
};

打印队列元素

this.print = function() {
    console.log(items.toString());
};

用ES6实现的Queue类

用一个WeakMap保存私有属性items，并用闭包封装Queue类。

let Queue2 = (function() {
    const items = new WeakMap();
    class Queue2 {
        constructor() {
            items.set(this,[]);
        }
        enqueue(element) {
            let q = items.get(this);
            q.push(element);
        }
    }
    return Queue2
})();

优先队列

实现一个优先队列有两种选项：设置优先级，然后在正确的位置添加元素；或者用入列操作添加元素，然后按照优先级移除它们。在这个示例中，我们将会在正确的位置添加元素，因此可以对他们使用默认的出列操作：

function PriorityQueue() {
    let items = [];
    function QueueElement(element, priority) {
        this.element = element;
        this.priority = priority;
    }
    this.enqueue = function(element, priority) {
        let queueElement = new QueueElement(element, priority);
        let added = false;
        for(let i = 0; i<items.length; i++){
            if(queueElement.priority < items[i].priority) {
                items.splice(i,0,queueElement);
                added = true;
                break;
            }
        }
        if (!added){
            items.push(queueElement);
        }
    };
    this.print = function() {
        for(let i = 0; i<items.length; i++) {
            console.log(`${items[i].element} - 
            ${items[i].priority}`);
        }
    };
    //其他方法和默认的Queue实现相同
}

和默认类实现上的区别是，要向PriorityQueue添加元素，需要创建一个特殊的元素，这个元素包含了要添加到队列的元素及其在队列中的优先级。

如果队列为空，可以直接将元素入列。否则就需要比较该元素与其他元素的优先级。当找到一个比要添加的元素的priority值更大（优先级更低）的项时，就把新元素插入到他之前。如果要添加的元素的priority值大于任何已有的元素，把它添加到队列的末尾就行了。

循环队列—击鼓传花

孩子么围成一圈，把花尽快地传递给旁边的人，某一时刻传花停止，这个时候花在谁手里，谁就退出圆圈结束游戏。重复这个过程直到只剩一个人。

function hotPotato(nameList, num)  {
    let queue = new Queue();
    for(let i = 0;i<nameList.length;i++){
        queue.enqueue(nameList[i]);
    }
    let eliminated = '';
    while(queue.size() > 1) {
        for(let i = 0; i<num; i++) {
            queue.enqueue(queue.dequeue());
        }
        eliminated = queue.dequeue();
        console.log(eliminated + '被淘汰');
    }
    return queue.dequeue();
}
let names = ['A','C','D','E','S'], winner = hotPotato(names,7);
console.log('winner is ' + winner);
D被淘汰
C被淘汰
S被淘汰
E被淘汰
winner is A

先把名字加入队列，给定一个数字然后迭代队列。从队列开头移除一项再将其添加到末尾。一旦传递数字达到给定的数字，拿着花的那人就被淘汰。