線性結構 — Linear Structures Interactive（C++）

📌 本頁使用方式（cppds Ch.3｜講義 05）

① 照節次讀：每一節先讀說明、動手玩互動元件，預測結果再按按鈕驗證。 ② 對照講義：頁上 §徽章對應 cppds 章節；細節與完整程式請回講義 05 與 cppds 原文。 ③ 每節做 quiz：答錯就回到該節重讀，不要往下跳。 ④ 最後翻關鍵詞彙卡（16 張）自測術語（中文為主、術語附英文），並用 REF 總覽區當速查表。標「講義補充」的節是課堂沒細講的延伸，第一輪可略過。

📑 講義 05 PDF 🖥 講義 05 HTML 📖 cppds 原文（LinearBasic）📘 Hello 演算法（堆疊與佇列）🏠 章節總覽

CONTENTS · 內容目錄

P00線性結構總覽 P01堆疊 Stack P02括號配對 P03進位轉換 P04中序⇄後序 P05佇列 Queue P06燙手山芋 P07印表機模擬 P08雙端佇列與迴文 EX練習題 REF總覽比較 CARD關鍵詞彙卡（16 張）

PROLOGUE · 開場

線性結構：資料的「排隊學」 cppds §3.1–3.2

堆疊（stack）、佇列（queue）、雙端佇列（deque）都是線性結構：元素之間只有「前後」關係，新增與移除發生在端點。差別只在「哪一端進、哪一端出」：這個小差別決定了它們完全不同的用途。

本章你會學到的技術 1. 三種 ADT：stack（LIFO）、queue（FIFO）、deque（兩端皆可）。
2. C++ 實作：正文使用 STL stack/queue/deque；課程自製 API 明標為作業補充。
3. 經典應用：括號配對、進位轉換、中序轉後序、約瑟夫問題、模擬、迴文。

Stack：同一端進出（LIFO）

Queue：尾進頭出（FIFO）

速度

一句話記住

Stack：後進先出：復原（undo）、呼叫堆疊、括號配對。
Queue：先進先出：排隊、工作佇列、BFS。
Deque：兩端皆可：滑動視窗、迴文檢查。

為什麼叫「線性」？

元素按加入順序有唯一的前後位置；操作只在端點發生。不同結構 = 不同的「進出端」組合。

PART 01 · 堆疊

Stack：後進先出的「盤子塔」 cppds §3.3–3.5

堆疊只在同一端（top）加入與移除。想像疊盤子：最後放上去的盤子一定最先被拿走： LIFO（last-in first-out）。它天生就是「反轉順序」的機器。

圖 1：stack 只有一個開口 top；push 放上去、pop 拿下來都在同一端，底部與中間的元素完全動不了。

先把 ADT 說清楚

cppds 的 C++ 正文以 std::stack 為主線：push(item)、 top()、pop()、empty()、size()。 STL 的 pop() 只移除、不回傳；需要值時要先讀 top()。

操作	Stack 內容（top 在右）	回傳
s.empty()	[]	true
s.push(4)	[4]
s.push(7)	[4, 7]	void
s.top()	[4, 7]	7
s.push(2)	[4, 7, 2]	void
s.size()	[4, 7, 2]	3
s.pop()	[4, 7]	void

一個 C++ stack 物件只裝一種型別。

C++ 實作 CODE

// cppds 正文：C++ Standard Library container adapter
std::stack<std::string> s;
s.push("first");
s.push("second");
std::cout << s.top(); // 先讀值
s.pop(); // pop 回傳 void
bool done = s.empty();

std::stack 操作成本

push / pop / topO(1)

size / emptyO(1)

課程實作補充：Stack2 的代價

把 top 改放在 vector 的前端也做得出一個功能完全正確的 stack： push 用 insert(begin())、pop 用 erase(begin())。介面一模一樣，使用者根本分不出來。這就是抽象化的威力，也是它的陷阱： 每次 push 和 pop 都要把整排元素搬一格，O(1) 變 O(n)。

n（push n 次、再全部 pop）	Stack（top 在尾端）搬移元素數	Stack2（top 在前端）搬移元素數
n = 10	0	90
n = 100	0	9,900
n = 1,000	0	999,000

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.top(); 之後，top() 回傳什麼？stack 內容（由底至頂）是什麼？

(A) 回傳 2；內容 [4, 2]

(B) 回傳 7；內容 [4, 7, 2]

講義練習：用 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 內部把字串排序了

cppds 正文 · STL 與課程 API 對照

std::stack<int> s;
s.push(4);
int x = s.top();
s.pop();              // 回傳 void

std::queue<int> q;
q.push(4);
int y = q.front();
q.pop();              // 回傳 void

正文以 std::stack／std::queue／std::deque 為主。pythonds3 的 Stack<T> 使用 peek()/isEmpty()；HW3 定容量 Stack<T>(capacity) 使用 stackTop() 或 peek(index)，另有 isFull()。三套 API 不可混用。

PART 02 · 括號配對

括號配對：stack 的第一個殺手級應用 cppds §3.6–3.7 · 講義補充

課堂投影片跳過這兩節（RISE skip）：屬自學補充，但它是 stack 最經典的應用，編譯器每天都在做這件事，建議別跳。

編譯器怎麼知道 (() 少了一個右括號？由內往外配對的結構剛好是 LIFO：每個右括號要配的是「最近一個還沒配對的左括號」：這就是 stack 的 top。

符號 stack

速度

虛擬碼 CODE

bool parChecker(const string& symbols) {
    stack<char> s;
    for (char symbol : symbols) {
        if (isOpen(symbol)) s.push(symbol);
        else { // 閉符號
            if (s.empty()) return false;
            char open = s.top(); s.pop();
            if (!matches(open, symbol)) return false; }
    } return s.empty(); }

三種失敗方式

① 閉符號來了但 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 出場。

餘數 stack

速度

虛擬碼 CODE

string baseConverter(int value, int base) {
    string digits = "0123456789ABCDEF";
    stack<int> remainders;
    while (value > 0) {
        remainders.push(value % base); value /= base; }
    string result;
    while (!remainders.empty()) {
        result += digits[remainders.top()];
        remainders.pop(); }
    return result; }

為什麼是 stack？

第一個算出的餘數是最低位，最後算出的是最高位。 pop 的順序剛好把它反過來：高位先出。

QUIZ · 進位轉換

baseConverter(25, 2) 的結果是？（可用上面的動畫驗證）

(A) 11001

(B) 10011

講義完整實作：從虛擬碼到 C++

講義 05 · divideBy2 與萬用 baseConverter

#include <iostream>
#include <stack>
#include <string>
using namespace std;
 
string divideBy2(int decimalNum) {
    stack<int> remStack;
    while (decimalNum > 0) {
        remStack.push(decimalNum % 2);
        decimalNum = decimalNum / 2;
    }
    string binString = "";
    while (!remStack.empty()) {
        binString += to_string(remStack.top());
        remStack.pop();
    }
    return binString;
}
 
string baseConverter(int decimalNum, int base) {
    string digits = "0123456789ABCDEF";
    stack<int> remStack;
    while (decimalNum > 0) {
        remStack.push(decimalNum % base);  decimalNum /= base;
    }
    string newString = "";
    while (!remStack.empty()) {
        newString += digits[remStack.top()];  remStack.pop();
    }
    return newString;
}
 
int main() {
    cout << divideBy2(42) << " " << divideBy2(31) << endl;
    cout << baseConverter(25, 2) << " " << baseConverter(25, 16) << endl;
    return 0;
}
 

預期輸出

101010 11111
11001 19

baseConverter 見上方動畫程式碼。兩個函式的骨架一模一樣：餘數進 stack、商繼續除、最後把 stack 倒出來。baseConverter 只多了一張 digits 對照表，base 16 的餘數 10~15 才印得出 A~F。

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))。然後把每個運算子搬到它那對括號的右括號位置、拆掉括號，就是後序；搬到左括號位置就是前序。考試手算用這招又快又不會錯。

圖 2：綠色是內層的 *、紅色是外層的 +；三列的欄位是對齊的，可以直接看出誰搬到哪裡。

機器轉換用 stack：運算元照抄、運算子進 stack 等待。關鍵觀察是後序式裡運算子的出現順序，可能跟中序相反（+ 先讀到卻最後輸出），「需要反轉的暫存」正是 stack 的主場。演算法四步：

開一個空的 opStack、一個空的輸出串列。
把中序字串切成 token（C++ 用 stringstream 逐個抽出來）。
由左到右掃：運算元直接輸出；( 進 stack；) 一路 pop 輸出直到遇見 (；一般運算子先把 stack 上「優先權大於等於自己」的全部 pop 輸出，再把自己 push 進去。
掃完把 stack 剩下的全部 pop 輸出。

infix tokens：

opStack

postfix 輸出：

速度

postfix 求值（operand stack）：

operandStack

速度

infix → postfix CODE

vector<string> infixToPostfix(const vector<string>& tokens) {
    stack<string> ops; vector<string> output;
    for (const string& token : tokens) {
        if (isOperand(token)) output.push_back(token);
        else if (token == "(") ops.push(token);
        else if (token == ")") popUntilLeftParen(ops, output);
        else {
            while (shouldPop(ops, token)) { output.push_back(ops.top()); ops.pop(); }
            ops.push(token);
        }
    } drain(ops, output);
    return output; }

postfix 求值 CODE

int postfixEval(const vector<string>& tokens) {
    stack<int> operands;
    for (const string& token : tokens) {
        if (isNumber(token)) operands.push(stoi(token));
        else {
            int right = operands.top(); operands.pop();
            int left = operands.top(); operands.pop();
            operands.push(doMath(token, left, right)); }
    } return operands.top(); }

優先權（prec）

^4（右結合）

* /3

+ −2

(1（最低）

QUIZ · 中序轉後序

( A + B ) * C 的後序表達式是？

(A) A B + C *

(B) A B C + *

QUIZ · 講義練習：加入次方運算子

要讓轉換器支援右結合的 ^（次方），pop 條件要怎麼改？5 * 3 ^ ( 4 - 2 ) 的後序是？

(A) 遇到 ^ 時只 pop「嚴格大於」自己的；答案 5 3 4 2 - ^ *

(B) 照舊 pop「大於等於」；答案 5 3 ^ 4 2 - *

講義完整實作：轉換器與求值器的 C++ 全文

講義 05 · infixToPostfix 完整程式（pythonds3/cppds/expression.hpp）

string infixToPostfix(string infixExpr) {
    map<string, int> prec = {{"*", 3}, {"/", 3}, {"+", 2}, {"-", 2}, {"(", 1}};
    stack<string> opStack;
    vector<string> postfixList;
    stringstream ss(infixExpr);
    string token;
    while (ss >> token) {
        if (isalnum(token[0])) {
            postfixList.push_back(token);        // 運算元直接輸出
        } else if (token == "(") {
            opStack.push(token);
        } else if (token == ")") {
            while (!opStack.empty() && opStack.top() != "(") {
                postfixList.push_back(opStack.top());
                opStack.pop();
            }
            opStack.pop();                       // 丟掉那個 "("
        } else {
            // 優先級 >= 自己的都先請出來
            while (!opStack.empty() && prec[opStack.top()] >= prec[token]) {
                postfixList.push_back(opStack.top());
                opStack.pop();
            }
            opStack.push(token);
        }
    }
    while (!opStack.empty()) {
        postfixList.push_back(opStack.top());
        opStack.pop();
    }
    string result = "";
    for (unsigned i = 0; i < postfixList.size(); i++) {
        if (i > 0) result += " ";
        result += postfixList[i];
    }
    return result;
}
 

prec 表把「(」設成最低的 1 是關鍵巧思：左括號躺在 stack 裡時，誰都「贏不過」它，自然不會被提前彈出。整段程式就是上面互動動畫的逐行文字版。

講義 05 · 轉換器使用畫面

#include <iostream>
#include "pythonds3/cppds/expression.hpp"
using namespace std;
 
int main() {
    cout << infixToPostfix("A * B + C * D") << endl;
    cout << infixToPostfix("( A + B ) * C - ( D - E ) * ( F + G )") << endl;
    return 0;
}
 

預期輸出

A B * C D * +
A B + C * D E - F G + * -

注意 token 之間要有空白（程式用 stringstream 以空白切 token）。第二條把五組括號全部「編譯」掉了：後序完全不需要括號。

講義 05 · A * B + C * D 逐 token 追蹤

token	opStack（頂在右）	輸出串
A		A
*	*	A
B	*	A B
+	+ ← * 優先級較高，先彈出	A B *
C	+	A B * C
*	+ * ← * 比 + 高，疊上去	A B * C
D	+ *	A B * C D
收尾	全部倒出	A B * C D * +

講義 05 · postfixEval 完整程式

double doMath(string op, double op1, double op2) {
    if (op == "*") return op1 * op2;
    else if (op == "/") return op1 / op2;
    else if (op == "+") return op1 + op2;
    else return op1 - op2;
}
 
double postfixEval(string postfixExpr) {
    stack<double> operandStack;
    stringstream ss(postfixExpr);
    string token;
    while (ss >> token) {
        if (isdigit(token[0])) {
            operandStack.push(stod(token));
        } else {
            double operand2 = operandStack.top(); operandStack.pop();
            double operand1 = operandStack.top(); operandStack.pop();
            operandStack.push(doMath(token, operand1, operand2));
        }
    }
    return operandStack.top();
}
 
int main() {
    cout << postfixEval("7 8 + 3 2 + /") << endl;
    return 0;
}
 

預期輸出

彈出順序是天大的事：先彈出的是 operand2（右運算元）。加法乘法看不出差別，除法減法一交換就錯：7 8 + 3 2 + / 是 15 ÷ 5 = 3，弄反就變 1/3。

講義 05 · 課後練習：讓 ^ 右結合

string infixToPostfix(string infixExpr) {
    // 你的程式碼：加入次方運算子 ^（優先級最高、右結合）
    // 提示：右結合代表「同優先級不彈出」，
    //       prec[opStack.top()] >= prec[token] 的 >= 要對 ^ 改成 >
    return result;
}
 
int main() {
    cout << infixToPostfix("5 * 3 ^ ( 4 - 2 )") << endl;
    return 0;
}
 

完成後的預期輸出

5 3 4 2 - ^ *

右結合是指 2 ^ 3 ^ 2 = 2 ^ (3 ^ 2) = 512，不是 (2 ^ 3) ^ 2 = 64。只改優先級不夠，還得改「同級要不要彈」的判斷。

PART 05 · 佇列

Queue：先進先出的公平隊伍 cppds §3.10–3.12

佇列在 rear 加入、front 移除，先來的先被服務（FIFO）。作業系統的工作排程、印表機隊伍、BFS 的「下一層名單」全是 queue。cppds C++ 正文使用 std::queue：push 從 rear 加入，front 讀取最前端， pop 移除但不回傳。作業的 enqueue/dequeue/isEmpty 是課程實作補充。

操作	Queue 內容（front 在左）	回傳
q.push(4)	[4]	void
q.push(7)	[4, 7]	void
q.push(2)	[4, 7, 2]	void
q.front()	[4, 7, 2]	4
q.back()	[4, 7, 2]	2
q.pop()	[7, 2]	void

C++ 實作 CODE

// cppds 正文：std::queue，預設以 std::deque 儲存
std::queue<std::string> q;
q.push("first");
q.push("second");
std::cout << q.front();
q.pop(); // pop 回傳 void
std::cout << q.back();

成本與介面

std::queue push / pop / frontO(1)

課程 vector 版的 enqueue 是 O(n)，只用來研究表示法；一般 C++ 程式優先用 STL。

PART 06 · 模擬

燙手山芋（約瑟夫問題）：用 queue 模擬傳遞 cppds §3.13

一群人圍圈傳山芋，數到第 num 下的人出局。queue 的「讀 front、push 到 rear、再 pop」剛好模擬 把手上的東西傳給下一個人：front 的人傳完就排到隊伍最尾。

num: 速度

虛擬碼 CODE

string hotPotato(vector<string> names, int num) {
    queue<string> q;
    for (string name : names) q.push(name);
    while (q.size() > 1) {
        for (int i = 0; i < num; ++i) {
            q.push(q.front()); q.pop(); // 傳一次
        } q.pop(); // 淘汰 front
    } return q.front();
}

複雜度

每輪傳遞num 次

總計O(n · num)

QUIZ · 燙手山芋

六人 [Bill, David, Susan, Jane, Kent, Brad]、num = 7 時，最後留下來的是誰？（動畫可驗證）

(A) Susan

(B) Bill

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（std::queue<Task>）。主迴圈每秒一個 tick；工作使用 value semantics，不需要手動 new/delete：

擲骰子決定要不要生新工作，生了就用 emplace 放入 queue（帶上目前秒數當時間戳）。
印表機空閒且 queue 非空：複製 front() 後 pop()，目前秒數減時間戳就是它等了多久。
印表機 tick 一秒：剩餘時間減一，歸零就變空閒。

Task CODE

class Task {
    int timestamp, pages;
  public:
    Task(int time, int pageCount)
        : timestamp(time), pages(pageCount) {}
    int getPages() const { return pages; }
    int waitTime(int now) const {
        return now - timestamp;
    }
};

Printer CODE

class Printer {
    int pageRate;  optional<Task> currentTask;
    double timeRemaining;
  public:
    void tick() {
        if (currentTask) {
            timeRemaining -= 1;
            if (timeRemaining <= 0) currentTask.reset();
        }
    }
    void startNext(const Task& t) {
        currentTask = t;
        timeRemaining = t.getPages() * 60.0 / pageRate;
    }
};

主迴圈 CODE

for (sec = 0; sec < 3600; sec++) {
    if (arrival(rng) == 180)
        printQueue.emplace(sec, pages(rng));
    if (!labPrinter.busy() && !printQueue.empty()) {
        Task next = printQueue.front();  printQueue.pop();
        waitingTimes.push_back(next.waitTime(sec));
        labPrinter.startNext(next);
    }
    labPrinter.tick();
}

印表機設定	平均等待時間（秒）	平均殘留未完成工作數
5 頁/分（高品質）	108.2	1.2
10 頁/分（草稿）	23.7	0.2

結論怎麼讀？講義跑了 10 次 3600 秒：5 頁/分的平均等待起伏很大，動輒將近兩分鐘還常留下未完成的工作； 10 頁/分則穩定壓在半分鐘以內、隊伍清空。等快兩分鐘拿一份報告，學生下一堂課都要遲到了，所以「切高品質」這個提案大概不可行。注意這個結論的效力完全建立在假設上（10 個人、每人每小時印兩次、1 到 20 頁均勻分布）。講義接著丟出三個 what-if，每一個都只要改參數重跑就能回答：

選課人數增加、實驗室平均多 20 個人呢？（到達率 1/180 要重算）
週六沒課，學生不趕時間呢？（同樣的等待時間，結論可能翻盤）
程式越寫越短、平均頁數下降呢？（頁數分布不再是 1 到 20 均勻）

模擬的價值就在這裡：改參數比改現實便宜太多，但模擬的可信度永遠不會超過它的假設。

QUIZ · 模擬的機率設定

為什麼是「每秒以 1/180 的機率生一個工作」？

(A) 每小時 20 件換算成秒就是平均 180 秒一件

(B) 180 是印表機印一頁的秒數

PART 08 · 雙端佇列

Deque 與迴文檢查：兩端都能進出 cppds §3.15–3.18

雙端佇列（deque，唸作 deck）兩端都能加入與移除，一個人就能扮演 stack 或 queue。代價是使用者要自己維持紀律，結構不再幫你防呆。cppds C++ 正文使用 std::deque： push_front/push_back 與 pop_front/pop_back 都是常數時間。課程的 addFront/removeFront API 是作業用補充。

操作	Deque 內容（front 在左）	回傳
d.push_back(4)	[4]	void
d.push_back(7)	[4, 7]	void
d.push_front(2)	[2, 4, 7]	void
d.front()	[2, 4, 7]	2
d.back()	[2, 4, 7]	7
d.pop_front()	[4, 7]	void

課程實作補充：教學版把 front 放在 vector 尾端，所以 addFront／removeFront 是 O(1)，addRear／removeRear 是 O(n)：兩端的成本並不對稱。 STL 的 std::deque 用分段連續的儲存做到兩端都 O(1)，實戰直接用它。

速度

C++ 實作 CODE

// cppds 正文：std::deque 的兩端操作都是 O(1)
std::deque<int> d;
d.push_front(2);
d.push_back(7);
int first = d.front(); d.pop_front();
int last = d.back(); d.pop_back();

迴文檢查 CODE

bool palChecker(const string& text) {
    deque<char> chars(text.begin(), text.end());
    while (chars.size() > 1) {
        char first = chars.front(); chars.pop_front();
        char last = chars.back(); chars.pop_back();
        if (first != last) return false;
    } return true; }

講義 05 · palChecker 的 C++ 全文

#include <iostream>
#include <deque>
#include <string>
using namespace std;
 
bool palChecker(string aString) {
    deque<char> charDeque;
    for (char ch : aString) charDeque.push_back(ch);   // 全部從尾端進
    while (charDeque.size() > 1) {
        char first = charDeque.front(); charDeque.pop_front();
        char last = charDeque.back(); charDeque.pop_back();
        if (first != last) return false;
    }
    return true;
}
 
int main() {
    cout << boolalpha;
    cout << palChecker("lsdkjfskf") << endl;
    cout << palChecker("radar") << endl;
    return 0;
}
 

預期輸出

false
true

palChecker 本體見上方動畫程式碼。while 條件是 size() > 1 而不是 !empty()：剩一個字元（奇數長度的中點）不用比，它自己跟自己一定相等。兩端各取一個、兩邊往中間夾，deque 兩端 O(1) 的能力在這裡剛好用滿。

EXERCISES · 練習

動手驗證：三個經典考點 cppds §3 綜合

EXERCISE 1 · stack 輸出序列

把 1, 2, 3 依序 push 進 stack，途中任何時刻都可以 pop。下列哪個輸出序列不可能出現？

(A) 3 1 2

(B) 2 1 3

EXERCISE 2 · 中序轉後序＋求值

10 + 3 * 5 / ( 16 - 4 ) 的後序是 10 3 5 * 16 4 - / +。用後序求值，答案是？（整數除法）

(A) 11

(B) 11.25

EXERCISE 3 · deque 成本

用「vector 尾端當 front」的 Deque 實作，下列哪組操作都是 O(1)？

(A) addFront 與 removeFront

(B) addRear 與 removeRear

REFERENCE · 總覽

三種線性 ADT 一次比較 cppds §3 總覽

ADT	進	出	紀律	經典應用
Stack	top	top	LIFO	括號配對、進位轉換、undo、呼叫堆疊、DFS
Queue	rear	front	FIFO	排程、模擬（燙手山芋、印表機）、BFS
Deque	兩端	兩端	使用者自律	迴文、滑動視窗、工作竊取排程