栈和队列的应用

🔥 高优先级
真题练习
本节的几个知识点经常在选择题考察:中序表达式求值、中序转后序、后序表达式求值、入栈出栈序列。

二叉表达式树

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

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

表达式种类

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

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

表达式类型描述示例表达式对应的公式
前序操作符位于其操作数之前* + A B C(A + B) * C
中序操作符位于其两个操作数之间,最常见的表示法(A + B) * C(A + B) * C
后序操作符位于其操作数之后A B + C *(A + B) * C
ExpressionTypestitle表达式种类(Expression Types)tree_title二叉表达式树title->tree_titletree_example     *   /   \  +     C / \A   Btree_title->tree_examplepreorder前序遍历(Preorder)tree_example->preorder前序遍历inorder中序遍历(Inorder)tree_example->inorder中序遍历postorder后序遍历(Postorder)tree_example->postorder后序遍历prefix前序表达式(波兰表示法)操作符在操作数之前preorder->prefix得到infix中序表达式(普通表示法)操作符在操作数之间inorder->infix得到postfix后序表达式(逆波兰表示法)操作符在操作数之后postorder->postfix得到prefix_example* + A B Cprefix->prefix_exampleprefix_features特点:• 无需括号• 从左到右求值• 操作符优先prefix->prefix_featuresinfix_example(A + B) * Cinfix->infix_exampleinfix_features特点:• 需要括号• 符合人类习惯• 最常见形式infix->infix_featurespostfix_exampleA B + C *postfix->postfix_examplepostfix_features特点:• 无需括号• 便于计算机处理• 栈式求值postfix->postfix_featuresprefix_app应用:• 函数式编程• LISP语言prefix_features->prefix_appinfix_app应用:• 数学公式• 编程语言infix_features->infix_apppostfix_app应用:• 计算器• 编译器• 虚拟机postfix_features->postfix_applegend图例说明:━━ 遍历关系┅┅ 特点说明⋯⋯ 应用场景

中序表达式求值

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

  1. 初始化两个栈
    • 操作数栈:用来存储数字。
    • 操作符栈:用来存储操作符和左括号。
  2. 逐个读取中序表达式的字符
    • 如果是 操作数(数字),则直接压入 操作数栈
    • 如果是 左括号,则直接压入 操作符栈
    • 如果是 右括号,则:
      • 操作符栈 中弹出一个操作符。
      • 操作数栈 中弹出所需的操作数。
      • 执行该操作符对应的运算。
      • 将结果压入 操作数栈
      • 重复以上步骤,直到从 操作符栈 中弹出一个左括号。
    • 如果是操作符(如+、-、*、/等):
      • 如果 操作符栈 为空,或栈顶是左括号,或当前操作符 优先级 高于栈顶操作符的 优先级,则直接压入 操作符栈
      • 否则:
        • 操作符栈 中弹出一个操作符。
        • 操作数栈 中弹出所需的操作数。
        • 执行该操作符对应的运算。
        • 将结果压入 操作数栈
        • 重复以上步骤,直到满足上述的压栈条件。
  3. 处理完所有字符后
    • 如果 操作符栈 不为空,则:
      • 操作符栈 中弹出一个操作符。
      • 操作数栈 中弹出所需的操作数。
      • 执行该操作符对应的运算。
      • 将结果压入 操作数栈
      • 重复以上步骤,直到 操作符栈 为空。
  4. 得到结果
    • 此时,操作数栈 中仅存一个数字,这就是整个中序表达式的值。

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

InfixEvaluationstart开始init初始化两个栈:操作数栈 (存储数字)操作符栈 (存储操作符和左括号)start->initread_char读取下一个字符init->read_charchar_type判断字符类型read_char->char_typeoperand操作数 (数字)直接压入操作数栈char_type->operand数字left_paren左括号 '('直接压入操作符栈char_type->left_paren左括号right_paren右括号 ')'char_type->right_paren右括号operator操作符 (+, -, *, /)char_type->operator操作符more_chars还有字符?operand->more_charsleft_paren->more_charsright_paren_process从操作符栈弹出操作符从操作数栈弹出操作数执行运算结果压入操作数栈right_paren->right_paren_processright_paren_check栈顶是左括号?right_paren_process->right_paren_checkright_paren_check->right_paren_processpop_left_paren弹出左括号right_paren_check->pop_left_parenpop_left_paren->more_charsop_condition操作符栈为空 OR栈顶是左括号 OR当前优先级 > 栈顶优先级?operator->op_conditionpush_operator压入操作符栈op_condition->push_operatorpop_and_calc从操作符栈弹出操作符从操作数栈弹出操作数执行运算结果压入操作数栈op_condition->pop_and_calcpush_operator->more_charspop_and_calc->op_conditionmore_chars->read_charfinal_check操作符栈为空?more_chars->final_checkfinal_calc从操作符栈弹出操作符从操作数栈弹出操作数执行运算结果压入操作数栈final_check->final_calcresult操作数栈中的唯一数字就是表达式的值final_check->resultfinal_calc->final_checkend结束result->endpriority操作符优先级:* / 高优先级+ - 低优先级( ) 括号优先级最高

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

步骤输入字符操作操作符栈数据栈
13压入数据栈3
2+压入 操作符栈+3
3(压入 操作符栈+, (3
45压入数据栈+, (3, 5
5*压入 操作符栈+, (, *3, 5
62压入数据栈+, (, *3, 5, 2
7-* 优先级 高于 -* 出栈计算后,将 - 入栈+, (, -3, 10
88压入数据栈+, (, -3, 10, 8
9)处理到 ( 之前的所有操作符+3, 2
10+ 运算符计算5

后序表达式求值

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

  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 - + 说明计算过程:

步骤输入字符操作操作数栈
13压入 操作数栈3
25压入 操作数栈3, 5
32压入 操作数栈3, 5, 2
4*弹出两个操作数并相乘,结果压入 操作数栈3, 10
58压入 操作数栈3, 10, 8
6-弹出两个操作数并相减,结果压入 操作数栈3, 2
7+弹出两个操作数并相加,结果压入 操作数栈5

中序转后序

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

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

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

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

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[结束:得到后缀表达式]
    
    style A fill:#e1f5fe,font-size:24px
    style P fill:#c8e6c9,font-size:24px
    style D fill:#fff3e0,font-size:24px
    style E fill:#fce4ec,font-size:24px
    style F fill:#fce4ec,font-size:24px
    style G fill:#f3e5f5,font-size:24px
    
    classDef default font-size:18px
    classDef largeText font-size:24px
    class A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P largeText
    
    linkStyle default font-size:22px

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

待处理序列后缀表达式当前扫描元素动作
a/b+(c*d-e*f)/gaa 加入后缀表达式
/b+(c*d-e*t)/ga/ 入栈
b+(c*d-e*f)/g/abb 加入后缀表达式
+(c*d-e*f)/g/ab+ 优先级 低于栈顶的 /,弹出
+(c*d-e*f)/gab/+ 入栈
(c*d-e*f)/g+ab/( 入栈
c*d-e*f)/g+(ab/cc 加入后缀表达式
*d-e*f)/g+(ab/c*栈顶为 ( 入栈
d-e*t)/g+(*ab/cdd 加入后缀表达式
-e*f)/g+(*ab/cd-- 先级低于栈顶的 *,弹出 *
-e*f)/g+(ab/cd*-栈顶为 ( 入栈
e*t)/g+(-ab/cd*ee 加入后缀表达式
*f)/g+(-ab/cd*e 优先级 高于栈顶的 入栈
f)/g+(-*ab/cd*eff 加入后缀表达式
)/g+(-*ab/cd*ef把栈中 ( 之前的符号加入表达式
/gab/cd*ef*-// 优先级 高于栈顶的 +/ 入栈
g+/ab/cd*ef*-gg 加入后缀表达式
+/ab/cd*ef*-g扫描完毕,运算符依次退栈加入表达式
ab/cd*ef*-g/+完成

入栈出栈序列

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

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

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

不可能的出栈序列

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

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

A
B
• • • 
• • • 
A
B
• • • 
B 出栈
A
• • • 
A 出栈
出栈序列: • • • B A • • • 
A 一定在 B 之后出栈

卡特兰数

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

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

$$ C_n = \frac{1}{n+1}\binom{2n}{n} $$

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

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

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

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

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

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

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

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

  2. 括号匹配 $n$ 对括号的合法匹配序列数量也为 $C_n$。 例如,当 $n=2$ 时,合法的序列有:

    ()()   (())