『資料結構』佇列 Queue

前言

第三週我們歡迎「 Queue 佇列」，上週我們學會了 stack ，這兩個東西非常相似，但是原則不同！
佇列在尾端新增元素，在頂部移除，在現實中就像是我們在排隊一樣，排在前面的人會優先被服務到，因此也有一個別稱叫做「隊列」。

佇列什麼來頭？

佇列是遵守著 FIFO (First In First Out, 先進先出) 原則的有序項目。

一群相同性質元素的組合
具有 FIFO 特性
加入元素發生在尾端
刪除元素發生在頂端

在 Computer Science 中，最常看到的例子就是列印佇列。假如我們要列印三份文件，會開啟檔案並按下列印的按鈕，每個文件都會被發送至列印佇列，第一個發送到的文件會首先被列印出來，直到所有文件都列印完成。

建立佇列

宣告類別

首先來宣告一個類別來建立自己的佇列：

1
2
3

function Queue(){
  // 寫入屬性和方法
}

我們需要一個用於存放元素的結構，這邊可以使用陣列，就像上一篇 Stack 那樣做。

1	var items = []

宣告方法

接下來讓我們開始宣告方法吧！以下是佇列可用的幾種方法：

enqueue(element(s)): 向佇列尾端增加一個(或多個)新元素。
dequeue(): 刪除佇列第一個元素(即排在最前面的)，並返回該元素。
front(): 返回佇列第一個元素－－最先加入的。（與 Stack 的 peek 方法極為相似）
isEmpty(): 如果佇列中不包含任何元素，返回 true，反之返回 false。
size(): 返回佇列裡的元素個數，與陣列的 length 相同。

第一個就是我們的‘新增’，記住佇列只能從未端添加！

1
2
3

this.enqueue = function(element){
  items.push(element);
}

實作佇列移除元素。由於只能遵循先進先出原則，最先加入的也是最先移除的。

1
2
3

this.dequeue = function(){
  return items.shift();
}

只有 enqueue, dequeue 兩種方法可以新增及刪除元素，這樣確保了 Queue 類別先進先出的規則。

接著就是屬於比較輔助的方法。
如果想知道佇列最前面的元素是什麼，可以用 front 方法，將返回佇列 index 為 0 的元素。

1
2
3

this.front = function(){
  return items[0];
}

isEmpty 如果佇列為空，返回 true，反之 false。常用於驗證。

1
2
3

this.isEmpty = function(){
  return items.length == 0;
}

最後我們可以讓 Queue 類別實作類似 Array 類別的 length 屬性的方法。size 方法也和 Stack 裡的一樣：

1
2
3

this.size = function(){
  return items.length;
}

到這邊，我們完成了！

完整 Queue 類別

function Queue(){
  var items = [];

  this.enqueue = function(element){
    items.push(element);
  }

  this.dequue = function(){
    return items.shift();
  }

  this.front = function(){
    return items[0];
  }

  this.isEmpty = function(){
    return items.length == 0;
  }

  this.size = function()[
    return items.length;
  ]
}

與 Stack 不同之處

唯一的區別是 dequeue 方法和 front 方法，這是由於先進先出和後進先出原則的不同所造成的。

使用 Queue 類別

第一步：實例化 Queue。

1 2	var queue = new Queue(); console.log(queue.isEmpty()); // 輸出 true

新增一些元素：

1 2	queue.enqueue('Jack'); queue.enqueue('Mike');

可以玩一玩其他的方法～

1
2
3

queue.dequeue();
queue.size(); // 1
queue.isEmpty();  // false

特殊佇列

優先佇列

佇列大量的應用在我們的生活中和電腦科學中，我們在之前的實作原型佇列中，也有其他的延伸。
其中一個就是「優先佇列」。元素的添加、移除是基於優先級別的。機場的登機順序就是一個現實的例子，頭等艙和商務艙的優先級要高於經濟艙的乘客。有些國家，老人和孕婦也擁有高於其他乘客的級別。

另一個例子是醫院的急診室，醫生會優先處理重症患者，而護士通常會先行分類並決定次序。

取自https://ithelp.ithome.com.tw/m/articles/10266980

實作一個優先佇列，有兩個選項：

一是設定優先級，然後在正確的位置增加元素。
二是用入列操作新增元素，然候依照優先級移除它們。

function PriorityQueue(){
  var items = [];

  function QueueElement(element, priority){
    this.element = element;
    this.priority = priority;
  }

  this.enqueue = function(element, priority){
    var queueElement = newQueueElement(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 新增元素，需要建立一個特殊元素。這個元素包含了要添加到佇列的元素（它可以是任意類型）及其在佇列中的優先級。

如果佇列為空，可以直接加入。否則，就需要先比較該元素與其他元素的優先級。當找到一個比要添加元素還要大的 priority 項目時，就把新元素插入到它之前（根據這個邏輯，相同優先級通樣要遵循先進先出原則）。

補充一點，這裡實作的稱為最小優先佇列，因為優先級較小被放置在最前面（ 1 表示更高優先）。最大優先佇列則與之相反。

環狀佇列

另一個延伸就是「環狀佇列」。遊戲燙手山芋（ Hot Potato ）就是一個很好的例子。
遊戲中，玩家圍成一個圈，把物品盡快地遞給旁邊的人，某一時刻傳遞停止，而這時候物品在誰手上，誰就退出圓圈結束遊戲。重複這個過程，直到一位勝者出爐。

取自https://www.123rf.com/photo_10918100_passing-on-the-hot-potato-a-concept.html

實作：

function hotPotato(nameList, num){
  var queue = new Queue();

  for(let i=0; i<nameList.length; i++){
    queue.enqueue(nameList[i]);
  }

  var eliminated = '';
  while(queue.size() > 1){
    for(let i=0; i<num; i++){
      queue.enqueue(queue.dequeue());
    }
    eliminated = queue.dequeue();
    console.log(eliminated + '在遊戲中被淘汰。');
  }

  return queue.dequeue();
}

var names = ['John', 'Colin', 'Alice', 'Eileen', 'Jack'];
var winner = hotPotato(names, 7);
console.log('勝利者' + winner);

小結

我們這次學習了佇列的資料結構，自己實作佇列的演算法，學習如何透過 enqueue, dequeue 方法增加和刪除元素。還有兩種著名的特殊佇列實作：優先佇列、環狀佇列。

接下來我們將學習鏈結串列，比陣列更加複雜的資料結構呦！