堆疊（LIFO：後進先出）與佇列（FIFO：先進先出）是最基本的兩種「受限存取」容器： 限制越多、實作越簡單、行為越好推理。函式呼叫、運算式求值、undo 機制靠堆疊； 排程、緩衝、訊息傳遞靠佇列。本單元同時給出「陣列版」與「鏈結版」實作， 並以 K&R §4.3 逆波蘭計算機的概念實作 RPN 求值器。
學習目標
- 實作陣列版與鏈結版堆疊：push / pop / peek / is_empty
- 用堆疊解兩個經典問題：括號匹配、後序運算式（RPN）求值
- 實作環形緩衝區（circular buffer）佇列與鏈結版佇列
- 理解兩種實作的取捨（容量固定 vs 動態、快取友善 vs 無上限）
- 能分析所有操作的時間複雜度
對照章節 / 參考來源
- K&R §4.3 External Variables（逆波蘭計算機：push/pop 的原始出處）
- K&R §5.1（本教材改以參數傳遞取代外部變數）
- CLRS 第 10.1 節 Stacks and queues
- 環形緩衝區：任何 OS 教科書的 producer/consumer 章節
觀念講解
1. 堆疊：LIFO
push(30) pop() -> 30
│ ▲
v │
┌──────┐ ┌──────┐
│ 30 │ <- top │ 20 │ <- top
│ 20 │ │ 10 │
│ 10 │ └──────┘
└──────┘只有一端（top）能進出。三個核心操作全部 O(1)：
| 操作 | 語意 | 陣列版 | 鏈結版 |
|---|---|---|---|
| push | 放到頂端 | a[top++] = v（滿了要擴容/報錯） |
頭插 |
| pop | 取出頂端 | return a[--top]（空了要報錯） |
刪頭 |
| peek | 看頂端不取出 | return a[top-1] |
讀頭 |
陣列版：連續記憶體、快取友善、但容量固定（或要 realloc）。 鏈結版：無容量上限、每次 push 一次 malloc、指標跳躍不利快取。
2. 應用一：括號匹配
掃描字串，左括號 push、右括號 pop 出來檢查是否成對：
for each ch in s:
if ch in "([{" -> push(ch)
if ch in ")]}" -> if stack empty or pop() 不是對應左括號 -> 不匹配
end: 堆疊必須為空這是編譯器語法檢查的雛形；編輯器的括號高亮、JSON 驗證器都是同一招。
3. 應用二：RPN（後序）計算機
K&R §4.3 的主角。中序 (1 + 2) * (7 - 3) 寫成後序 1 2 + 7 3 - *，
不需要括號與優先權，一個堆疊就能求值：
token 動作 堆疊
1 push 1 [1]
2 push 2 [1 2]
+ pop 2,1 push 3 [3]
7 push 7 [3 7]
3 push 3 [3 7 3]
- pop 3,7 push 4 [3 4]
* pop 4,3 push 12 [12]注意運算元順序：a - b 中 b 先 pop 出來（它是後 push 的）。
函式呼叫堆疊、JVM/CPython 的求值堆疊，本質上都是放大的 RPN 機。
4. 佇列：FIFO 與環形緩衝區
佇列從尾端進（enqueue）、頭端出（dequeue）。陣列版若 head 只會前進， 空間會「用過即棄」；解法是讓索引繞回開頭——環形緩衝區：
容量 5 的環形緩衝區（h=head, t=tail, count=3）：
0 1 2 3 4
┌─────┬─────┬─────┬─────┬─────┐
│ │ 20 │ 30 │ 40 │ │
└─────┴─────┴─────┴─────┴─────┘
^h ^t
enqueue: buf[t] = v; t = (t+1) % cap
dequeue: v = buf[h]; h = (h+1) % cap滿/空的判別：另存 count（最簡單），或犧牲一格（(t+1)%cap == h 即滿）。
容量取 2 的冪時，% cap 可換成 & (cap-1)（上一單元的位元技巧）。
環形緩衝區是嵌入式與驅動程式的明星結構：UART 收發、音訊緩衝、 lock-free SPSC 佇列，都是它。
5. 複雜度總表
| 操作 | 陣列堆疊 | 鏈結堆疊 | 環形佇列 | 鏈結佇列 |
|---|---|---|---|---|
| push / enqueue | O(1)* | O(1) | O(1) | O(1) |
| pop / dequeue | O(1) | O(1) | O(1) | O(1) |
| peek / front | O(1) | O(1) | O(1) | O(1) |
| 空間 | 預留容量 | 隨用隨配 | 預留容量 | 隨用隨配 |
* 動態陣列擴容時單次 O(n)，攤銷仍 O(1)。
範例程式
| 檔案 | 內容 | 編譯 / 執行 |
|---|---|---|
01_stack.c |
陣列版 + 鏈結版堆疊、括號匹配檢查器 | cc -std=c11 -Wall -Wextra -o out 01_stack.c && ./out |
02_rpn_calc.c |
RPN 計算機：tokenizer + 堆疊求值 + 錯誤處理（K&R §4.3 概念） | cc -std=c11 -Wall -Wextra -o out 02_rpn_calc.c && ./out |
03_queue.c |
環形緩衝區佇列 + 鏈結版佇列、繞回行為展示 | cc -std=c11 -Wall -Wextra -o out 03_queue.c && ./out |
常見錯誤與陷阱
- off-by-one：
top是「下一個空位」還是「頂端元素」？兩種慣例都行， 但 push/pop/peek 三處必須一致。a[top++]配a[--top]是一組。 - 空堆疊 pop / 滿堆疊 push 不檢查：陣列版直接越界（UB）， 一定要檢查並定義好錯誤行為（回傳錯誤碼或 assert）。
- 環形佇列滿/空判別：
h == t既可能是空也可能是滿， 必須額外用 count 或犧牲一格來區分，否則會覆蓋未讀資料。 - RPN 求值順序：
5 3 -應為 2；先 pop 的是右運算元，寫反變 -2。 - 鏈結版忘記釋放：pop 只把值拿走卻沒 free 節點；或程式結束前沒清空整條。
練習題
- 【易】為陣列堆疊加上
stack_grow：滿時用 realloc 倍增容量。 - 【易】用兩個堆疊實作一個佇列（enqueue 進 A，dequeue 時把 A 倒進 B 再 pop）。
- 【中】為 RPN 計算機加上
%（取餘）、neg（取負）、dup（複製頂端）指令。 - 【中】寫「中序轉後序」（shunting-yard 演算法），把
(1+2)*3轉成1 2 + 3 *後餵給現成的 RPN 求值器。 - 【中】實作 deque（雙端佇列）：用環形緩衝區支援 push/pop front/back 全 O(1)。
- 【難】實作「最小值堆疊」：除 push/pop 外，
get_min也要 O(1) （提示：輔助堆疊同步記錄目前最小值）。
補充：呼叫堆疊——你每天都在用的堆疊
函式呼叫機制本身就是一個堆疊：每次呼叫 push 一個「堆疊框」（stack frame）， return 就 pop。這解釋了很多現象：
main() 呼叫 f()，f() 呼叫 g()：
高位址 ┌──────────────┐
│ main 的框 │ 區域變數、返回位址
├──────────────┤
│ f 的框 │
├──────────────┤
sp ──> │ g 的框 │ <- 目前執行中
低位址 └──────────────┘ （堆疊向低位址成長）- 遞迴太深會 stack overflow：每層遞迴 push 一個框， 預設堆疊只有幾 MB，百萬層的遞迴必炸——這正是深遞迴要改成 「顯式堆疊 + 迴圈」的原因。
- 除錯器的 bt（backtrace）：印的就是這個堆疊的內容。
- 區域變數的生命週期：函式返回即 pop， 這就是「回傳區域變數位址」是懸空指標的結構性原因。
把遞迴改寫成顯式堆疊是一個重要技能：DFS、樹走訪、快速排序 都有「手動堆疊版」，能處理遞迴版會爆棧的深度。
補充：佇列在系統中的角色
- 排程器：作業系統的 run queue、印表機的工作佇列。
- 訊息傳遞：執行緒間的 message queue（見 13-concurrency 的 生產者-消費者——共享緩衝區就是一個加了鎖的環形佇列）。
- BFS：圖與樹的層序走訪天生需要佇列（見 08-trees 的 level_order）。
- 速率緩衝：音訊/網路封包的 jitter buffer，用環形佇列吸收突發流量。
延伸閱讀
- K&R §4.3（逆波蘭計算機完整程式）
- CLRS 第 10.1 節
- Wikipedia: Shunting-yard algorithm（Dijkstra）
- 《Making Embedded Systems》(Elecia White)：環形緩衝區實務
- PostScript / Forth 語言：整個語言就是一台 RPN 堆疊機