JavaScript数据结构之-队列

队列遵循 FIFO，先进先出 原则的一组有序集合。队列在尾部添加元素，在顶部删除元素。在现实中最常见的队列就是 排队 。先排队的先服务。（ 请大家文明排队，不要插队。 ）

创建队列

实现包含以下方法的Queue类

• enqueue(element(s)):向队列尾部添加一个（或多个）元素。
• dequeue():移除队列的第一项，并返回移除的元素。
• front():返回队列的第一个元素--最先被添加，最先被移除的元素。
• isEmpty():判断队列是否为空。
• size():返回队列的长度。

1、简单实现Queue类

// 队列Queue类简单实现
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;
    };
}
复制代码

2、ES6语法实现Queue队列类，利用WeakMap来保存私有属性items,并用外层函数（闭包）来封装Queue类。

let Queue1 = (function() {
    const items = new WeakMap();
    class Queue1 {
        constructor() {
            items.set(this, []);
        }
        // 获取队列
        getQueue() {
            return items.get(this);
        }
        // 添加元素
        enqueue (element) {
            this.getQueue().push(element);
        }
        // 删除元素
        dequeue() {
            return this.getQueue().shift();
        }
        // 返回队列第一个元素
        front() {
            return this.getQueue()[0];
        }
        // 判断队列是否为空
        isEmpty() {
            return this.getQueue().length === 0;
        }
        // 返回队列长度
        size() {
            return this.getQueue().length;
        }
    }
    return Queue1;
})();
复制代码

优先队列

元素的添加和删除基于优先级。常见的就是机场的登机顺序。头等舱和商务舱的优先级高于经济舱。实现优先队列，设置优先级。

// 优先列队
function PriorityQueue() {
    let items = [];
    // 创建元素和它的优先级（priority越大优先级越低）
    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.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() {
        for (let i = 0; i < items.length; i++) {
            console.log(`${items[i].element} - ${items[i].priority}`);
        }
    };
}
复制代码

循环队列（击鼓传花）

// 循环队列（击鼓传花）
function hotPotato(nameList, num) {
    let queue = new Queue(); // {1}
    for(let i =0; i< nameList.length; i++) {
        queue.enqueue(nameList[i]); // {2}
    }
    let eliminted = '';
    while(queue.size() > 1) {
        // 把队列num之前的项按照优先级添加到队列的后面
        for(let i = 0; i < num; i++) {
            queue.enqueue(queue.dequeue()); // {3}
        }
        eliminted = queue.dequeue(); // {4}
        console.log(eliminted + '在击鼓传花游戏中被淘汰');
    }
    return queue.dequeue(); // {5}
}
let names = ['John', 'Jack', 'Camila', 'Ingrid', 'Carl'];
let winner = hotPotato(names, 7);
console.log('获胜者是：' + winner);
复制代码

实现一个模拟击鼓传花的游戏，{1}利用队列类，创建一个队列。{2}把当前玩击鼓传花游戏的所有人都放进队列。{3}给定一个数字，迭代队列，从队列的开头移除一项，添加到队列的尾部（如游戏就是：你把花传给旁边的人，你就可以安全了）。{4}一旦迭代次数到达，那么这时拿着花的这个人就会被淘汰。{5}最后剩下一个人，这个人就是胜利者。