Lecture 2: 栈与队列（Stacks & Queues：LIFO/FIFO 与 ADT 客户端视角）（对应课程真实讲座 L05）

目录 · ← l1 · l3 →

Lecture 2: 栈与队列（Stacks & Queues：LIFO/FIFO 与 ADT 客户端视角）（对应课程真实讲座 L05）

概述

本讲介绍两种最简单的“有序容器”：栈（stack）与队列（queue）。它们不提供任意位置读写，只各开一个口子，却因此换来了极简、极快的操作，并能优雅地解决反转、配对、任务排队等一大批问题。本讲延续“客户端视角”：只关心“能做什么、语义是什么”，暂不深究内部实现；同时会用容器按引用传递、取模运算符 %、break 语句等配套语法，并完整实现一个经典应用——后缀表达式（postfix）求值。 对应官方 L05（6/29，Stacks and Queues）一讲；官方还随讲附赠 StackViz / QueueViz 两个可视化小程序帮助直观感受进出顺序。

核心概念与算法原理

1. ADT 的“客户端视角”（Client-Side Approach）

问题定义：学了 Vector/Grid 之后，如何又快又稳地搭建新工具，而不必先懂内部实现？ 直观解释：课程采取“先当用户、后当制造者”的策略：先学会使用 ADT（调用它的操作、相信它的语义），实现细节（数组？链表？）留到讲完指针与动态内存之后再揭开。官方在 L04 与 L05 反复强调这一点：作为客户端，我们享受的是“契约”——只要按文档调用，内部怎么折腾我们不必操心。 步骤分解：使用一个 ADT 的标准流程 = ① 决定需要什么语义（后进先出还是先进先出）→ ② 选对容器（Stack 或 Queue）→ ③ 只通过其公开操作读写（不越权访问内部）→ ④ 按文档假设复杂度与行为。官方用 StackViz/QueueViz 动画直观演示入栈出栈、入队出队的每一步，建议下载摆弄一遍。

2. Stack：LIFO，后进先出

问题定义：有些任务要求“最后放进去的最先被处理”——比如撤销、后退。 直观解释：栈像一摞盘子：你永远只能从最上面取放（官方 L05 称其为 LIFO：last-in, first-out）。它只开一个口（栈顶 top），开口少反而让它行为确定、几乎不可能误操作。 操作/步骤分解（官方 Stack 与 std::stack 对照）：

栈的抽象视图(只从顶部进出):
        ┌─────┐
        │ 12  │ ← top: peek/pop 都在这
        ├─────┤
        │ 15  │
        ├─────┤
        │ 20  │
        ├─────┤
        │ 10  │ ← 最先 push 的,沉在最底
        └─────┘
 push(7) → 7 落在 12 之上; pop() → 移走 12

注意：C++ 标准库的 stack::pop() 返回值是 void——必须先 top() 看一眼再 pop() 移走，两步完成“取出”。官方 Stanford 的 pop() 一步到位返回元素，这是两者最易踩的差异。 现实应用（官方列举）：① 反转任何序列（后进先出天然倒序）；② 程序本身的“调用栈 call stack”记录函数调用顺序与返回地址；③ 浏览器“后退”按钮按访问历史回退；④ 文本编辑器撤销（undo）操作栈。官方还预告：图论里的深度优先搜索（DFS）本质上也能用栈实现，课程后段会再见面。

3. Queue：FIFO，先进先出

问题定义：另一些任务讲究“先来先服务”的公平排队。 直观解释：队列像排队买票：新来的排到队尾，服务完的从队首离开——FIFO（first-in, first-out）。只开两个口：队首（front，出）与队尾（back，入）。 操作/步骤分解：

队列的抽象视图(队尾进,队首出):
  enqueue(7)                     dequeue()
      │                              │
      ▼                              ▼
[ 尾 ] [ 4 ][ 3 ][ 2 ][ 1 ] [ 首 ] → 移走 1,其余前移

现实应用：打印店的打印任务队列、演唱会购票排队、游戏登录排队、LaIR 答疑排队（官方 L05 全数点名）；图论中的广度优先搜索（BFS）用队列逐层扩散。广度式处理的通用模式是：先把“起点/初始任务”入队，然后循环“出队一个 → 处理 → 把它的后继任务入队”，直到队列空。 清空/遍历的标准句式：队列没有下标、不能用 range-for（std 的 stack/queue 都是“只露一头的适配器”），想遍历就只能一边出队一边处理：while (!q.empty()) { 处理 q.front(); q.pop(); }。官方 L05 特意演示了错误写法 for (int i = 0; i < q.size(); i++)——每出队一次 size 就变小，循环会提前结束，只处理掉一半任务。

4. 配套工具：容器按引用传递、%、break

问题定义：写操作这些容器的函数时，有什么约定俗成的规矩？

• 容器一律按引用传：队列/栈可能装大量数据，按值传等于整份拷贝（时间 O(n)、内存翻倍）；写 void f(queue<int>& q) 只建立 O(1) 的“纽带”。即使函数不打算改动容器，也应写 const queue<int>& 以省拷贝（官方 L05 把它列为“top take-away”）。
• 取模 %：返回整除的余数：17 % 3 == 2（17÷3=5 余 2），5 % 2 == 1。高频用途：奇偶判断（x % 2）、每 N 次做某事（次数 % N == 0）、环形下标前进 (i + 1) % n。
• break：立即跳出当前所在的那一层循环，跳到循环后第一行继续。常配合 while (true) 做“满足条件就收手”的中断。
• range-for 与输出流：std 的 stack/queue 不能 range-for、也不能直接 cout << s（官方 Stanford 版支持打印与 == 比较，这是课程库的贴心之处）；本笔记统一用“边出边处理”的方式展示内容。

5. 用 Vector 充当 Stack——抽象的力量

问题定义：栈和 vector 有什么关系？为什么有了 vector 还要 Stack？ 直观解释：官方 L05 演示：push/pop 完全可以用 vector 的“末尾增删”模拟——v.push_back(x) 当 push、v.pop_back() 当 pop。但两者不可同日而语：写 stack 版本时语义一眼可见、无下标可算、几乎不可能出错；写 vector 版本要自己小心“该从哪头删”，一不留神就出界或删错端。这就是抽象的价值：把“只能从顶部操作”的约束内建进类型，错误在编译与设计层面就被挡掉了。std::vector 提供 push_back/pop_back/back() 恰好可作此用，而 std::stack 则把这一约束固化成了专用类型。

6. 经典应用：后缀表达式（postfix）求值

问题定义：人习惯中缀（infix）写法 3 + 5 * 2，但解析它要处理优先级与括号、多次扫描；如何让程序一次从左到右扫完就算出结果？ 直观解释：后缀表达式（也叫逆波兰记法 RPN）把运算符放到两个操作数之后：3 5 2 * + 表示“3 与 (5×2) 相加”。它完全不需要括号和优先级规则，天然适合计算机从左到右单遍处理（官方 L05 补充说明里完整推导过）。谁在帮我们算？ 一台只认得“数就压、符就取二合一”的栈机器。 步骤分解（算法）：准备一个空栈；从左到右读每个 token：

1. 读到数字 → 压栈；
2. 读到运算符（+ - * /）→ 先 pop 出右操作数，再 pop 出左操作数（顺序关键！减法和除法左右颠倒结果就错），算完把结果压回栈；
3. 全部读完 → 栈顶唯一剩下的数字就是答案。

走查 3 5 2 * + 12 2 3 * / -（对应中缀 3 + 5*2 − 12/(2*3)）：

token   动作               栈(自底向上)
3       数字,压栈           [3]
5       数字,压栈           [3,5]
2       数字,压栈           [3,5,2]
*       取 5*2=10,压栈      [3,10]
+       取 3+10=13,压栈     [13]
12      数字,压栈           [13,12]
2       数字,压栈           [13,12,2]
3       数字,压栈           [13,12,2,3]
*       取 2*3=6,压栈       [13,12,6]
/       取 12/6=2,压栈      [13,2]
-       取 13-2=11,压栈     [11]
结束    pop → 答案 11

健壮性检查：非法表达式会露出马脚——运算符出现时栈里不足 2 个数（操作数不够）、除数为 0、token 既非数字也非运算符、结束时栈里不是恰好 1 个数（说明多/少了操作数）。一个完整的 processPostfix 实现见下方示例 3，返回 bool 表示成功与否，失败时保持结果参数原值。

代码示例与实现详解

示例 1：用 std::stack 反转字符串 + 模拟浏览器“后退”（含 break）

// 文件: stack_demo.cpp
// 演示: push/top/pop、清空栈的 while 句式、LIFO 反转、“后退”应用与 break
#include <iostream>
#include <stack>
#include <string>
using namespace std;

// 用栈反转字符串: 后进先出 = 天然倒序
string reverseViaStack(const string& text)
{
    stack<char> s;
    for (char ch : text) {
        s.push(ch);              // 逐个压栈
    }
    string out;
    while (!s.empty()) {         // 清空栈的标准句式
        out += s.top();          // 先 top() 看一眼栈顶
        s.pop();                 // 再 pop() 移走(标准库 pop 不返回值!)
    }
    return out;
}

int main()
{
    string word = "stressed";
    cout << "stressed 反转: " << reverseViaStack(word) << endl;  // desserts

    // 浏览器“后退”按钮: 历史记录就是一个栈,越新访问的越先被退回
    stack<string> history;
    history.push("首页");
    history.push("课程主页");
    history.push("L05 讲义页");

    cout << "开始点击后退…" << endl;
    while (!history.empty()) {
        string current = history.top();   // 当前停在哪一页
        history.pop();                    // 后退 = 弹出当前页
        cout << "离开: " << current << endl;
        if (current == "课程主页") {       // 回到课程主页就收手
            cout << "已回到课程主页,停止回退。" << endl;
            break;                        // break: 跳出最近的 while
        }
    }
    return 0;
}

【代码做什么】：reverseViaStack 把 “stressed” 每个字符压栈再全部弹出，得到 “desserts”——LIFO 的反转威力一目了然；main 里用 stack<string> 存放访问历史，模拟浏览器后退：循环里“看栈顶 → pop 离开该页”，一旦弹出的是 “课程主页” 就 break 退出循环。

【实现机制解说】：栈的操作全在“顶”上发生，因此每个操作都是 O(1)。s.pop() 不返回被移除的元素是 C++ 标准库与官方 Stanford 版最大的差异：官方 Stack::pop() 直接返回栈顶，而 std 版必须 top() + pop() 两步走——若直接 s.pop() 后想用返回值，会拿到垃圾甚至编译错误。break 只作用于它所在的最近一层循环：本例它在 while 内部，因此触发后直接跳到循环右花括号之后。注意 while (!s.empty()) 是“排空容器”的通用句式：任何循环里若一边遍历一边改变容器大小，千万别把 s.empty() 换成循环次数上限之类的固定值——那正是官方 L05 演示的队列遍历翻车点。

示例 2：用 std::queue 模拟打印任务队列（FIFO + % + 引用传递）

// 文件: queue_demo.cpp
// 演示: push/front/pop、FIFO 打印队列、% 运算符、容器按引用传递
#include <iostream>
#include <queue>
#include <string>
using namespace std;

// 处理整个打印队列。参数必须是引用: 传值会把整支队伍拷贝一份(费时费内存)
void runPrinter(queue<int>& jobs)
{
    int done = 0;
    while (!jobs.empty()) {           // 边出队边处理,直到队列空
        int job = jobs.front();       // peek: 看队首(最早提交的任务)
        jobs.pop();                   // dequeue: 移走队首
        done++;
        cout << "打印完成: 任务 #" << job << endl;
        if (done % 3 == 0) {          // % 取模: 每完成 3 个汇报一次
            cout << "   —— 已累计完成 " << done << " 个任务" << endl;
        }
    }
    cout << "队列已空,打印机待机。" << endl;
}

int main()
{
    queue<int> printer;               // 打印任务按提交顺序排队(FIFO)
    for (int job = 1; job <= 6; job++) {
        printer.push(job);            // enqueue: 依次进队尾
    }
    cout << "队首(最先打印)任务: #" << printer.front() << endl;  // 1
    cout << "队尾任务: #" << printer.back() << endl;             // 6

    runPrinter(printer);              // 先进先出: 1,2,3,4,5,6

    // % 的另两个常见用法: 奇偶判断 与 环形下标
    for (int i = 1; i <= 5; i++) {
        if (i % 2 == 0) cout << i << " 是偶数, ";
    }
    cout << endl;
    cout << "环形下标: 6 个槽(编号 0..5)里, 槽 5 的下一个是槽 "
         << (5 + 1) % 6 << "  ← 公式 (i+1) % 总槽数" << endl;
    return 0;
}

【代码做什么】：任务 1..6 按序入队，front()/back() 分别展示队首队尾，随后 runPrinter 用“看队首 → pop”的句式按 FIFO 顺序打印全部任务（输出 1 到 6，证明先来先服务），并用 done % 3 == 0 每三个任务汇报一次进度；结尾顺带展示 % 的奇偶判断与环形下标两种常见用法。

【实现机制解说】：runPrinter(queue<int>& jobs) 用引用而非值——若写 queue<int> jobs，函数入口就要把整支队伍逐元素拷贝（O(n) 时间 + 双倍内存），函数里清空的也只是一份副本，调用方的队列原封不动。这是官方 L05 反复强调的规矩：容器进函数一律走引用；不打算改就加 const。打印顺序 1→6 恰好验证 FIFO：push 全在队尾、pop 全在队首，新任务永远不可能插队。% 的实质是“整除的余数”，done % 3 == 0 在 done=3、6 时为真——“每 N 次触发一次”是它的招牌用法；环形下标 (i+1) % n 让下标在 0..n-1 间循环打转，是轮询调度（round-robin）的基础。

示例 3：后缀表达式求值器（完整健壮版）

// 文件: postfix_demo.cpp
// 演示: 用 std::stack 单遍求值后缀表达式,含非法输入检测
#include <iostream>
#include <sstream>   // istringstream: 按空白切分字符串
#include <stack>
#include <string>
using namespace std;

// 求值后缀表达式 expr; 成功返回 true 并把答案写进 result;
// 失败(非法表达式/除零)返回 false 且 result 保持原值不变。
bool processPostfix(const string& expr, int& result)
{
    stack<int> s;
    istringstream iss(expr);
    string token;
    while (iss >> token) {                       // 逐个取 token(按空格切)
        if (token == "+" || token == "-" ||
            token == "*" || token == "/") {
            if (s.size() < 2) return false;      // 操作数不够 → 非法
            int rhs = s.top(); s.pop();          // 先弹出的是右操作数!
            int lhs = s.top(); s.pop();          // 再弹出的是左操作数
            if (token == "+")      s.push(lhs + rhs);
            else if (token == "-") s.push(lhs - rhs);
            else if (token == "*") s.push(lhs * rhs);
            else {                               // 除法: 防除零
                if (rhs == 0) return false;
                s.push(lhs / rhs);
            }
        } else {                                 // 既非四则符 → 尝试当整数
            try {
                s.push(stoi(token));
            } catch (...) {
                return false;                    // 既非运算符又非整数 → 非法
            }
        }
    }
    if (s.size() != 1) return false;             // 栈应恰好只剩最终答案
    result = s.top();
    return true;
}

int main()
{
    const string exprs[] = {
        "3 5 2 * + 12 2 3 * / -",   // 等价于 3+5*2-12/(2*3) = 11
        "5 10 +",                   // 15
        "10 12 + 5 -",              // 17
        "2 3 + 4 5 + *",            // 45
        "5 10 + +",                 // 非法: 第二个 + 缺操作数
        "10 + 20",                  // 非法: 开头两个数没到就先遇运算符
        "4 0 /",                    // 非法: 除零
        "3 x 2 +",                  // 非法: x 不是数字也不是运算符
        ""                          // 非法: 空串
    };
    for (const string& e : exprs) {
        int result = 0;                            // 每次重置,便于观察“失败不改值”
        if (processPostfix(e, result)) {
            cout << "\"" << e << "\" = " << result << endl;
        } else {
            cout << "\"" << e << "\" → 非法表达式(结果仍为 " << result << ")" << endl;
        }
    }
    return 0;
}

【代码做什么】：processPostfix 从左到右单遍扫描：数字压栈，运算符则弹两个操作数（先弹右、后弹左）计算后压回；结束时若栈里恰好剩一个数即为答案。main 用 9 个用例覆盖：4 个合法表达式（含官方 L05 的经典式 3 5 2 * + 12 2 3 * / - = 11）与 5 类非法输入（缺操作数、数字不足、除零、乱 token、空串）。

【实现机制解说】：算法成立的关键是栈暂存子结果：遇到运算符时，栈顶两个数正是它该吃的“最近两个数”，算完压回后它们以单个结果的身份继续参与外层运算——这恰好是表达式树的后序遍历求值，因此无需括号与优先级。弹栈顺序必须“先右后左”：- 与 / 不满足交换律，10 12 + 5 - 若先弹左会算出 7 而非 17。istringstream >> token 自动按任意空白切词，比手写 split 简洁。错误处理走“早退原则”：任一环节发现非法立即 return false，且绝不动 result——官方练习强调用“失败不改参数”来测试，防止调用者误以为失败会写入哨兵值。该函数与官方 L05 课后练习 bool processPostfix(string expr, int& result) 同款签名，这里用纯标准库实现。

复杂度分析

要点：栈与队列把“能做的事”刻意收窄，换来的是所有核心操作都是 O(1)，且语义无歧义、几乎不可能误用。std 默认用 deque 兜底（stack 也可指定 vector），两种底层都不影响客户端看到的复杂度。

关键要点

• 栈是 LIFO：只能碰栈顶，push 进去、pop 出来，天然反转一切“后来居上”的序列。
• 队列是 FIFO：队尾进、队首出，“先来先服务”，是公平排队的代名词。
• 清空/遍历栈与队列只有一种标准句式：while (!空) { 取顶/首; 弹出; }，绝不要用固定循环次数。
• 容器进出函数一律传引用（不修改就 const &），按值传等于白拷一份 O(n) 的数据。
• 后缀表达式求值 = “数字压栈、运算符取二合一”的栈机器，单遍扫描即可，先弹右操作数再弹左操作数。

常见陷阱与注意事项

• std::stack::pop() 不返回元素：直接 int x = s.pop(); 编译报错。规避：先 top() 取值再 pop()。
• 循环条件随出队变小：for (i = 0; i < q.size(); i++) { q.pop(); } 只处理一半。规避：一律 while (!q.empty())。
• 空容器上操作：对空栈 top()/pop()、空队列 front()/pop() 是未定义行为，可能崩溃。规避：操作前先判空。
• 弹栈顺序弄反：后缀求值里 -、/ 先弹右操作数，反了结果错。规避：把“先弹右、后弹左”写进注释并自测减法/除法用例。
• 按值传容器：void f(queue<int> q) 隐式整队拷贝。规避：写成 queue<int>& 或 const queue<int>&。
• 误以为栈/队列可随机访问或可 range-for：下标、迭代器一概没有。规避：想“翻看”全部内容就先想清楚是否需要排队/栈语义，或改用 vector。
• % 与 / 混淆：17 % 3 是余数 2，17 / 3 是商 5。规避：默念“% 是取余”。

思考题（带答案）

问题 1：依次 push(1), push(2), pop(), push(3), pop(), pop() 后栈为空。问每次 pop() 各返回什么？若换成队列（push 当 enqueue、pop 当 dequeue）结果又如何？ 答案：栈是 LIFO，三次 pop 依次返回 2、3、1（每次 pop 的都是当时的栈顶）。队列是 FIFO，三次 pop 依次返回 1、2、3（每次 pop 的都是最早的队首）。同一组操作、两种容器、完全相反的输出顺序——这正是 LIFO 与 FIFO 语义差异的最佳记忆点。

问题 2：为什么官方 L05 说“用 vector 也能当栈用，但我们还是推荐 Stack”？举一个用 vector 模拟栈时容易犯的错。 答案：vector 的 push_back/pop_back 确实能模拟栈，但 vector 同时暴露了下标、insert、erase 等“多余能力”，使用者要时刻自律“只能动尾巴”，容易下标算错、从错误的端删除、甚至越界。Stack 把“只能从顶部进出”固化为类型约束，犯错空间被设计层面抹掉——这就是抽象的力量：用更受限的接口换更低的出错率。

问题 3：给出后缀式 2 3 4 * + 5 + 的求值过程（写出每一步后的栈）。 答案：2 压栈 [2]；3 压栈 [2,3]；4 压栈 [2,3,4]；* 取 3×4=12 压回 [2,12]；+ 取 2+12=14 压回 [14]；5 压栈 [14,5]；+ 取 14+5=19 压回 [19]；结束，答案 19。（可对照官方 L05 练习用例 "2 3 4 * + 5 +" == 19。）