返回：0300 数据结构总目录 · 上一章：0303 Chap3 列表 · 下一章：0305 Chap5 二叉树

1、学习目标

栈和队列都是受限线性表。它们的重点不在“能存元素”，而在访问规则：栈是后进先出，队列是先进先出。很多算法看起来复杂，本质上只是利用了这两种访问顺序。

结构 规则 典型应用
栈 LIFO 递归、函数调用、括号匹配、表达式求值、DFS 辅助
队列 FIFO BFS、层次遍历、任务调度、缓冲区

2、资料范围

PDF 课件 内容
04.S_Q.A.stack-ADT_implementation.pdf 栈 ADT 与实现
04.S_Q.B.stack-execution_stack.pdf 函数调用栈
04.S_Q.C1-C5 进制转换、括号匹配、栈混洗、表达式求值、RPN
04.S_Q.D.Queue-ADT_implementation.pdf 队列 ADT 与实现
04.S_Q.E.Queue-App.pdf 队列应用
04.S_Q.X2-X3 八皇后、迷宫回溯

3、栈 ADT

操作 含义
push(e) 入栈
pop() 出栈并返回栈顶
top() 查看栈顶
empty() 判断是否为空
size() 元素个数

栈可以用向量或列表实现。向量实现更简单，尾部入栈/出栈分摊 O(1)。

1
2
3
4
5
6
7
8
9
template <typename T>
class Stack {
    vector<T> data;
public:
    void push(const T& e) { data.push_back(e); }
    T pop() { T e = data.back(); data.pop_back(); return e; }
    T& top() { return data.back(); }
    bool empty() const { return data.empty(); }
};

4、函数调用栈

递归能够运行，是因为每次函数调用都有独立的栈帧，保存参数、局部变量、返回地址等信息。

1
2
3
4
int sum(int n) {
    if (n == 0) return 0;
    return sum(n - 1) + n;
}

当 sum(3) 调用 sum(2) 时，sum(3) 的现场被保留在栈上。等 sum(2) 返回后，程序再回到 sum(3) 继续执行。

递归转迭代，很多时候就是把隐式调用栈改写成显式栈。

5、栈的典型应用

5.1 进制转换

除基取余，余数逆序输出：

1
2
3
4
5
6
7
8
9
10
11
12
string convert(int n, int base) {
    string digits = "0123456789ABCDEF";
    Stack<char> s;
    do {
        s.push(digits[n % base]);
        n /= base;
    } while (n > 0);

    string ans;
    while (!s.empty()) ans += s.pop();
    return ans;
}

5.2 括号匹配

左括号入栈，右括号检查栈顶是否匹配。

1
2
3
4
5
bool match(char l, char r) {
    return (l == '(' && r == ')') ||
           (l == '[' && r == ']') ||
           (l == '{' && r == '}');
}

算法要点：

  1. 右括号出现时，栈不能为空。
  2. 类型必须匹配。
  3. 扫描结束后，栈必须为空。

5.3 栈混洗

栈混洗讨论的是：输入序列 1..n 依次入栈，在任意时刻可以出栈，哪些输出序列可能出现。

判断思路：

1
模拟入栈和出栈过程，如果目标序列无法匹配，则不是合法栈混洗。

经典结论：合法栈混洗数量与 Catalan 数相关。

5.4 表达式求值

中缀表达式求值通常维护两个栈：

栈 内容
操作数栈 数字、中间结果
运算符栈 运算符、括号

处理规则：

  1. 数字直接入操作数栈。
  2. 左括号入运算符栈。
  3. 右括号触发计算直到左括号。
  4. 普通运算符根据优先级决定是否先计算栈顶运算符。

逆波兰表达式则更简单：遇数入栈，遇运算符弹出操作数计算再入栈。

6、队列 ADT

操作 含义
enqueue(e) 入队
dequeue() 出队
front() 查看队首
empty() 判断空
size() 队列规模

顺序循环队列要注意“空”和“满”的区分。常见做法是浪费一个单元：

1
2
empty: front == rear
full : (rear + 1) % capacity == front

链式队列则维护队首和队尾指针。

7、队列应用

7.1 BFS

BFS 的核心是队列：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
queue<int> q;
visited[s] = true;
q.push(s);

while (!q.empty()) {
    int v = q.front();
    q.pop();
    for (int u : adj[v]) {
        if (!visited[u]) {
            visited[u] = true;
            q.push(u);
        }
    }
}

因为队列先进先出，所以 BFS 会按距离从近到远扩展。在无权图中，BFS 可以求源点到各点的最短边数。

7.2 层次遍历

二叉树层次遍历也是队列：

1
2
3
4
5
6
7
8
queue<Node*> q;
q.push(root);
while (!q.empty()) {
    Node* x = q.front(); q.pop();
    visit(x);
    if (x->left) q.push(x->left);
    if (x->right) q.push(x->right);
}

8、栈、队列和递归的关系

问题 常用结构
最近的未完成任务优先 栈
最早等待的任务优先 队列
需要回退尝试 栈或递归
按层扩展 队列
保存函数调用现场 系统栈

9、易错点

易错点 修正
空栈仍 pop/top 操作前检查空
括号匹配只数数量 类型和顺序都要匹配
循环队列满空条件混淆 明确是否浪费一个单元
BFS 入队后才标记太晚 通常入队时就标记，避免重复入队
表达式求值忽略优先级 运算符栈必须比较优先级和结合性

10、复盘清单

检查项 状态
能写出栈 ADT 和队列 ADT 待复盘
能用栈实现进制转换和括号匹配 待复盘
能说明函数调用栈和递归的关系 待复盘
能写出双栈表达式求值框架 待复盘
能用队列写 BFS 和层次遍历 待复盘