Queue 佇列

排隊這件事，連資料結構都要遵守。

先來的先走

Queue = 先進先出（FIFO）。從尾巴進、從頭出。所有操作 O(1)。它是 BFS、任務排程、訊息佇列的基礎。跟 Stack 的差異就一條：Stack 是「最後來的先走」，Queue 是「先來的先走」。

排隊的規則

enqueue →  [40] [30] [20] [10]  → dequeue
           rear            front

操作	做什麼	時間
enqueue(x)	排到隊尾	O(1)
dequeue()	從隊頭離開	O(1)
peek()	看隊頭是誰	O(1)

跟 Stack 一樣簡單，只是方向不同——一端進、另一端出：

enqueue(40)：從 rear 進
[10][20][30]  →  [10][20][30][40]
                              ↑ 新加在隊尾
 
dequeue()：從 front 出
[10][20][30]  →  [20][30]
 ↑ 取走 10        ↑ 新的 front

Stack 是同一端進出，Queue 是兩端各管一件事，這是它們唯一的差別。

環形陣列：解決空間浪費

用普通陣列實作 Queue 有個問題——dequeue 之後前面會空出來：

dequeue 了 3 次：
[__, __, __, 40, 50]
              ↑ front
 
前面三格浪費掉了！

解法是讓指標繞回去，把陣列當成一個環：

實際陣列: [60, 70, __, 40, 50]
               ↑   ↑
             rear  front
 
邏輯上:   [40] [50] [60] [70]

關鍵就一行：index = (index + 1) % capacity。到底了就繞回 0。

這個技巧在 OS 的 kernel buffer、網路封包處理裡到處都是。Java 的 ArrayDeque 底層就是環形陣列。

🎬 互動視覺化：線性結構操作動畫 — 切到 Queue 分頁，看 front / rear 兩個指標怎麼繞著環形陣列跑，dequeue 後空出來的格子怎麼被重新利用。

Queue 無所不在

BFS（廣度優先搜尋） 用 Queue 一層一層往外擴展——這是 Queue 在演算法裡最重要的應用。沒有 Queue 就沒有 BFS。

訊息佇列（Message Queue） 像 RabbitMQ、Kafka，本質上就是分散式的 Queue。生產者丟訊息進去，消費者按順序拿出來處理。

印表機、鍵盤輸入、網路封包——所有「先來先處理」的場景都是 Queue。

你有沒有想過，為什麼 JavaScript 的事件處理叫「event queue」？因為瀏覽器把事件按照發生順序排進 Queue，event loop 從頭一個一個取出來處理。setTimeout(fn, 0) 不是「立即執行」，而是「排到隊尾，等前面的事做完」。

變體：Priority Queue

普通 Queue 是先來先走。但有時候你需要「最重要的先走」——這就是 Priority Queue。

它不是 FIFO，而是按照優先度出隊。底層通常用 Heap 實作，不是用陣列排序（那樣太慢了）。

急診室的叫號就是 Priority Queue：不是先來的先看，是最嚴重的先看。

---

Queue 的公平性讓人安心——但現實生活中，大部分的 Queue 最後都會變成 Priority Queue。

接下來往哪走

• Heap 堆積 — Priority Queue 的底層：不是先進先出，是最重要的先走
• Graph 圖 — Queue 的殺手級應用：BFS 靠它一層一層擴散
• Deque 雙端佇列 — Queue 的雙頭版：兩端都能進出