3.3 栈和队列的应用
括号匹配、表达式求值（中缀/后缀/前缀）、递归与函数调用栈，以及队列在层次遍历和缓冲区中的应用。
括号匹配
假设表达式中允许包含三种括号：圆括号 ()、方括号 [] 和花括号 {}，其嵌套顺序任意。如何判断括号是否成对且正确嵌套？
观察可以发现：最后出现的左括号最先被匹配——这正是栈的 LIFO 特性。算法思想：
- 初始设置一个空栈，顺序读入括号；
- 若是左括号，压入栈中；
- 若是右括号，则与栈顶的左括号比较：类型匹配则弹出，否则失败；若此时栈已空，说明右括号多余，失败；
- 扫描结束后，若栈不空，说明左括号多余，失败；否则匹配成功。
动画演示栈的应用：括号匹配
C 代码
1bool BracketCheck(char str[], int n) {2 SqStack S; InitStack(S);3 for (int i = 0; i < n; i++) {4 if (str[i] == '(' || str[i] == '[' || str[i] == '{')5 Push(S, str[i]); // 左括号入栈6 else {7 if (StackEmpty(S)) // 右括号单身8 return false;9 char top; Pop(S, top);10 if (str[i] == ')' && top != '(') return false;11 if (str[i] == ']' && top != '[') return false;12 if (str[i] == '}' && top != '{') return false;13 }14 }15 return StackEmpty(S); // 栈空才匹配成功16}
1/15从左到右扫描括号序列，遇到左括号入栈，遇到右括号就与栈顶比较
表达式求值
三种表达式
| 名称 | 运算符位置 | 示例： |
|---|---|---|
| 中缀表达式 | 运算符在两个操作数中间 | (a + b) * c |
| 后缀表达式（逆波兰式） | 运算符在两个操作数后面 | a b + c * |
| 前缀表达式（波兰式） | 运算符在两个操作数前面 | * + a b c |
后缀表达式和前缀表达式不需要括号，运算顺序完全由运算符的位置决定，非常适合计算机处理。
手工转换方法
中缀转后缀的手算方法（以 a + b * (c - d) - e / f 为例）：
- 按运算符优先级给每个运算加上括号：
((a + (b * (c - d))) - (e / f)) - 把每个运算符移到对应括号的后面：
((a (b (c d)-)*)+ (e f)/)- - 去掉所有括号：
a b c d - * + e f / -
移到括号前面则得到前缀表达式：- + a * b - c d / e f。
机算：中缀转后缀
用一个栈保存暂时还不能确定运算顺序的运算符。从左到右扫描：
- 遇到操作数：直接加入后缀表达式；
- 遇到
(：直接入栈；遇到)：依次弹出栈内运算符并加入后缀表达式，直到弹出(为止（括号不加入）； - 遇到运算符：依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，遇到
(或栈空则停止。之后再把当前运算符入栈； - 扫描完后，将栈中剩余运算符依次弹出。
切换到”中缀 → 后缀”模式，观察运算符栈的变化：
动画演示栈的应用：中缀转后缀
算法流程
1// 中缀表达式 → 后缀表达式2for (每个 token t) {3 if (t 是操作数)4 直接加入后缀表达式;5 else if (t == '(')6 入栈;7 else if (t == ')') {8 依次弹出栈中运算符加入后缀表达式,9 直到弹出 '(' 为止; // '(' 不加入10 } else { // t 是运算符11 依次弹出栈中优先级 >= t 的运算符12 加入后缀表达式, 遇到 '(' 或栈空则停止;13 把 t 入栈;14 }15}16栈中剩余运算符依次弹出, 加入后缀表达式;
1/21从左到右扫描中缀表达式，用一个栈暂存运算符
后缀表达式求值
从左到右扫描后缀表达式：遇到操作数就入栈；遇到运算符就弹出两个操作数进行运算，并把结果压回栈。
动画演示栈的应用：后缀表达式求值
算法流程
1// 后缀表达式求值2for (每个 token t) {3 if (t 是操作数)4 Push(S, t);5 else { // t 是运算符6 Pop(S, b); // 先弹出的是右操作数！7 Pop(S, a);8 Push(S, a t b); // 运算结果压回栈9 }10}11栈中唯一的元素即为结果;
1/18从左到右扫描后缀表达式，用一个栈暂存操作数
前缀表达式求值与之类似，只是要从右往左扫描，并且先弹出的是左操作数。
栈与递归
递归是指在一个函数的定义中又调用了它自身。递归模型必须满足两个条件：递归表达式（递归体）和边界条件（递归出口）。
以斐波那契数列为例：
int Fib(int n) {
if (n == 0) return 0; // 边界条件
else if (n == 1) return 1; // 边界条件
else return Fib(n - 1) + Fib(n - 2); // 递归表达式
}在递归调用的过程中，系统为每一层的返回点、局部变量、传入实参等开辟了递归工作栈来进行数据存储。递归次数过多容易造成栈溢出。
- 递归的深度决定了递归工作栈的最大深度，即空间复杂度。
- 可以将递归算法转换为非递归算法，通常需要借助栈来实现（例如二叉树遍历的非递归写法）。
队列的应用
| 应用 | 说明 |
|---|---|
| 树的层次遍历 | 根入队；出队一个结点就把它的孩子依次入队 |
| 图的广度优先遍历 | 与层次遍历类似，见第 6 章 |
| 主机与外设之间的缓冲区 | 解决速度不匹配问题，例如打印数据缓冲区 |
| 多用户争抢 CPU | 操作系统按”先来先服务”组织就绪队列 |
即时练习
即时练习5 题
点击选项即可作答
- 1已知操作符包括 +、−、×、/、( 和 )。将中缀表达式 a + b − a × ((c + d) / e − f) + g 转换为等价的后缀表达式 ab + acd + e / f − × − g + 时，用栈来存放暂时还不能确定运算次序的操作符。若栈初始时为空，则转换过程中同时保存在栈中的操作符的最大个数是（ ）。
- 2后缀表达式 3 4 2 × + 5 − 的值是（ ）。
- 3对于一个问题的递归算法求解和其相对应的非递归算法求解，（ ）。
- 4执行函数时，其局部变量一般采用（ ）进行存储。
- 5下列关于栈和队列的应用，说法错误的是（ ）。
学完了吗？
标记完成后，侧栏会显示进度。进度仅保存在本浏览器中。