栈和队列的应用

🔥 高优先级

本节的几个知识点经常在选择题考察：中序表达式求值、中序转后序、后序表达式求值、入栈出栈序列。

二叉表达式树

二叉表达式树 是一种特殊的二叉树，用于表示算术或逻辑表达式。它的每个 叶子节点 通常存放 操作数 （operand，如数字或变量），每个 非叶子节点 存放 操作符 （operator，如 +, -, *, /）。

ExpressionTreen1/n2*n1->n2n37n1->n3n4+n2->n4n5-n2->n5n63n4->n6n74n4->n7n85n5->n8n92n5->n9

表达式种类

前序表达式（Preorder，波兰表示法）、中序表达式（Infix）和后序表达式（Postorder，逆波兰表示法）是根据二叉表达式树的不同遍历方式得到的表达式结果。具体来说：

• 前序表达式：前序遍历 得到的序列。
• 中序表达式：中序遍历 得到的序列。
• 后序表达式：后序遍历 得到的序列。

这三种表达式的 操作符 和 操作数 间的相对位置有所不同：

中序表达式求值

中序表达式求值涉及到两个主要的数据结构：操作符栈 与 操作数栈 。其核心思路是逐个读取中序表达式的字符，根据字符的类型（操作数 、操作符 、括号 ）进行不同的处理，最终得到表达式的值。

1. 初始化两个栈 ：

• 操作数栈 ：用来存储数字。
• 操作符栈 ：用来存储操作符和左括号。

2. 逐个读取中序表达式的字符 ：

• 如果是 操作数 （数字），则直接压入 操作数栈 。
• 如果是 左括号 ，则直接压入 操作符栈 。
• 如果是 右括号 ，则：
  • 从 操作符栈 中弹出一个操作符。
  • 从 操作数栈 中弹出所需的操作数。
  • 执行该操作符对应的运算。
  • 将结果压入 操作数栈 。
  • 重复以上步骤，直到从 操作符栈 中弹出一个左括号。
• 如果是操作符 （如+、-、*、/等）：
  • 如果 操作符栈 为空，或栈顶是左括号，或当前操作符 优先级 高于栈顶操作符的 优先级 ，则直接压入 操作符栈 。
  • 否则：
    • 从 操作符栈 中弹出一个操作符。
    • 从 操作数栈 中弹出所需的操作数。
    • 执行该操作符对应的运算。
    • 将结果压入 操作数栈 。
    • 重复以上步骤，直到满足上述的压栈条件。

3. 处理完所有字符后 ：

• 如果 操作符栈 不为空，则：

  • 从 操作符栈 中弹出一个操作符。
  • 从 操作数栈 中弹出所需的操作数。
  • 执行该操作符对应的运算。
  • 将结果压入 操作数栈 。
  • 重复以上步骤，直到 操作符栈 为空。
  4. 得到结果 ：

• 此时，操作数栈 中仅存一个数字，这就是整个中序表达式的值。

中序表达式求值的过程可以参照以下流程图进行理解：

以表达式 3 + (5 * 2 - 8) 说明计算过程：

后序表达式求值

后序表达式求值主要依赖一个 操作数栈 。其核心思路是逐个读取后序表达式的元素，并根据元素的类型（操作数 或操作符 ）进行处理。

1. 初始化一个操作数栈**** ：

• 用于存储后序表达式中的数字。

  2. 逐个读取后序表达式的元素 ：

• 如果是操作数 ，则直接压入 操作数栈 。

• 如果是操作符 （如+、-、*、/等）：

  • 从 操作数栈 中弹出所需的操作数。注意，因为操作符是后置的，所以先弹出的数字是第二操作数，后弹出的是第一操作数。
  • 根据操作符执行相应的运算。
  • 将计算结果压入 操作数栈 。

3. 完成后序表达式的读取 ：

• 操作数栈 中的顶部元素即为整个后序表达式的值。

后序表达式求值的过程可以参照以下流程图进行理解：

flowchart TD
A[开始: 初始化操作数栈] --> B[读取后序表达式的下一个元素]

B --> C{是否还有元素?}
C -->|否| H[栈顶元素即为最终结果]
H --> I[结束]

C -->|是| D{当前元素类型?}

D -->|操作数| E[将操作数压入栈中]
E --> B

D -->|操作符| F[从栈中弹出两个操作数<br/>注意: 先弹出的是第二操作数<br/>后弹出的是第一操作数]
F --> G[执行运算并将结果压入栈中]
G --> B

style A fill:#e1f5fe
style I fill:#c8e6c9
style D fill:#fff3e0
style E fill:#f3e5f5
style F fill:#ffebee
style G fill:#ffebee
style H fill:#e8f5e8

以表达式 3 5 2 * 8 - + 说明计算过程：

中序转后序

将中缀表达式转换为后缀表达式的算法思想如下：

初始化一个 操作符栈 ，从左向右开始扫描中缀表达式；

• 遇到数字时，加入后缀表达式；
• 遇到运算符时：
• 若为 （，入栈；
• 若为 ），则依次把栈中的运算符加入后缀表达式中，直到出现 （，从栈中删除 （；
• 若为除括号外的其他运算符
  • 当其 优先级 高于除 （ 以外的栈顶运算符时，直接入栈；
  • 否则从栈顶开始，依次弹出 优先级 高于或等于当前运算符的运算符，直到遇到 优先级 更低的运算符或左括号为止。

中序转后序的过程可以参照以下流程图进行理解：

flowchart TD
A[开始：初始化操作符栈] --> B[从左向右扫描中缀表达式]
B --> C{读取下一个字符}

C -->|数字| D[直接添加到后缀表达式]
C -->|左括号| E[直接入栈]
C -->|右括号| F[弹出栈中运算符到后缀表达式]
C -->|运算符| G{当前运算符优先级 > 栈顶运算符优先级?}

D --> H{是否扫描完成?}
E --> H

F --> I{栈顶是否为左括号?}
I -->|否| F
I -->|是| J[弹出左括号但不加入后缀表达式]
J --> H

G -->|是| K[直接入栈]
G -->|否| L[弹出栈顶运算符到后缀表达式]
L --> M{栈空或栈顶为左括号或优先级更低?}
M -->|否| L
M -->|是| N[当前运算符入栈]

K --> H
N --> H

H -->|否| C
H -->|是| O[弹出栈中所有剩余运算符]
O --> P[结束：得到后缀表达式]

以中序表达式 a/b+(c*d-e*f)/g 为例，可以通过如下步骤将其转换为后续表达式：

入栈出栈序列

入栈出栈是常考的问题，这类问题的核心可以被总结为以下两种范式：

• 给定一个入栈序列，判断哪些出栈序列是不可能的？
• 给定一个入栈序列，其出栈序列序列有多少种？

这里给出这两个常见问题的解答。

不可能的出栈序列

给定一个入栈序列，其出栈序列可能有很多种，因为一个元素的出栈时间比较灵活，比如它可以一入栈马上出栈，也可以等一会再出栈。要辨别不可能的出栈系列，需要 抓住关键规则 ：只有 栈顶元素 能够最先出栈。

也就是说，对于下图这种情况，A 被 B 压住了，在出栈序列中，A 一定在 B 的后面。如果某个出栈序列中 A 在 B 的前面，则这种出栈序列是不可能出现的。

出栈序列： • • • B A • • •

A 一定在 B 之后出栈

卡特兰数

考虑这样一个问题：有 n 个不同的元素（例如 1,2,⋯,n ），我们按照某种顺序依次将它们 入栈 ，并且在任意时刻可以选择 出栈 。每个元素都必须恰好入栈一次、出栈一次。我们想知道，所有可能的出栈序列共有多少种。

这个问题的答案可以用 卡特兰数（Catalan number） 来表示。卡特兰数的公式如下：

Cn​=n+11​(n2n​)

也就是说，上述问题中 \(n\) 个元素的所有可能出栈序列数量就是 \(C_n\)。

那么为什么入栈出栈序列总数可以用卡特兰数来表示呢？

我们可以把每一次操作用数字表示：

• 入栈 ：记作 +1
• 出栈 ：记作 -1

整个过程总共有 \(2n\) 次操作，其中有 \(n\) 次入栈，\(n\) 次出栈。为了保证操作合法（不能在栈为空时出栈），必须满足：在任意时刻，出栈次数 不能超过 入栈次数。

这恰好 与卡特兰数的经典定义相对应 ：卡特兰数计数的就是符合类似限制的序列数量。因此，入栈出栈序列数量正好是 \(C_n\)。

卡特兰数不仅出现在入栈出栈序列中，还常 出现在很多等价问题中 ，例如：

1. 二叉树计数 给定 \(n\) 个不同节点，可以构造的不同形态二叉树的数量为 \(C_n\)。

2. 括号匹配 \(n\) 对括号的合法匹配序列数量也为 \(C_n\)。 例如，当 \(n=2\) 时，合法的序列有：

     ()()   (())

相关笔记

• 线性表定义与基本操作
• 线性表概述
• 链表
• 顺序表