視覺化概覽
graph LR EN["enqueue"] ==>|"加入尾端"| REAR subgraph FIFO 佇列 REAR["尾端 40"] --- C["30"] --- B["20"] --- FRONT["頭端 10"] end FRONT ==>|"取出頭端"| DE["dequeue"] style EN fill:#9f9,stroke:#333 style DE fill:#f99,stroke:#333 style REAR fill:#bbf,stroke:#333 style FRONT fill:#bbf,stroke:#333
💡 白話版：Queue 就像排隊買飯。先到的先買，後到的後買（FIFO）。印表機的列印佇列就是這個原理。
什麼是佇列？
佇列就像排隊，先來的先處理。
先進先出 (FIFO - First In First Out)
enqueue → [40] [30] [20] [10] → dequeue
rear front
(加入) (取出)
Stack vs Queue
| 比較 | Stack | Queue |
|---|---|---|
| 原則 | 後進先出 LIFO | 先進先出 FIFO |
| 比喻 | 一疊盤子 | 排隊買票 |
| 加入 | push (頂端) | enqueue (尾端) |
| 取出 | pop (頂端) | dequeue (頭端) |
核心操作
| 操作 | 說明 | 時間 |
|---|---|---|
| enqueue(x) | 加入到尾端 | O(1) |
| dequeue() | 取出頭端 | O(1) |
| peek() | 查看頭端 | O(1) |
| isEmpty() | 是否為空 | O(1) |
Enqueue 操作
enqueue(40):
front rear
↓ ↓
[10] [20] [30] → [10] [20] [30] [40]
↑
新加入
Dequeue 操作
dequeue() = 10:
front rear
↓ ↓
[10] [20] [30] → [20] [30]
↑ ↑
取出 新的 front
環形陣列 (Circular Array)
問題
用普通陣列實作 Queue，dequeue 後前面會空出來：
dequeue 3 次後：
[__, __, __, 40, 50]
↑
front
陣列前面浪費了！
解法：環形
讓 rear 繞回開頭使用空位：
陣列: [60, 70, __, 40, 50]
↑ ↑
rear front
邏輯上: [40] [50] [60] [70]
front rear
關鍵公式：
rear = (rear + 1) % capacity; // rear 往後移
front = (front + 1) % capacity; // front 往後移經典應用
1. 任務排程
印表機佇列:
enqueue(文件A)
enqueue(文件B)
enqueue(文件C)
列印順序: A → B → C (先來先印)
2. 廣度優先搜尋 (BFS)
圖的走訪，一層一層往外擴展
需要 Queue 來記錄「待訪問」的節點
3. 訊息佇列 (Message Queue)
生產者 → [Queue] → 消費者
訊息按順序處理
4. 緩衝區 (Buffer)
鍵盤輸入 → [Buffer Queue] → 程式處理
暫存輸入，依序處理
變體
雙端佇列 (Deque)
兩端都可以加入和取出：
addFirst ← [10] [20] [30] → addLast
removeFirst ← → removeLast
優先佇列 (Priority Queue)
不是 FIFO，而是按優先順序取出（用 Heap 實作）。
什麼時候用 Queue？
- 需要「先處理先來的」場景
- 廣度優先搜尋 (BFS)
- 任務排程、事件處理
- 緩衝、流量控制
相關檔案
- Java 實作：Queue.java
- 視覺化：queue.html