摘要：但是，還有一種隊(duì)列叫優(yōu)先隊(duì)列，元素的添加和移除是依賴優(yōu)先級(jí)的。分類優(yōu)先隊(duì)列分為兩類最小優(yōu)先隊(duì)列最大優(yōu)先隊(duì)列最小優(yōu)先隊(duì)列是把優(yōu)先級(jí)的值最小的元素被放置到隊(duì)列的最前面代表最高的優(yōu)先級(jí)。那么最小優(yōu)先隊(duì)列排序應(yīng)該為，，，。

前面我們學(xué)習(xí)了棧的實(shí)現(xiàn)，隊(duì)列和棧非常類似，但是使用了不同的原則，而非后進(jìn)先出。

隊(duì)列是遵循FIFO（First In First Out，先進(jìn)先出）原則的一組有序的項(xiàng)。隊(duì)列在尾部添加新元素，并從頂部移除元素。最新添加的元素必須排在隊(duì)列的末尾。

在計(jì)算機(jī)科學(xué)中，一個(gè)最常見(jiàn)的例子就是打印隊(duì)列。比如說(shuō)我們要打印五份文檔。我們會(huì)打開每個(gè)文檔，然后點(diǎn)擊打印按鈕。每個(gè)文檔都會(huì)被發(fā)送至打印隊(duì)列。第一個(gè)發(fā)送到打印隊(duì)列的文檔會(huì)首先被打印，以此類推，直到打印完所有文檔。

創(chuàng)建普通隊(duì)列類：

// 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;
}

隊(duì)列里面有一些聲明的輔助方法：

enqueue(element)：向隊(duì)列尾部添加新項(xiàng)

dequeue()：移除隊(duì)列的第一項(xiàng)（即排在隊(duì)列最前面的項(xiàng)），并返回被移除的元素

front()：返回隊(duì)列中第一個(gè)元素，隊(duì)列不做任何變動(dòng)，和Stack的peek()方法類似

isEmpty()：如果隊(duì)列中不包含任何元素，返回true，否則返回false

size()：返回隊(duì)列包含的元素個(gè)數(shù)，與數(shù)組的length屬性類似

print()：打印隊(duì)列中的元素

clear()：清空整個(gè)隊(duì)列

下面我們來(lái)一一實(shí)現(xiàn)這些輔助方法：

// 向隊(duì)列尾部添加元素
function enqueue (element) {
  this.items.push(element);
}

// 移除隊(duì)列的第一個(gè)元素，并返回被移除的元素
function dequeue () {
  return this.items.shift();
}

// 返回隊(duì)列的第一個(gè)元素
function front () {
  return this.items[0];
}

// 判斷是否為空隊(duì)列
function isEmpty () {
  return this.items.length === 0;
}

// 獲取隊(duì)列的長(zhǎng)度
function size () {
  return this.items.length;
}

// 清空隊(duì)列
function clear () {
  this.items = [];
}

// 打印隊(duì)列里的元素
function print () {
  console.log(this.items.toString());
}

創(chuàng)建普通隊(duì)列實(shí)例進(jìn)行測(cè)試：

// 創(chuàng)建Queue實(shí)例
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

普通隊(duì)列的添加和移除只依賴于先后順序，先來(lái)的先添加，后來(lái)的后添加，然后按照先后順序依次從隊(duì)列移除。

但是，還有一種隊(duì)列叫優(yōu)先隊(duì)列，元素的添加和移除是依賴優(yōu)先級(jí)的。

一個(gè)現(xiàn)實(shí)的例子就是機(jī)場(chǎng)登機(jī)的順序。頭等艙和商務(wù)艙乘客的優(yōu)先級(jí)要高于經(jīng)濟(jì)艙乘客。再比如火車，老年人、孕婦和帶小孩的乘客是享有優(yōu)先檢票權(quán)的。

優(yōu)先隊(duì)列分為兩類：

最小優(yōu)先隊(duì)列

最大優(yōu)先隊(duì)列

最小優(yōu)先隊(duì)列是把優(yōu)先級(jí)的值最小的元素被放置到隊(duì)列的最前面（代表最高的優(yōu)先級(jí)）。比如有四個(gè)元素："John", "Jack", "Camila", "Tom"，他們的優(yōu)先級(jí)值分別為4，3，2，1。

那么最小優(yōu)先隊(duì)列排序應(yīng)該為："Tom"，"Camila"，"Jack"，"John"。

最大優(yōu)先隊(duì)列正好相反，把優(yōu)先級(jí)值最大的元素放置在隊(duì)列的最前面，以上面的為例，最大優(yōu)先隊(duì)列排序應(yīng)該為："John", "Jack", "Camila", "Tom"。

實(shí)現(xiàn)一個(gè)優(yōu)先隊(duì)列，有兩種選項(xiàng)：

設(shè)置優(yōu)先級(jí)，根據(jù)優(yōu)先級(jí)正確添加元素，然后和普通隊(duì)列一樣正常移除

設(shè)置優(yōu)先級(jí)，和普通隊(duì)列一樣正常按順序添加，然后根據(jù)優(yōu)先級(jí)移除

這里最小優(yōu)先隊(duì)列和最大優(yōu)先隊(duì)列我都采用第一種方式實(shí)現(xiàn)，大家可以嘗試一下第二種。

所以我只重寫enqueue()方法和print()方法，其他方法和上面的普通隊(duì)列完全相同。完整代碼見(jiàn)我的github。

實(shí)現(xiàn)最小優(yōu)先隊(duì)列：

// 定義最小優(yōu)先隊(duì)列
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;
}

實(shí)現(xiàn)最小優(yōu)先隊(duì)列enqueue()方法和print()方法：

// 優(yōu)先隊(duì)列添加元素，要根據(jù)優(yōu)先級(jí)判斷在隊(duì)列中的插入順序
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);
    }
  }
}

// 打印隊(duì)列里的元素
function print () {
  var strArr = [];

  strArr = this.items.map(function (item) {
    return `${item.element}->${item.priority}`;
  });

  console.log(strArr.toString());
}

最小優(yōu)先隊(duì)列測(cè)試：

// 創(chuàng)建最小優(yōu)先隊(duì)列minPriorityQueue實(shí)例
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

實(shí)現(xiàn)最大優(yōu)先隊(duì)列

最大優(yōu)先隊(duì)列只要將優(yōu)先級(jí)的判斷改為大于號(hào)">"就可以了：

// 最大優(yōu)先隊(duì)列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)先隊(duì)列添加元素，要根據(jù)優(yōu)先級(jí)判斷在隊(duì)列中的插入順序
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++) {
      // 注意，只需要將這里改為大于號(hào)就可以了
      if (queueElement.priority > this.items[i].priority) {
        this.items.splice(i, 0, queueElement);
        added = true;
        break ;
      }
    }

    if (!added) {
      this.items.push(queueElement);
    }
  }
}

最大優(yōu)先隊(duì)列測(cè)試：

// 創(chuàng)建最大優(yōu)先隊(duì)列maxPriorityQueue實(shí)例
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

還有一種隊(duì)列實(shí)現(xiàn)叫做循環(huán)隊(duì)列。

循環(huán)隊(duì)列的一個(gè)例子就是擊鼓傳花游戲（Hot Potato）。在這個(gè)游戲中，孩子們圍城一個(gè)圓圈，擊鼓的時(shí)候把花盡快的傳遞給旁邊的人。某一時(shí)刻擊鼓停止，這時(shí)花在誰(shuí)的手里，誰(shuí)就退出圓圈直到游戲結(jié)束。重復(fù)這個(gè)過(guò)程，直到只剩一個(gè)孩子（勝者）。

下面我們?cè)谄胀?duì)列的基礎(chǔ)上，實(shí)現(xiàn)一個(gè)模擬的擊鼓傳花游戲：

// 實(shí)現(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次，隊(duì)首出來(lái)去到隊(duì)尾
    for (var i = 0; i < num; i++) {
      queue.enqueue(queue.dequeue());
    }
    // 循環(huán)num次過(guò)后，移除當(dāng)前隊(duì)首的元素
    eliminated = queue.dequeue();
    console.log(`${eliminated}在擊鼓傳花中被淘汰！`);
  }

  // 最后只剩一個(gè)元素
  return queue.dequeue();
}

// 測(cè)試
var nameList = ["John", "Jack", "Camila", "Ingrid", "Carl"];
var winner = hotPotato(nameList, 10);
console.log(`最后的勝利者是：${winner}`);

執(zhí)行結(jié)果為：

// John在擊鼓傳花中被淘汰！
// Ingrid在擊鼓傳花中被淘汰！ 
// Jack在擊鼓傳花中被淘汰！
// Camila在擊鼓傳花中被淘汰！
// 最后的勝利者是：Carl

本文會(huì)同步到我的個(gè)人博客，完整代碼可以到我的github倉(cāng)庫(kù)查看，如果對(duì)你有幫助的話歡迎點(diǎn)一個(gè)Star~~