栈和队列的应用
表达式种类
前序表达式（Preorder，也叫做波兰表示法）、中序表达式（Infix）和后序表达式（Postorder, 也称为逆波兰表示法）都是二叉树的遍历策略，通常用于算术表达式的表示。不同的表示方法对操作符和操作数的顺序有不同的规定。
| 表达式类型 | 描述 | 示例表达式 | 对应的公式 |
|---|---|---|---|
| 前序 | 操作符位于其操作数之前 | * + A B C | (A + B) * C |
| 中序 | 操作符位于其两个操作数之间，最常见的表示法 | (A + B) * C | (A + B) * C |
| 后序 | 操作符位于其操作数之后 | A B + C * | (A + B) * C |
上图是表达式 (A + B) * C 对应的二叉树，前序、后序表达式分别是对这棵树的 前序遍历和后序遍历。
中序表达式求值
中序表达式求值涉及到两个主要的数据结构：操作符栈与操作数栈。其核心思路是逐个读取中序表达式的字符，根据字符的类型（操作数、操作符、括号）进行不同的处理，最终得到表达式的值。
- 初始化两个栈：
- 操作数栈：用来存储数字。
- 操作符栈：用来存储操作符和左括号。
- 逐个读取中序表达式的字符：
- 如果是 操作数（数字），则直接压入操作数栈。
- 如果是 左括号，则直接压入操作符栈。
- 如果是 右括号，则：
- 从操作符栈中弹出一个操作符。
- 从操作数栈中弹出所需的操作数。
- 执行该操作符对应的运算。
- 将结果压入操作数栈。
- 重复以上步骤，直到从操作符栈中弹出一个左括号。
- 如果是操作符（如
+、-、*、/等）：- 如果操作符栈为空，或栈顶是左括号，或当前操作符优先级高于栈顶操作符的优先级，则直接压入操作符栈。
- 否则：
- 从操作符栈中弹出一个操作符。
- 从操作数栈中弹出所需的操作数。
- 执行该操作符对应的运算。
- 将结果压入操作数栈。
- 重复以上步骤，直到满足上述的压栈条件。
- 处理完所有字符后：
- 如果操作符栈不为空，则：
- 从操作符栈中弹出一个操作符。
- 从操作数栈中弹出所需的操作数。
- 执行该操作符对应的运算。
- 将结果压入操作数栈。
- 重复以上步骤，直到操作符栈为空。
- 如果操作符栈不为空，则：
- 得到结果：
- 此时，操作数栈中仅存一个数字，这就是整个中序表达式的值。
以表达式 3 + (5 * 2 - 8) 说明计算过程：
| 步骤 | 输入字符 | 操作 | 操作符栈 | 数据栈 |
|---|---|---|---|---|
| 1 | 3 | 压入数据栈 | 3 | |
| 2 | + | 压入操作符栈 | + | 3 |
| 3 | ( | 压入操作符栈 | +, ( | 3 |
| 4 | 5 | 压入数据栈 | +, ( | 3, 5 |
| 5 | * | 压入操作符栈 | +, (, * | 3, 5 |
| 6 | 2 | 压入数据栈 | +, (, * | 3, 5, 2 |
| 7 | - | * 比 - 优先级高，* 出栈计算后，将 - 入栈 | +, (, - | 3, 10 |
| 8 | 8 | 压入数据栈 | +, (, - | 3, 10, 8 |
| 9 | ) | 处理到 (之前的所有操作符 | + | 3, 2 |
| 10 | 用 + 运算符计算 | 5 |
后序表达式求值
后序表达式求值主要依赖一个操作数栈。其核心思路是逐个读取后序表达式的元素，并根据元素的类型（操作数或操作符）进行处理。
- 初始化一个操作数栈：
- 用于存储后序表达式中的数字。
- 逐个读取后序表达式的元素：
- 如果是操作数，则直接压入操作数栈。
- 如果是操作符（如+、-、*、/等）：
- 从操作数栈中弹出所需的操作数。注意，因为操作符是后置的，所以先弹出的数字是第二操作数，后弹出的是第一操作数。
- 根据操作符执行相应的运算。
- 将计算结果压入操作数栈。
- 完成后序表达式的读取：
- 操作数栈中的顶部元素即为整个后序表达式的值。
以表达式 3 5 2 * 8 - + 说明计算过程：
| 步骤 | 输入字符 | 操作 | 操作数栈 |
|---|---|---|---|
| 1 | 3 | 压入操作数栈 | 3 |
| 2 | 5 | 压入操作数栈 | 3, 5 |
| 3 | 2 | 压入操作数栈 | 3, 5, 2 |
| 4 | * | 弹出两个操作数并相乘，结果压入操作数栈 | 3, 10 |
| 5 | 8 | 压入操作数栈 | 3, 10, 8 |
| 6 | - | 弹出两个操作数并相减，结果压入操作数栈 | 3, 2 |
| 7 | + | 弹出两个操作数并相加，结果压入操作数栈 | 5 |
中序转后序
将中缀表达式转换为后缀表达式的算法思想如下：
初始化一个操作符栈，从左向右开始扫描中缀表达式；
- 遇到数字时，加入后缀表达式；
- 遇到运算符时：
- 若为
（，入栈； - 若为
），则依次把栈中的运算符加入后缀表达式中，直到出现（，从栈中删除（； - 若为除括号外的其他运算符
- 当其优先级高于除
（以外的栈顶运算符时，直接入栈； - 否则从栈顶开始，依次弹出比当前处理的运算符优先级高和优先级相等的运算符，直到一个比它优先级低的或者遇到了一个左括号为止。
- 当其优先级高于除
- 若为
以中序表达式 a/b+(c*d-e*f)/g 为例，可以通过如下步骤将其转换为后续表达式：
| 待处理序列 | 栈 | 后缀表达式 | 当前扫描元素 | 动作 |
|---|---|---|---|---|
a/b+(c*d-e*f)/g | a | a 加入后缀表达式 | ||
/b+(c*d-e*t)/g | a | / | ／ 入栈 | |
b+(c*d-e*f)/g | / | a | b | b 加入后缀表达式 |
+(c*d-e*f)/g | / | ab | + | ＋ 优先级低千栈顶的 /, 弹出 ／ |
+(c*d-e*f)/g | ab/ | + | ＋入栈 | |
(c*d-e*f)/g | + | ab/ | ( | （入栈 |
c*d-e*f)/g | +( | ab/ | c | c 加入后缀表达式 |
*d-e*f)/g | +( | ab/c | * | 栈顶为 (，＊入栈 |
d-e*t)/g | +(* | ab/c | d | d 加入后缀表达式 |
-e*f)/g | +(* | ab/cd | - | - 先级低于栈顶的 *，弹出 * |
-e*f)/g | +( | ab/cd* | - | 栈顶为 (，－入栈 |
e*t)/g | +(- | ab/cd* | e | e 加入后缀表达式 |
*f)/g | ＋(- | ab/cd*e | ＊ | ＊ 优先级高于栈顶的 －， ＊ 入栈 |
f)/g | +(-* | ab/cd*e | f | f加入后缀表达式 |
)/g | +(-* | ab/cd*ef | ） | 把栈中 ( 之前的符号加入表达式 |
/g | ＋ | ab/cd*ef*- | / | / 优先级高于栈顶的 +, / 入栈 |
g | +/ | ab/cd*ef*- | g | g 加入后缀表达式 |
+/ | ab/cd*ef*-g | 扫描完毕，运算符依次退栈加入表达式 | ||
ab/cd*ef*-g/+ | 完成 |
入栈出栈序列
入栈出栈是常考的问题，这类问题的核心可以被总结为以下两种范式：
- 给定一个入栈序列，判断哪些出栈序列是不可能的？
- 给定一个入栈序列，其出栈序列序列有多少种？
这里给出这两个常见问题的解答。
不可能的出栈序列
给定一个入栈序列，其出栈序列可能有很多种，因为一个元素的出栈时间比较灵活，比如它可以一入栈马上出栈，也可以等一会再出栈。要辨别不可能的出栈系列，需要抓住关键规则：只有栈顶元素能够最先出栈。
也就是说，对于下图这种情况，A 被 B 压住了，在出栈序列中，A 一定在 B 的后面。如果某个出栈序列中 A 在 B 的前面，则这种出栈序列是不可能出现的。
卡特兰数
假设有 $n$ 个不同元素（例如 $1,2,\cdots,n$），按某种顺序依次入栈，并且可以在任意时刻出栈，每个元素恰好入栈一次且出栈一次，求所有可能的出栈序列数。
这个问题可以用卡特兰数计算，首先给出卡特兰数的公式：
$$C_{n} = \frac{1}{n+1}\begin{pmatrix}2n \\ n\end{pmatrix}$$
这也是上述问题的答案，接下来解释一下为什么是卡特兰数：
我们将入栈操作记作 +1，出栈操作记作 -1，整个过程中有 $n$ 次入栈，$n$ 次出栈，总共有 $2n$ 个操作。我们要保证以下条件：
在任何时刻，入栈次数不得超过出栈次数。
这种操作方式正好对应于卡特兰数的关键特征，所以 $n$ 个入栈元素对应可能的出栈序列总数就是 $C_{n}$。
除了入栈出栈序列之外，卡特兰数也常常出现在以下场景中，这些问题与入栈出栈序列是等价的：
- 二叉树的计数：给定 $n$ 个不同节点，构造不同形态的二叉树个数为 $C_{n}$。
- 括号匹配：$n$ 对括号的合法匹配序列数为 $C_{n}$。例如，$n=2$ 时，合法序列为
()()和(())。