你走進超商，前面已經有三個人在排隊。
你站到隊伍最後面，等待前面的人依序結帳。
我甚至不用特別講，你也能腦補這個機制：

1. 第一個來的人先結帳
2. 第二個來的人接著結帳
3. 新來的人排到最後面

不需要有人特別解釋規則，就知道自己應該站在哪裡。

但如果今天有人直接走到櫃檯前面插隊呢？

哪裡來的野蠻人，家裡沒教不能插隊嗎？
你要插我後面沒問題，但插我前面就不行 #@?...

所以我們在意的並不是資料順序被改變這麼簡單，是約定成俗的秩序被破壞了，也就是：

這個排隊系統原本承諾的規則被破壞了。

這就是 Queue 原本的語意。

從「排隊」開始想

假設現在有四位顧客依序走進超商：

Amy → Bob → Carol → David

店員一次只能服務一個人，那麼最直覺的處理順序就是：

Amy
Bob
Carol
David

我們可以把它想成：

出口                     入口
 ↓                        ↓
[Amy] [Bob] [Carol] [David]

Amy 最早進來，所以最先離開。
David 最晚進來，所以必須等待前面的人。

這種規則叫做：

FIFO（First In, First Out）

而專門用來表示這種先進先出順序的資料結構，就是 Queue。

Queue 真正表示的不是「一串資料」

乍看之下，Queue 好像只是一個 Array。
例如我們可以寫：

const customers = [
  "Amy",
  "Bob",
  "Carol",
  "David"
];

資料確實排成了一列。
Queue 通常只關心兩件事情：

enqueue：從尾端加入資料
dequeue：從前端取出資料

例如：

queue.enqueue("David");

代表 David 來到隊伍最後面。
而：

queue.dequeue();

代表目前排在最前面的人接受服務，並離開隊伍。

如果現在 Queue 是：

[Amy, Bob, Carol]

執行：

enqueue("David")

就會變成：

[Amy, Bob, Carol, David]

接著執行：

dequeue()

取出的只能是：

Amy

剩下：

[Bob, Carol, David]

這才是 Queue 最重要的地方。

是它限制了資料可以如何進出。

為什麼不能隨便插隊？

假設 David 說：

我只是新增一個資料而已，插在 Amy 前面有什麼差？

於是變成：

[David, Amy, Bob, Carol]

從 Array 的角度來看，完全沒有問題，Array 當然允許我們這麼做。
但從 Queue 的角度來看，問題就非常大，因為 David 原本是最後抵達的人，現在卻變成第一個接受服務的人。

也就是：

到達順序：
Amy → Bob → Carol → David

服務順序：
David → Amy → Bob → Carol

這已經不是 FIFO，順序已經亂了。
因此我們不能只問：

「這個資料結構能不能做到這件事？」

還必須問：

「做到這件事之後，原本的問題語意規則還存在嗎？」

這也是資料結構很重要的一個觀念：

• Array 給了我們非常大的操作自由
• Queue 則刻意限制這些自由

而這些限制不是甚麼缺陷，限制本身就是 Queue 想表達的規則。

Queue 解決的是「誰應該先被處理」

超商結帳只是其中一個例子，同樣的情況其實出現在很多地方。

客服電話

假設三個人依序打進客服中心：

A → B → C

客服人員一次只能處理一通電話，最基本的策略通常就是：

A 完成
↓
B 完成
↓
C 完成

如果新的電話每次都可以插到最前面，那麼比較早打電話的人可能永遠在聽等候音樂。

列印工作

辦公室只有一台印表機，三台電腦依序送出：

report.pdf
invoice.pdf
contract.pdf

印表機不能同時把三份文件全部印出來，所以列印工作通常會先進入一個等待佇列：

[report, invoice, contract]

印完 report：

[invoice, contract]

如果這時又有人送出：

presentation.pdf

它就加入尾端，變成：

[invoice, contract, presentation]

這其實又是一個 Queue。

問題的限制：處理能力有限

仔細看前面的例子，可以發現 Queue 通常不會憑空出現。
它背後往往有一個共同條件：

工作抵達的速度，可能比系統當下能處理的速度快。

超商可能有十個客人，但只有一個櫃檯。
客服中心可能同時收到一百通電話，但只有二十位客服。
印表機可能一次收到很多工作，但一次只能處理有限數量。
因此系統需要回答：

那些暫時處理不了的工作，要放在哪裡？

以及更重要的：

等資源空出來之後，下一個到底輪到誰？

Queue 給出的答案就是：

依照抵達順序處理。

所以 Queue 不只是「把資料排成一排」。
它其實是在替系統保存工作的到達順序。

用 JavaScript Array 做一個 Queue

在 JavaScript 裡，我們很容易使用 Array 模擬 Queue。
例如：

const queue = [];

queue.push("Amy");
queue.push("Bob");
queue.push("Carol");

const customer = queue.shift();

console.log(customer);
// Amy

這裡的 push()，負責把新資料加入尾端，可以把它理解成 enqueue，而 shift() 從最前面取出資料，可以理解成 dequeue。

因此：

queue.push("David");

相當於：

enqueue("David")

而：

queue.shift();

相當於：

dequeue()

如果只是少量資料或簡單應用，這種寫法非常直覺。

shift() 為什麼可能有成本？

先看這個 Array：

["Amy", "Bob", "Carol", "David"]

它可以想像成：

0       1       2        3
Amy     Bob     Carol    David

當我們執行 queue.shift();，移除 Amy 之後，Array 會變成：

0       1       2
Bob     Carol   David

也就是原本後面的元素，在 Array 的索引語意上全部往前移動。

概念上可以理解成：

Bob:   1 → 0
Carol: 2 → 1
David: 3 → 2

所以，如果 Queue 裡只有幾個元素，通常沒有什麼值得擔心的。
但如果裡面有：

100 個
1,000 個
100,000 個

元素呢？

Queue 越大，從 Array 前端移除元素可能涉及的工作也越多。
從一般資料結構的複雜度來看：

push()   → O(1) amortized
shift()  → O(n)

這也是為什麼：

JavaScript Array 可以表達 Queue 的行為，但不代表它永遠是最理想的 Queue 實作。

JavaScript 引擎內部可能做各種最佳化，但在設計資料結構時，我們不應該把 Queue 的效率假設建立在某個特定引擎剛好做了什麼最佳化之上。

那是不是不能用 Array？

也不是，這裡很容易掉進另一個誤區：

shift() 是 O(n)，所以永遠不能用。

這也不是資料結構真正想教我們的事情。
如果你的 Queue：

• 最多只有十幾筆資料
• 操作頻率很低
• 效能根本不是瓶頸
• Array 寫法反而最容易理解

那麼：

push()
shift()

完全夠用，資料結構不是在要求我們永遠使用「理論上最快」的實作。
而是在幫助我們辨認：

現在這個問題，需要保留什麼關係，又有哪些操作會隨著資料量增加而變得昂貴？

如果 Queue 真的非常大，而且 dequeue 非常頻繁，我們才有理由改變實作方式。
例如不真的刪除 Array 第一個元素，而是記住目前 Queue 的起點：

class Queue {
  constructor() {
    this.items = [];
    this.head = 0;
  }

  enqueue(value) {
    this.items.push(value);
  }

  dequeue() {
    if (this.isEmpty()) {
      return undefined;
    }

    const value = this.items[this.head];
    this.items[this.head] = undefined;
    this.head += 1;

    if (this.isEmpty()) {
      this.items = [];
      this.head = 0;
    }

    return value;
  }

  isEmpty() {
    return this.size === 0;
  }

  get size() {
    return this.items.length - this.head;
  }
}

這次 dequeue 不再呼叫 shift()，只是把 head 後移，記住下一個尚未處理的位置。
我們可以實際操作一次：

const queue = new Queue();

queue.enqueue("Amy");
queue.enqueue("Bob");
queue.enqueue("Carol");

console.log(queue.dequeue()); // Amy
console.log(queue.dequeue()); // Bob

queue.enqueue("David");

console.log(queue.size);      // 2
console.log(queue.dequeue()); // Carol
console.log(queue.dequeue()); // David
console.log(queue.isEmpty()); // true

即使 David 是在兩次 dequeue() 之後才加入，他仍然會排在 Carol 後面。每次 dequeue() 只會取出目前等待最久的資料。
例如：

[Amy, Bob, Carol, David]
 ↑
head = 0

取出 Amy 後，我們把已經處理過的位置清空，再將 head 往後移：

[空, Bob, Carol, David]
      ↑
    head = 1

我們沒有真的把整個 Array 往前搬。
只是告訴 Queue：

前面的資料已經處理過了，下一次從這裡開始。

當所有資料都被取出時，這個範例會清空 items，並把 head 歸零。
真正長時間運作、而且佇列幾乎不會清空的系統，還會進一步考慮定期整理底層陣列等空間回收策略。
但現階段最重要的不是把 Queue 寫得多完整，而是理解：

同樣是 FIFO，不同的底層表示方式，會讓操作成本不同。

這正好延續上一篇談到的概念資料結構是一種問題表述。
我們今天只是剛好看到這個觀念真正產生效果。

理解 Queue 不只去背 enqueue() 和 dequeue()

如果只背面試題，很容易把 Queue 記成：

enqueue
dequeue
FIFO

然後寫完一個 class，就認為自己學完 Queue 了。
但真正值得記住的其實是另一件事情。
假設今天有人問：

為什麼客服系統需要 Queue？

真正想聽的回答不是：

因為 Queue 有 enqueue 和 dequeue。

是去理解：

因為這個系統需要保留工作抵達的先後順序，並按照這個順序分配有限的處理資源。

enqueue() 和 dequeue() 只是這個規則最後呈現在程式上的操作。
問題得先存在，資料結構才跟著出現。

今天要記住的事情

Queue 最核心的概念是去理解：

「先來先服務」本身就是問題的一部分。

當我們決定使用 Queue，其實等於做出了一個規則：

先抵達
    ↓
先排隊
    ↓
先被處理

因此：

• FIFO 描述資料的處理順序
• Queue 用來保存這種順序
• enqueue 從尾端加入新的工作
• dequeue 從前端取得下一個工作
• 任意插隊會破壞 Queue 原本承諾的語意
• JavaScript Array 可以模擬 Queue
• 但底層表示方式仍然會影響操作成本

這才是我們真正開始學資料結構的地方：

去探討這個問題要求我們保存什麼規則。

但如果本來就不該先來先服務呢？

現在換一個情境。
急診室裡同時來了兩位病人：

10:00  輕微擦傷
10:02  嚴重呼吸困難

如果我們完全遵守 FIFO：

10:00 的病人
↓
10:02 的病人

好像哪裡不太對。
因為這個問題裡，誰先來的問題已經不再那麼重要了，反而是我們要去判斷：

誰比較緊急？

也就是說，有些問題需要 Queue。
但有些問題雖然也在「排隊」，決定順序的規則卻完全不同。

如果不是先到先服務呢？

下一篇，我們就來看看 Priority Queue：

當「順序」不再由時間決定，而是由優先級決定時，資料結構又會怎麼改變？