三、队列：优先队列+循环队列（击鼓传花算法）
隊列：
隊列是遵循FIFO（First In First Out，先進先出，也稱為先來先服務）原則的一組有序的項。隊列在尾部添加新元素，并從頂部移除元素。最新添加的元素必須排在隊列的末尾。
在現實中，最常見的隊列的例子就是排隊。
我們需要創建自己的類來表示一個隊列：
function Queue() {/** enqueue(element)：向隊列尾部添加一個（或多個）新的項。* dequeue()：移除隊列的第一（即排在隊列最前面的）項，并返回被移除的元素。* front()：返回隊列中第一個元素——最先被添加，也將是最先被移除的元素。隊列不做任何變動。* isEmpty()：如果隊列中不包含任何元素，返回true，否則返回false。* size()：返回隊列包含的元素個數，與數組的length屬性類似。* clear(): 清空隊列。* print(): 以字符串形式打印當前隊列。*/var items = [];this.enqueue = function (element) {items.push(element);};this.dequeue = function () {return items.shift();};this.front = functin(){return item[0];}this.isEmpty = function(){return items.length === 0;};this.size = function () {return items.length;};this.clear = function () {items = [];};this.print = function(){console.log(items.toString());} }實例化隊列：const queue = new Queue();
向隊列中依次添加三個元素：
1、queue.enqueue('John');
2、queue.enqueue('Jack');
3、queue.enqueue('camila');
下圖展示的是入列操作，以及隊列當前的狀態：
出列兩個元素（執行兩次dequeue方法）。
1、queue.dequeue();
2、queue.dequeue();
下圖展示了dequeue方法的執行過程：
優先隊列：
實現一個優先隊列，有兩種選項：
1、設置優先級，然后在正確的位置添加元素。
2、用入列操作添加元素，然后按照優先級移除它們。
優先隊列分為：
1、最小優先隊列：優先級：1>2>3>…
2、最大優先隊列；優先級：…>3>2>1
在下面的示例中是一個 “最小優先隊列” ，我們聲明一個優先隊列的類，在正確的位置添加元素，因此可以對它們使用默認的出列操作：
/** element: 排隊的人* priority: 優先級*/ function PriorityQueue() {var items = [];function QueueElement(element, priority) {this.element = element;this.priority = priority;}this.isEmpty = function () {return items.length === 0;};this.print = function () {console.log(items);};this.enqueue = function (element, priority) {var queueElement = new QueueElement(element, priority);if (this.isEmpty()) {items.push(queueElement);} else {var added = false;for (var 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);}}} }默認的Queue類和PriorityQueue類實現上的區別是，要向PriorityQueue添加元素，需要創建一個特殊的元素QueueElement。這個元素包含了要添加到隊列的元素（它可以是任意類型）及其在隊列中的優先級。
如果隊列為空，可以直接將元素入列。否則，就需要比較該元素與其他元素的優先級。當找到一個比要添加的元素的priority值更大（優先級更低）的項時，就把新元素插入到它之前（根據這個邏輯，對于其他優先級相同，但是先添加到隊列的元素，我們同樣遵循先進先出的原則）。要做到這一點，我們可以用JavaScript的array類的 splice 方法。一旦找到priority值更大的元素，就插入新元素并終止隊列循環。這樣，隊列也就根據優先級排序了。
如果要添加元素的priority值大于任何已有的元素，把它添加到隊列的末尾就行了。
執行以下操作：
1、var priorityQueue = new PriorityQueue();
2、priorityQueue.enqueue('John', 2);
3、priorityQueue.enqueue('Jack', 1);
4、priorityQueue.enqueue('Camila', 1);
5、priorityQueue.print();
入列方式如下圖所示：
打印結果（items）如下圖所示：
循環隊列：
循環隊列的一個例子就是擊鼓傳花游戲（HotPotato）。在這個游戲中，孩子們圍成一個圓圈，把花盡快地傳遞給旁邊的人。某一時刻傳花停止，這個時候花在誰手里，誰就退出圓圈結束游戲。重復這個過程，直到只剩一個孩子（勝者）。
/** nameList: 玩游戲的人* num: 傳遞次數* eliminated: 被淘汰的人*/ 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) {for (var i = 0; i < num; i++) {queue.enqueue(queue.dequeue());}eliminated = queue.dequeue();console.log(eliminated + '在擊鼓傳花游戲中被淘汰。');}return queue.dequeue(); } var names = ['John', 'Jack', 'Camila', 'Ingrid', 'Carl']; var winner = hotPotato(names, 7); console.log('勝利者：' + winner); /** 以上代碼輸出* Camila在擊鼓傳花游戲中被淘汰。* Jack在擊鼓傳花游戲中被淘汰。* Carl在擊鼓傳花游戲中被淘汰。* Ingrid在擊鼓傳花游戲中被淘汰。* 勝利者：John*/實現一個模擬的擊鼓傳花游戲，要用到開頭實現的Queue類。我們會得到一份名單，把里面的名字全都加入隊列。給定一個數字，然后迭代隊列。從隊列開頭移除一項，再將其添加到隊列末尾，模擬擊鼓傳花（如果你把花傳給了旁邊的人，你被淘汰的威脅立刻就解除了）。一旦傳遞次數達到給定的數字，拿著花的那個人就被淘汰了。最后只剩下一個人的時候，這個人就是勝者。
下圖是輸出過程：
總結
以上是生活随笔為你收集整理的三、队列：优先队列+循环队列（击鼓传花算法）的全部內容，希望文章能夠幫你解決所遇到的問題。
