PROLOGUE · 開場
線性結構：資料的「排隊學」 cppds §3.1–3.2
堆疊（stack）、佇列（queue）、雙端佇列（deque）都是線性結構：元素之間只有「前後」關係，
新增與移除發生在端點。差別只在「哪一端進、哪一端出」：這個小差別決定了它們完全不同的用途。
本章你會學到的技術
1. 三種 ADT：stack（LIFO）、queue（FIFO）、deque（兩端皆可）。
2. C++ 實作：用 vector 自己刻，並理解每個操作的成本。
3. 經典應用：括號配對、進位轉換、中序轉後序、約瑟夫問題、模擬、迴文。
›按下方按鈕，把同一串資料 4→7→2 分別放進 stack 與 queue，再全部取出，觀察順序差異。
一句話記住
Stack：後進先出：復原（undo）、呼叫堆疊、括號配對。
Queue：先進先出：排隊、工作佇列、BFS。
Deque：兩端皆可：滑動視窗、迴文檢查。
為什麼叫「線性」？
元素按加入順序有唯一的前後位置；
操作只在端點發生。不同結構 = 不同的「進出端」組合。
PART 01 · 堆疊
Stack：後進先出的「盤子塔」 cppds §3.3–3.5
堆疊只在同一端（top）加入與移除。想像疊盤子：最後放上去的盤子一定最先被拿走
： LIFO（last-in first-out）。它天生就是「反轉順序」的機器。
先把 ADT 說清楚
Stack ADT 有六個操作：push(item)、pop()（移除並回傳 top）、
peek()（只看不拿）、isEmpty()、size()，加上建構子。
講義用一張操作序列表把行為完全定死（top 在最右邊）：
| 操作 | Stack 內容（top 在右） | 回傳 |
|---|
| s.isEmpty() | [] | true |
| s.push(4) | [4] | |
| s.push("dog") | [4, dog] | |
| s.peek() | [4, dog] | dog |
| s.push(true) | [4, dog, true] | |
| s.size() | [4, dog, true] | 3 |
| s.push(8.4) | [4, dog, true, 8.4] | |
| s.pop() | [4, dog, true] | 8.4 |
| s.pop() | [4, dog] | true |
表裡混放了數字、字串、布林，這是 ADT 層次的示意。
實作成 C++ template 之後，一個 Stack 物件只裝一種型別：Stack<double> 裝 double、
Stack<string> 裝字串。
›輸入值後按 push；pop 會移除 top。照上面那張表操作一輪試試。
C++ 實作 CODE
class Stack { // dscpp/stack.hpp（vector 尾端 = top）
vector<T> items;
bool isEmpty() { return items.empty(); }
void push(T item) { items.push_back(item); }
T pop() { T top = items.back(); items.pop_back(); return top; }
T peek() { return items.back(); }
int size() { return items.size(); }
};
操作成本（vector 尾端當 top）
push / pop / peekO(1)*
size / isEmptyO(1)
* push 是攤銷 O(1)。
同一個 ADT、另一種實作：Stack2 的代價
把 top 改放在 vector 的前端也做得出一個功能完全正確的 stack：
push 用 insert(begin())、pop 用 erase(begin())。
介面一模一樣，使用者根本分不出來。這就是抽象化的威力，也是它的陷阱：
每次 push 和 pop 都要把整排元素搬一格，O(1) 變 O(n)。
›數字會說話：對兩種實作各做 n 次 push，數一數總共搬移了幾個元素。
Stack2（top 在前端）CODE
void push(T item) {
items.insert(items.begin(), item); // O(n)!
}
T pop() {
T top = items.front();
items.erase(items.begin()); // O(n)!
return top;
}
邏輯等價、效能天差地遠。這個例子會在第 2 章（演算法分析）被正式量化。
QUIZ · Stack 行為
依序執行 s.push(4); s.push(7); s.pop(); s.push(2); s.peek(); 之後，peek() 回傳什麼？stack 內容（由底至頂）是什麼？
(A) 回傳 2；內容 [4, 2]
(B) 回傳 7；內容 [4, 7, 2]
(C) 回傳 4；內容 [2, 4]
講義練習：用 stack 反轉字串
講義在這裡留了一題：寫一個 revString(myStr)，用 stack 把字串反過來。
期待輸出：revString("NSYSU") 得到 "USYSN"。
原題挖了兩個空（push 迴圈與 pop 拼接），完整解答如下：
revString：進去一趟就反了 CODE
string revString(string myStr) {
stack<char> s;
for (char ch : myStr) s.push(ch); // ① 逐字推上去
string rStr = "";
while (!s.empty()) {
rStr = rStr + s.top(); // ② 彈出順序 = 反序
s.pop();
}
return rStr;
}
QUIZ · 為什麼 stack 天生會反轉？
revString 只是「全部 push、再全部 pop」就完成反轉。背後的原因是？
(A) LIFO：最後進去的最先出來，順序自然顛倒
(B) stack 內部把字串排序了
(C) top() 會從兩端輪流取
PART 02 · 括號配對
括號配對：stack 的第一個殺手級應用 cppds §3.6–3.7 · 講義補充
課堂投影片跳過這兩節（RISE skip）：屬自學補充，
但它是 stack 最經典的應用，編譯器每天都在做這件事，建議別跳。
編譯器怎麼知道 (() 少了一個右括號？由內往外配對的結構剛好是 LIFO：
每個右括號要配的是「最近一個還沒配對的左括號」：這就是 stack 的 top。
›輸入符號字串後按「開始」。開符號 push、閉符號 pop 配對。
虛擬碼 CODE
parChecker(symbolString):
Stack<char> s
for (char symbol : symbolString):
if symbol 是開符號 '(' '[' '{':
s.push(symbol)
else: // 閉符號
if s.isEmpty(): return false
if !matches(s.pop(), symbol): return false
return s.isEmpty() // 有剩 = 沒配完
三種失敗方式
① 閉符號來了但 stack 空（())( 的第 3 步）。
② pop 出來的開符號種類不合（[)）。
③ 掃完字串 stack 還有剩（(()）。
一般化：三種括號混用
實際的程式語言同時用 ()、[]、{}，
各自要維持自己的開閉關係。像 { { ( [ ] [ ] ) } ( ) } 是平衡的，
( [ ) ] 就不是：每個閉符號要配的不只是「某個開符號」，而是
stack 頂端那一個、而且種類要對。演算法只多一件事：pop 出來後用
matches() 檢查種類。
bool matches(char symLeft, char symRight) {
string allLefts = "([{{"; string allRights = ")]}}";
return allLefts.find(symLeft) == allRights.find(symRight);
} // 開閉符號在各自字串裡的位置相同，就是一對
完整的 balanceChecker() 在講義 §3.7：
跟 parChecker 只差在 pop 之後多呼叫一次 matches()。上面的動畫輸入框直接支援三種括號，
拿 [{()] 餵餵看。
PART 03 · 進位轉換
十進位 → 任意進位：「除基取餘」與順序反轉 cppds §3.8
反覆「除以基底、記下餘數」會由低位往高位產生數字，但我們書寫時要從高位開始：
又是一個「產生順序與使用順序相反」的問題，stack 出場。
虛擬碼 CODE
baseConverter(decNumber, base):
digits = "0123456789ABCDEF"
Stack<int> remStack
while decNumber > 0:
remStack.push(decNumber % base)
decNumber = decNumber / base // 整數除法
newString = ""
while !remStack.isEmpty():
newString += digits[remStack.pop()]
return newString
為什麼是 stack？
第一個算出的餘數是最低位，最後算出的是最高位。
pop 的順序剛好把它反過來：高位先出。
QUIZ · 進位轉換
baseConverter(25, 2) 的結果是？（可用上面的動畫驗證）
(A) 11001
(B) 10011
(C) 11010
PART 04 · 表達式
中序、前序、後序：把括號「編譯」掉 cppds §3.9
寫 A + B * C 的時候，誰先算？人靠兩條默契：優先權（乘除高於加減）
和結合律（同級由左到右）。括號則能推翻默契。這種「運算子夾在中間」的寫法叫
中序（infix），對人友善，對機器是負擔：電腦得先讀懂整套默契才知道順序。
把運算子搬到運算元前面就是前序（prefix），搬到後面就是後序
（postfix）。神奇的是，搬完之後括號和優先權表都不需要了，順序資訊全部藏在位置裡：
| 中序 | 前序 | 後序 |
|---|
| A + B | + A B | A B + |
| A + B * C | + A * B C | A B C * + |
| (A + B) * C | * + A B C | A B + C * |
| A + B * C + D | + + A * B C D | A B C * + D + |
| (A + B) * (C + D) | * + A B + C D | A B + C D + * |
| A + B + C + D | + + + A B C D | A B + C + D + |
手算技巧：全括號法
先把式子完全加括號（一個運算子一對括號）：A + B * C 變成 (A + (B * C))。
然後把每個運算子搬到它那對括號的右括號位置、拆掉括號，就是後序；
搬到左括號位置就是前序。考試手算用這招又快又不會錯。
機器轉換用 stack：運算元照抄、運算子進 stack 等待。
關鍵觀察是後序式裡運算子的出現順序，可能跟中序相反（+ 先讀到卻最後輸出），
「需要反轉的暫存」正是 stack 的主場。演算法四步：
- 開一個空的 opStack、一個空的輸出串列。
- 把中序字串切成 token（C++ 用 stringstream 逐個抽出來）。
- 由左到右掃：運算元直接輸出；
( 進 stack；) 一路 pop 輸出直到遇見 (；
一般運算子先把 stack 上「優先權大於等於自己」的全部 pop 輸出，再把自己 push 進去。
- 掃完把 stack 剩下的全部 pop 輸出。
infix tokens：
postfix 輸出：
›按「開始」把中序轉成後序。
postfix 求值（operand stack）：
›用 7 8 + 3 2 + / 走一次後序求值。
infix → postfix CODE
infixToPostfix(infixExpr):
Stack<string> opStack; postfixList = []
for (token : infixExpr):
if token 是運算元:
postfixList.push_back(token)
else if token == "(":
opStack.push(token)
else if token == ")":
pop 並輸出，直到遇見 "("
else: // 運算子
while !opStack.isEmpty() && prec[opStack.peek()] >= prec[token]: 輸出 pop
opStack.push(token)
postfix 求值 CODE
postfixEval(postfixExpr):
Stack<int> operandStack
for (token : postfixExpr):
if token 是數字:
operandStack.push(toInt(token))
else:
right = operandStack.pop(); left = operandStack.pop()
operandStack.push(doMath(token, left, right))
return operandStack.pop()
優先權（prec）
^4（右結合）
* /3
+ −2
(1（最低）
後序求值的一個細節：pop 的順序
看到運算子就 pop 兩次：第一次 pop 出來的是右運算元、第二次才是左運算元。
加法乘法無所謂，除法減法就是生死線：7 8 + 3 2 + / 是 15 / 5 = 3，
順序寫反會變成 5 / 15。輔助函式 doMath(op, op1, op2) 把四則收在一處，
完整程式在 dscpp/expression.hpp。
QUIZ · 中序轉後序
( A + B ) * C 的後序表達式是？
(A) A B + C *
(B) A B C + *
(C) + A B * C
QUIZ · 講義練習：加入次方運算子
要讓轉換器支援右結合的 ^（次方），pop 條件要怎麼改？5 * 3 ^ ( 4 - 2 ) 的後序是？
(A) 遇到 ^ 時只 pop「嚴格大於」自己的；答案 5 3 4 2 - ^ *
(B) 照舊 pop「大於等於」；答案 5 3 ^ 4 2 - *
(C) 把 ^ 的優先權設成最低
PART 05 · 佇列
Queue：先進先出的公平隊伍 cppds §3.10–3.12
佇列在 rear 加入、front 移除，先來的先被服務（FIFO）。
作業系統的工作排程、印表機隊伍、BFS 的「下一層名單」全是 queue。ADT 操作只有五個：
enqueue(item)、dequeue()、isEmpty()、size() 加建構子。
講義的操作序列表（front 在右，注意方向）：
| 操作 | Queue 內容（front 在右） | 回傳 |
|---|
| q.enqueue(4) | [4] | |
| q.enqueue("dog") | [dog, 4] | |
| q.enqueue(true) | [true, dog, 4] | |
| q.size() | [true, dog, 4] | 3 |
| q.enqueue(8.4) | [8.4, true, dog, 4] | |
| q.dequeue() | [8.4, true, dog] | 4 |
| q.dequeue() | [8.4, true] | dog |
›enqueue 加到 rear（右）、dequeue 從 front（左）取出。
C++ 實作 CODE
class Queue { // dscpp/queue.hpp（vector 前端 = rear）
vector<T> items;
bool isEmpty() { return items.empty(); }
void enqueue(T item) { items.insert(items.begin(), item); }
T dequeue() { T front = items.back(); items.pop_back(); return front; }
int size() { return items.size(); }
};
成本注意！
enqueue（insert 前端）O(n)
dequeue（pop_back）O(1)
教學版把 rear 放在 vector 前端，enqueue 要整體搬移。工業級請用環形緩衝或 std::deque。
PART 06 · 模擬
燙手山芋（約瑟夫問題）：用 queue 模擬傳遞 cppds §3.13
一群人圍圈傳山芋，數到第 num 下的人出局。queue 的「dequeue 再 enqueue」剛好模擬
把手上的東西傳給下一個人：front 的人傳完就排到隊伍最尾。
虛擬碼 CODE
hotPotato(nameList, num):
Queue<string> simQueue
for (name : nameList): simQueue.enqueue(name)
while simQueue.size() > 1:
for i = 0; i < num; i++:
simQueue.enqueue(simQueue.dequeue()) // 傳一次
simQueue.dequeue() // 淘汰 front
return simQueue.dequeue()
複雜度
每輪傳遞num 次
總計O(n · num)
QUIZ · 燙手山芋
六人 [Bill, David, Susan, Jane, Kent, Brad]、num = 7 時，最後留下來的是誰？（動畫可驗證）
(A) Susan
(B) Bill
(C) Brad
PART 07 · 模擬
印表機模擬：用機率與 queue 回答容量問題 cppds §3.14 · 講義補充
課堂投影片跳過本節（RISE skip）：屬自學補充。
它是 queue 在「容量規劃」上的完整實戰，也是全章唯一用到隨機模擬的地方。
實驗室的印表機可以切兩種模式：草稿模式一分鐘 10 頁，高品質模式一分鐘只剩 5 頁。
切高品質的話，學生會不會等到天荒地老？這是個真實的容量規劃問題，
而且沒辦法用公式直接算，因為「什麼時候有人送印、一次印幾頁」都是隨機的。
講義的做法：寫一個模擬，讓隨機事件跑一小時，統計平均等待時間。
先把機率定出來
實驗室平均 10 個人，每人每小時印兩次，所以每小時約 20 個列印工作。換算成秒：
20 件/小時 × 1 小時/60 分 × 1 分/60 秒 = 1 件/180 秒
於是每一秒擲一顆 180 面的骰子，擲到 180 就生出一個工作（頁數 1 到 20 均勻隨機）。
可能連續好幾秒都有工作、也可能好幾分鐘沒動靜，這正是模擬的本性。
三個類別、一個主迴圈
照真實世界的物件切：Task（記創建時間戳與頁數）、Printer（記頁速與剩餘工作量）、
print queue（就用我們的 Queue ADT）。主迴圈每秒一個 tick：
- 擲骰子決定要不要生新工作，生了就 enqueue（帶上目前秒數當時間戳）。
- 印表機空閒且 queue 非空：dequeue 下一個工作，目前秒數減時間戳就是它等了多久，記進等待清單。
- 印表機 tick 一秒：剩餘時間減一，歸零就變空閒。
Task CODE
class Task {
int timestamp, pages;
public:
Task(int time) {
timestamp = time;
pages = rand() % 20 + 1;
}
int getPages() { return pages; }
int waitTime(int now) {
return now - timestamp;
}
};
Printer CODE
class Printer {
int pageRate; Task *currentTask;
double timeRemaining;
public:
void tick() {
if (currentTask != NULL) {
timeRemaining -= 1;
if (timeRemaining <= 0) currentTask = NULL;
}
}
void startNext(Task *t) {
currentTask = t;
timeRemaining = t->getPages() * 60.0 / pageRate;
}
};
主迴圈 CODE
for (sec = 0; sec < 3600; sec++) {
if (newPrintTask()) // rand()%180 == 0
printQueue.push(new Task(sec));
if (!labPrinter.busy() && !printQueue.empty()) {
Task *next = printQueue.front(); printQueue.pop();
waitingTimes.push_back(next->waitTime(sec));
labPrinter.startNext(next);
}
labPrinter.tick();
}
| run | 5 頁/分 平均等待（秒） | 10 頁/分 平均等待（秒） |
|---|
›按下方按鈕各跑 10 次 3600 秒的模擬（固定亂數種子，可重現），跟講義同規模。
結論怎麼讀？
講義跑了 10 次 3600 秒：5 頁/分的平均等待起伏很大，動輒好幾分鐘還常留下未完成的工作；
10 頁/分則穩定壓在半分鐘以內、隊伍清空。等六分鐘拿一份報告，學生下一堂課都要遲到了，
所以「切高品質」這個提案大概不可行。注意這個結論的效力完全建立在假設上
（10 個人、每人每小時印兩次、1 到 20 頁均勻分布）。講義接著丟出三個 what-if，每一個都只要改參數重跑就能回答：
- 選課人數增加、實驗室平均多 20 個人呢？（到達率 1/180 要重算）
- 週六沒課，學生不趕時間呢？（同樣的等待時間，結論可能翻盤）
- 程式越寫越短、平均頁數下降呢？（頁數分布不再是 1 到 20 均勻）
模擬的價值就在這裡：改參數比改現實便宜太多，但模擬的可信度永遠不會超過它的假設。
QUIZ · 模擬的機率設定
為什麼是「每秒以 1/180 的機率生一個工作」？
(A) 每小時 20 件換算成秒就是平均 180 秒一件
(B) 180 是印表機印一頁的秒數
(C) 隨便訂的，跑起來像就好
PART 08 · 雙端佇列
Deque 與迴文檢查：兩端都能進出 cppds §3.15–3.18
雙端佇列（deque，唸作 deck）兩端都能加入與移除，一個人就能扮演 stack 或 queue。
代價是使用者要自己維持紀律，結構不再幫你防呆。六個操作：addFront、addRear、
removeFront、removeRear、isEmpty、size。
講義的操作表（front 在右，方向跟 queue 的表一致）：
| 操作 | Deque 內容（front 在右） | 回傳 |
|---|
| d.add_rear(4) | [4] | |
| d.add_rear("dog") | [dog, 4] | |
| d.add_front("cat") | [dog, 4, cat] | |
| d.add_front(true) | [dog, 4, cat, true] | |
| d.add_rear(8.4) | [8.4, dog, 4, cat, true] | |
| d.remove_rear() | [dog, 4, cat, true] | 8.4 |
| d.remove_front() | [dog, 4, cat] | true |
教學版把 front 放在 vector 尾端，所以
addFront／removeFront 是 O(1)，addRear／removeRear 是 O(n)：兩端的成本並不對稱。
STL 的 std::deque 用分段連續的儲存做到兩端都 O(1)，實戰直接用它。
›radar 是迴文嗎？兩端同時取出比較。
C++ 實作 CODE
class Deque { // dscpp/deque.hpp（vector 尾端 = front）
vector<T> items;
void addFront(T item) { items.push_back(item); }
void addRear(T item) { items.insert(items.begin(), item); }
T removeFront() { T f = items.back(); items.pop_back(); return f; }
T removeRear() { T r = items.front(); items.erase(items.begin()); return r; }
};
迴文檢查 CODE
palChecker(aString):
Deque<char> charDeque
for (ch : aString): charDeque.addRear(ch)
while charDeque.size() > 1:
first = charDeque.removeFront()
last = charDeque.removeRear()
if first != last:
return false
return true
EXERCISES · 練習
動手驗證：三個經典考點 cppds §3 綜合
EXERCISE 1 · stack 輸出序列
把 1, 2, 3 依序 push 進 stack，途中任何時刻都可以 pop。下列哪個輸出序列不可能出現？
(A) 3 1 2
(B) 2 1 3
(C) 1 3 2
EXERCISE 2 · 中序轉後序＋求值
10 + 3 * 5 / ( 16 - 4 ) 的後序是 10 3 5 * 16 4 - / +。用後序求值，答案是？（整數除法）
EXERCISE 3 · deque 成本
用「vector 尾端當 front」的 Deque 實作，下列哪組操作都是 O(1)？
(A) addFront 與 removeFront
(B) addRear 與 removeRear
(C) 四個操作全部
REFERENCE · 總覽
三種線性 ADT 一次比較 cppds §3 總覽
| ADT | 進 | 出 | 紀律 | 經典應用 |
|---|
| Stack | top | top | LIFO | 括號配對、進位轉換、undo、呼叫堆疊、DFS |
| Queue | rear | front | FIFO | 排程、模擬（燙手山芋、印表機）、BFS |
| Deque | 兩端 | 兩端 | 使用者自律 | 迴文、滑動視窗、工作竊取排程 |
教學版實作成本（以 vector 為底）
| 操作 | vector 尾端 | vector 前端 |
|---|
| 加入 / 移除 | O(1)（攤銷） | O(n)（整體搬移） |
| 本章的選擇 | Stack top、Queue front、Deque front | Queue rear、Deque rear |
關鍵概念複習
① stack = 反轉機器；queue = 公平機器；deque = 萬用但要自律。
② 「產生順序 ≠ 使用順序」→ stack；「先來先服務」→ queue。
③ ADT 與實作分離：介面不變，底層可以換 vector、linked list 或環形緩衝。