一、定义
前面我们学习了，队列和栈非常类似，但是使用了不同的原则，而非后进先出。
队列是遵循FIFO（First In First Out，先进先出）原则的一组有序的项。队列在尾部添加新元素，并从顶部移除元素。最新添加的元素必须排在队列的末尾。
在计算机科学中，一个最常见的例子就是打印队列。比如说我们要打印五份文档。我们会打开每个文档，然后点击打印按钮。每个文档都会被发送至打印队列。第一个发送到打印队列的文档会首先被打印，以此类推，直到打印完所有文档。
二、队列的实现
2.1 普通队列
创建普通队列类：
// Queue类function Queue () { this.items = []; this.enqueue = enqueue; this.dequeue = dequeue; this.front = front; this.isEmpty = isEmpty; this.size = size; this.clear = clear; this.print = print;}复制代码 队列里面有一些声明的辅助方法：
- enqueue(element)：向队列尾部添加新项
- dequeue()：移除队列的第一项（即排在队列最前面的项），并返回被移除的元素
- front()：返回队列中第一个元素，队列不做任何变动，和Stack的peek()方法类似
- isEmpty()：如果队列中不包含任何元素，返回true，否则返回false
- size()：返回队列包含的元素个数，与数组的length属性类似
- print()：打印队列中的元素
- clear()：清空整个队列
下面我们来一一实现这些辅助方法：
// 向队列尾部添加元素function enqueue (element) { this.items.push(element);}// 移除队列的第一个元素，并返回被移除的元素function dequeue () { return this.items.shift();}// 返回队列的第一个元素function front () { return this.items[0];}// 判断是否为空队列function isEmpty () { return this.items.length === 0;}// 获取队列的长度function size () { return this.items.length;}// 清空队列function clear () { this.items = [];}// 打印队列里的元素function print () { console.log(this.items.toString());}复制代码 创建普通队列实例进行测试：
// 创建Queue实例var queue = new Queue();console.log(queue.isEmpty()); // truequeue.enqueue("John"); // undefinedqueue.enqueue("Jack"); // undefinedqueue.enqueue("Camila"); // undefinedqueue.print(); // "John,Jack,Camila"console.log(queue.size()); // 3console.log(queue.isEmpty()); // falsequeue.dequeue(); // "John"queue.dequeue(); // "Jack"queue.print(); // "Camila"queue.clear(); // undefinedconsole.log(queue.size()); // 0复制代码 2.2 优先队列
2.2.1 定义
普通队列的添加和移除只依赖于先后顺序，先来的先添加，后来的后添加，然后按照先后顺序依次从队列移除。
但是，还有一种队列叫优先队列，元素的添加和移除是依赖优先级的。
一个现实的例子就是机场登机的顺序。头等舱和商务舱乘客的优先级要高于经济舱乘客。再比如火车，老年人、孕妇和带小孩的乘客是享有优先检票权的。
2.2.2 分类
优先队列分为两类：
- 最小优先队列
- 最大优先队列
最小优先队列是把优先级的值最小的元素被放置到队列的最前面（代表最高的优先级）。比如有四个元素："John", "Jack", "Camila", "Tom"，他们的优先级值分别为4，3，2，1。
那么最小优先队列排序应该为："Tom"，"Camila"，"Jack"，"John"。
最大优先队列正好相反，把优先级值最大的元素放置在队列的最前面，以上面的为例，最大优先队列排序应该为："John", "Jack", "Camila", "Tom"。
2.2.2 实现
实现一个优先队列，有两种选项：
- 设置优先级，根据优先级正确添加元素，然后和普通队列一样正常移除
- 设置优先级，和普通队列一样正常按顺序添加，然后根据优先级移除
这里最小优先队列和最大优先队列我都采用第一种方式实现，大家可以尝试一下第二种。
所以我只重写enqueue()方法和print()方法，其他方法和上面的普通队列完全相同。完整代码见。
实现最小优先队列：
// 定义最小优先队列function MinPriorityQueue () { this.items = []; this.enqueue = enqueue; this.dequeue = dequeue; this.front = front; this.isEmpty = isEmpty; this.size = size; this.clear = clear; this.print = print;}复制代码 实现最小优先队列enqueue()方法和print()方法：
// 优先队列添加元素，要根据优先级判断在队列中的插入顺序function enqueue (element, priority) { var queueElement = { element: element, priority: priority }; if (this.isEmpty()) { this.items.push(queueElement); } else { var added = false; for (var i = 0; i < this.size(); i++) { if (queueElement.priority < this.items[i].priority) { this.items.splice(i, 0, queueElement); added = true; break ; } } if (!added) { this.items.push(queueElement); } }}// 打印队列里的元素function print () { var strArr = []; strArr = this.items.map(function (item) { return `${item.element}->${item.priority}`; }); console.log(strArr.toString());}复制代码 最小优先队列测试：
// 创建最小优先队列minPriorityQueue实例var minPriorityQueue = new MinPriorityQueue();console.log(minPriorityQueue.isEmpty()); // trueminPriorityQueue.enqueue("John", 1); // undefinedminPriorityQueue.enqueue("Jack", 3); // undefinedminPriorityQueue.enqueue("Camila", 2); // undefinedminPriorityQueue.enqueue("Tom", 3); // undefinedminPriorityQueue.print(); // "John->1,Camila->2,Jack->3,Tom->3"console.log(minPriorityQueue.size()); // 4console.log(minPriorityQueue.isEmpty()); // falseminPriorityQueue.dequeue(); // {element: "John", priority: 1}minPriorityQueue.dequeue(); // {element: "Camila", priority: 2}minPriorityQueue.print(); // "Jack->3,Tom->3"minPriorityQueue.clear(); // undefinedconsole.log(minPriorityQueue.size()); // 0复制代码 实现最大优先队列
最大优先队列只要将优先级的判断改为大于号">"就可以了：// 最大优先队列MaxPriorityQueue类function MaxPriorityQueue () { this.items = []; this.enqueue = enqueue; this.dequeue = dequeue; this.front = front; this.isEmpty = isEmpty; this.size = size; this.clear = clear; this.print = print;}// 优先队列添加元素，要根据优先级判断在队列中的插入顺序function enqueue (element, priority) { var queueElement = { element: element, priority: priority }; if (this.isEmpty()) { this.items.push(queueElement); } else { var added = false; for (var i = 0; i < this.items.length; i++) { // 注意，只需要将这里改为大于号就可以了 if (queueElement.priority > this.items[i].priority) { this.items.splice(i, 0, queueElement); added = true; break ; } } if (!added) { this.items.push(queueElement); } }}复制代码 最大优先队列测试：
// 创建最大优先队列maxPriorityQueue实例var maxPriorityQueue = new MaxPriorityQueue();console.log(maxPriorityQueue.isEmpty()); // truemaxPriorityQueue.enqueue("John", 1); // undefinedmaxPriorityQueue.enqueue("Jack", 3); // undefinedmaxPriorityQueue.enqueue("Camila", 2); // undefinedmaxPriorityQueue.enqueue("Tom", 3); // undefinedmaxPriorityQueue.print(); // "Jack->3,Tom->3,Camila->2,John->1"console.log(maxPriorityQueue.size()); // 4console.log(maxPriorityQueue.isEmpty()); // falsemaxPriorityQueue.dequeue(); // {element: "Jack", priority: 3}maxPriorityQueue.dequeue(); // {element: "Tom", priority: 3}maxPriorityQueue.print(); // "Camila->2,John->1"maxPriorityQueue.clear(); // undefinedconsole.log(maxPriorityQueue.size()); // 0复制代码 2.3 循环队列
还有一种队列实现叫做循环队列。
循环队列的一个例子就是击鼓传花游戏（Hot Potato）。在这个游戏中，孩子们围城一个圆圈，击鼓的时候把花尽快的传递给旁边的人。某一时刻击鼓停止，这时花在谁的手里，谁就退出圆圈直到游戏结束。重复这个过程，直到只剩一个孩子（胜者）。
下面我们在普通队列的基础上，实现一个模拟的击鼓传花游戏：
// 实现击鼓传花function hotPotato (nameList, num) { var queue = new Queue(); for (var i = 0; i < nameList.length; i++) { queue.enqueue(nameList[i]); } var eliminated = ''; while (queue.size() > 1) { // 循环num次，队首出来去到队尾 for (var i = 0; i < num; i++) { queue.enqueue(queue.dequeue()); } // 循环num次过后，移除当前队首的元素 eliminated = queue.dequeue(); console.log(`${eliminated}在击鼓传花中被淘汰！`); } // 最后只剩一个元素 return queue.dequeue();}// 测试var nameList = ["John", "Jack", "Camila", "Ingrid", "Carl"];var winner = hotPotato(nameList, 10);console.log(`最后的胜利者是：${winner}`);复制代码 执行结果为：
// John在击鼓传花中被淘汰！// Ingrid在击鼓传花中被淘汰！ // Jack在击鼓传花中被淘汰！// Camila在击鼓传花中被淘汰！// 最后的胜利者是：Carl复制代码
三、结束
本文会同步到我的，完整代码可以到我的，如果对你有帮助的话欢迎点一个Star~~