前面我們學習了棧的實現(xiàn)，隊列和棧非常類似袱蜡，但是使用了不同的原則丝蹭，而非后進先出。
隊列是遵循FIFO（First In First Out坪蚁，先進先出）原則的一組有序的項奔穿。隊列在尾部添加新元素，并從頂部移除元素敏晤。最新添加的元素必須排在隊列的末尾贱田。
在計算機科學中，一個最常見的例子就是打印隊列嘴脾。比如說我們要打印五份文檔男摧。我們會打開每個文檔蔬墩，然后點擊打印按鈕。每個文檔都會被發(fā)送至打印隊列耗拓。第一個發(fā)送到打印隊列的文檔會首先被打印拇颅，以此類推，直到打印完所有文檔乔询。
創(chuàng)建普通隊列類：
// 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()：返回隊列包含的元素個數(shù)，與數(shù)組的length屬性類似
print()：打印隊列中的元素
clear()：清空整個隊列
下面我們來一一實現(xiàn)這些輔助方法：
// 向隊列尾部添加元素
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());
}
創(chuàng)建普通隊列實例進行測試：
// 創(chuàng)建Queue實例
var queue = new Queue();
console.log(queue.isEmpty());? ? // true
queue.enqueue("John");? ? ? ? ? ? // undefined
queue.enqueue("Jack");? ? ? ? ? ? // undefined
queue.enqueue("Camila");? ? ? ? ? // undefined
queue.print();? ? ? ? ? ? ? ? ? ? // "John,Jack,Camila"
console.log(queue.size());? ? ? ? // 3
console.log(queue.isEmpty());? ? // false
queue.dequeue();? ? ? ? ? ? ? ? ? // "John"
queue.dequeue();? ? ? ? ? ? ? ? ? // "Jack"
queue.print();? ? ? ? ? ? ? ? ? ? // "Camila"
queue.clear();? ? ? ? ? ? ? ? ? ? // undefined
console.log(queue.size());? ? ? ? // 0
普通隊列的添加和移除只依賴于先后順序监婶，先來的先添加，后來的后添加齿桃，然后按照先后順序依次從隊列移除惑惶。
但是，還有一種隊列叫優(yōu)先隊列短纵，元素的添加和移除是依賴優(yōu)先級的带污。
一個現(xiàn)實的例子就是機場登機的順序。頭等艙和商務艙乘客的優(yōu)先級要高于經(jīng)濟艙乘客香到。再比如火車鱼冀，老年人、孕婦和帶小孩的乘客是享有優(yōu)先檢票權(quán)的悠就。
優(yōu)先隊列分為兩類：
最小優(yōu)先隊列
最大優(yōu)先隊列
最小優(yōu)先隊列是把優(yōu)先級的值最小的元素被放置到隊列的最前面（代表最高的優(yōu)先級）千绪。比如有四個元素：”John”, “Jack”, “Camila”, “Tom”，他們的優(yōu)先級值分別為4梗脾，3荸型，2，1炸茧。
那么最小優(yōu)先隊列排序應該為：“Tom”瑞妇，”Camila”，”Jack”梭冠，”John”辕狰。
最大優(yōu)先隊列正好相反，把優(yōu)先級值最大的元素放置在隊列的最前面控漠，以上面的為例柳琢，最大優(yōu)先隊列排序應該為：“John”, “Jack”, “Camila”, “Tom”。
實現(xiàn)一個優(yōu)先隊列，有兩種選項：
設置優(yōu)先級柬脸，根據(jù)優(yōu)先級正確添加元素他去，然后和普通隊列一樣正常移除
設置優(yōu)先級，和普通隊列一樣正常按順序添加倒堕，然后根據(jù)優(yōu)先級移除
這里最小優(yōu)先隊列和最大優(yōu)先隊列我都采用第一種方式實現(xiàn)灾测，大家可以嘗試一下第二種。
所以我只重寫enqueue()方法和print()方法垦巴，其他方法和上面的普通隊列完全相同媳搪。完整代碼見我的github。
實現(xiàn)最小優(yōu)先隊列：
// 定義最小優(yōu)先隊列
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;
}
實現(xiàn)最小優(yōu)先隊列enqueue()方法和print()方法：
// 優(yōu)先隊列添加元素骤宣，要根據(jù)優(yōu)先級判斷在隊列中的插入順序
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());
}
最小優(yōu)先隊列測試：
// 創(chuàng)建最小優(yōu)先隊列minPriorityQueue實例
var minPriorityQueue = new MinPriorityQueue();
console.log(minPriorityQueue.isEmpty());? ? // true
minPriorityQueue.enqueue("John", 1);? ? ? ? // undefined
minPriorityQueue.enqueue("Jack", 3);? ? ? ? // undefined
minPriorityQueue.enqueue("Camila", 2);? ? ? // undefined
minPriorityQueue.enqueue("Tom", 3);? ? ? ? ? // undefined
minPriorityQueue.print();? ? ? ? ? ? ? ? ? ? // "John->1,Camila->2,Jack->3,Tom->3"
console.log(minPriorityQueue.size());? ? ? ? // 4
console.log(minPriorityQueue.isEmpty());? ? // false
minPriorityQueue.dequeue();? ? ? ? ? ? ? ? ? // {element: "John", priority: 1}
minPriorityQueue.dequeue();? ? ? ? ? ? ? ? ? // {element: "Camila", priority: 2}
minPriorityQueue.print();? ? ? ? ? ? ? ? ? ? // "Jack->3,Tom->3"
minPriorityQueue.clear();? ? ? ? ? ? ? ? ? ? // undefined
console.log(minPriorityQueue.size());? ? ? ? // 0
實現(xiàn)最大優(yōu)先隊列
最大優(yōu)先隊列只要將優(yōu)先級的判斷改為大于號”>”就可以了：在此我向大家推薦一個架構(gòu)學習交流群秦爆。交流學習群號：821169538 ?里面會分享一些資深架構(gòu)師錄制的視頻錄像：有Spring，MyBatis憔披，Netty源碼分析等限，高并發(fā)、高性能芬膝、分布式望门、微服務架構(gòu)的原理，JVM性能優(yōu)化锰霜、分布式架構(gòu)等這些成為架構(gòu)師必備的知識體系筹误。還能領取免費的學習資源，目前受益良多癣缅。
// 最大優(yōu)先隊列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;
}
// 優(yōu)先隊列添加元素厨剪，要根據(jù)優(yōu)先級判斷在隊列中的插入順序
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);
? ? }
? }
}
最大優(yōu)先隊列測試：
// 創(chuàng)建最大優(yōu)先隊列maxPriorityQueue實例
var maxPriorityQueue = new MaxPriorityQueue();
console.log(maxPriorityQueue.isEmpty());? ? // true
maxPriorityQueue.enqueue("John", 1);? ? ? ? // undefined
maxPriorityQueue.enqueue("Jack", 3);? ? ? ? // undefined
maxPriorityQueue.enqueue("Camila", 2);? ? ? // undefined
maxPriorityQueue.enqueue("Tom", 3);? ? ? ? ? // undefined
maxPriorityQueue.print();? ? ? ? ? ? ? ? ? ? // "Jack->3,Tom->3,Camila->2,John->1"
console.log(maxPriorityQueue.size());? ? ? ? // 4
console.log(maxPriorityQueue.isEmpty());? ? // false
maxPriorityQueue.dequeue();? ? ? ? ? ? ? ? ? // {element: "Jack", priority: 3}
maxPriorityQueue.dequeue();? ? ? ? ? ? ? ? ? // {element: "Tom", priority: 3}
maxPriorityQueue.print();? ? ? ? ? ? ? ? ? ? // "Camila->2,John->1"
maxPriorityQueue.clear();? ? ? ? ? ? ? ? ? ? // undefined
console.log(maxPriorityQueue.size());? ? ? ? // 0
還有一種隊列實現(xiàn)叫做循環(huán)隊列友存。
循環(huán)隊列的一個例子就是擊鼓傳花游戲（Hot Potato）丽惶。在這個游戲中，孩子們圍城一個圓圈爬立，擊鼓的時候把花盡快的傳遞給旁邊的人钾唬。某一時刻擊鼓停止，這時花在誰的手里侠驯，誰就退出圓圈直到游戲結(jié)束抡秆。重復這個過程，直到只剩一個孩子（勝者）吟策。
下面我們在普通隊列的基礎上儒士，實現(xiàn)一個模擬的擊鼓傳花游戲：
// 實現(xiàn)擊鼓傳花
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) {
? ? // 循環(huán)num次，隊首出來去到隊尾
? ? for (var i = 0; i < num; i++) {
? ? ? queue.enqueue(queue.dequeue());
}
? ? // 循環(huán)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}`);
執(zhí)行結(jié)果為：
// John在擊鼓傳花中被淘汰诅福！
// Ingrid在擊鼓傳花中被淘汰！
// Jack在擊鼓傳花中被淘汰拖叙！
// Camila在擊鼓傳花中被淘汰氓润！
// 最后的勝利者是：Carl
