一、课上练习

编程练习

1. 栈的出栈序列：L3201
2. 判定栈的入栈、出栈序列合法性：L3202

二、知识总结

✨ 核心思想

栈是一种重要的抽象数据类型，常被比喻为物理世界中的一堆叠在一起的盘子。这种数据结构具有"后进先出"（Last In, First Out，简称 LIFO）的特性，即最后一个添加到栈中的元素将是第一个被移除的元素。栈的这种特性使其在各种算法和系统中发挥着核心作用，尤其是在任务调度、内存管理、括号匹配、后缀表达式计算等领域。

✨ 栈的基本操作

栈支持几个基本操作，每个操作都可以在常数时间内完成，即时间复杂度为 O(1)：

• Push：将一个元素压入栈顶。
• Pop：从栈顶移除一个元素。
• Top 或 Peek：返回栈顶元素，但不从栈中移除它。
• IsEmpty：检查栈是否为空。
• Size：返回栈中的元素数量。

✨ 实现方式

栈可以通过多种数据结构实现，包括但不限于：

• 数组：使用数组实现栈是最直接的方法。数组的最后一个位置用作栈顶。
• 链表：使用链表实现栈可以提供动态的内存使用。通常使用链表的头部作为栈顶，这样可以轻松地添加和删除元素。

下面分别展示了三种栈的实现方式：

1#include <iostream>
2#include <stdexcept>  // 用于异常处理
3
4const int MAX_SIZE = 100;  // 定义栈的最大容量
5
6int stack[MAX_SIZE];  // 栈的数组
7int top = -1;  // 栈顶指针，初始化为-1表示栈为空
8
9// 入栈操作
10void push(int value) {
11    if (top >= MAX_SIZE - 1) {
12        throw std::overflow_error("Stack overflow");
13    }
14    stack[++top] = value;  // 先增加栈顶指针，再赋值
15}
16
17// 出栈操作
18int pop() {
19    if (top == -1) {
20        throw std::underflow_error("Stack underflow");
21    }
22    return stack[top--];  // 返回栈顶元素，然后减少栈顶指针
23}
24
25// 查看栈顶元素
26int peek() {
27    if (top == -1) {
28        throw std::runtime_error("Stack is empty");
29    }
30    return stack[top];
31}
32
33// 检查栈是否为空
34bool is_empty() {
35    return top == -1;
36}
37
38// 主函数，用于演示栈的操作
39int main() {
40    try {
41        push(10);
42        push(20);
43        push(30);
44
45        std::cout << "Current top element: " << peek() << std::endl;  // 显示栈顶元素
46
47        std::cout << "Elements: ";
48        while (!is_empty()) {
49            std::cout << pop() << " ";  // 逐个出栈并显示
50        }
51        std::cout << std::endl;
52    } catch (const std::exception& e) {
53        std::cerr << "Error: " << e.what() << std::endl;
54    }
55
56    return 0;
57}

✨ 执行示例

下面通过一个具体示例，展示栈的 push 和 pop 操作的完整执行过程。

操作序列： push(5), push(3), push(8), pop(), push(2), pop(), pop()

第 1 步：push(5)

• 栈顶指针 top 从 -1 变为 0
• stack[0] = 5
• 栈状态（从底到顶）：[5]

第 2 步：push(3)

• top 从 0 变为 1
• stack[1] = 3
• 栈状态：[5, 3]

第 3 步：push(8)

• top 从 1 变为 2
• stack[2] = 8
• 栈状态：[5, 3, 8]

第 4 步：pop() -> 返回 8

• 取出 stack[2] = 8，top 从 2 变为 1
• 栈状态：[5, 3]

第 5 步：push(2)

• top 从 1 变为 2
• stack[2] = 2
• 栈状态：[5, 3, 2]

第 6 步：pop() -> 返回 2

• 取出 stack[2] = 2，top 从 2 变为 1
• 栈状态：[5, 3]

第 7 步：pop() -> 返回 3

• 取出 stack[1] = 3，top 从 1 变为 0
• 栈状态：[5]

注意每次 pop 返回的都是最后一个 push 进去的元素，这就是"后进先出"的体现。

后缀表达式求值完整示例： 计算 2 3 4 * + 5 -

最终结果为 9。

1#include<iostream>
2using namespace std;
3
4// 定义链表节点结构，用于实现栈
5struct Node {
6        int value; // 节点存储的值
7        Node *next; // 指向下一个节点的指针
8};
9
10// 函数向栈中推入一个新元素
11void push(Node *head, int x) {
12        Node *node = new Node; // 创建新的节点
13        node->value = x; // 设置节点存储的值
14        node->next = head->next; // 新节点的下一个节点设置为头节点的下一个节点
15        head->next = node;        // 头节点的下一个节点设置为新节点
16}
17
18// 函数从栈中弹出顶部元素
19void pop(Node *head) {
20        Node *node = head->next; // 获取栈顶节点
21        if (node) { // 如果栈不为空
22                cout << node->value << endl; // 打印栈顶元素的值
23                head->next = node->next; // 移除栈顶元素，将头节点的下一个节点设置为栈顶元素的下一个节点
24                delete node; // 释放栈顶节点的内存
25        } else { // 如果栈为空
26                cout << -1 << endl; // 打印-1，表示栈为空
27        }
28}
29
30int main() {
31        Node *head = new Node; // 创建头节点，用作栈的头部
32        head->next = NULL; // 初始化头节点的next为NULL
33        int n = 0; // 存储操作数量
34        cin >> n; // 读取操作数量
35        string op; // 存储操作类型（push或pop）
36        int x = 0; // 存储push操作的值
37        for (int i = 0; i < n; i++) { // 遍历所有操作
38                cin >> op; // 读取操作类型
39                if (op == "push") { // 如果是push操作
40                        cin >> x; // 读取要push的值
41                        push(head, x); // 执行push操作
42                } else { // 如果是pop操作
43                        pop(head); // 执行pop操作
44                }
45        }
46        return 0; // 程序结束
47}

1#include <iostream>
2#include <stack>
3using namespace std;
4
5int main() {
6    stack<int> s;  // 声明一个int类型的栈
7
8    // 向栈中添加元素
9    s.push(10);
10    s.push(20);
11    s.push(30);
12
13    // 访问栈顶元素
14    cout << "Top element: " << s.top() << endl;
15
16    // 移除栈顶元素
17    s.pop();
18    cout << "Top element after pop: " << s.top() << endl;
19
20    // 检查栈是否为空
21    if (!s.empty()) {
22        cout << "Stack is not empty" << endl;
23    }
24
25    // 打印栈的大小
26    cout << "Stack size: " << s.size() << endl;
27
28    return 0;
29}

✨ 应用场景

栈在计算机科学中有广泛的应用：

• 函数调用栈：计算机科学中的函数调用栈使用栈来追踪函数调用的顺序。每当一个函数被调用时，它的返回地址和参数被压入一个栈中，当函数执行完成后，这些信息被用来返回到函数调用的地方。
• 表达式求值：栈用于表达式求值中，尤其是在转换和计算后缀（逆波兰记法）表达式时。
• 括号匹配：在编程和文本编辑中，栈常用来检查文本中的括号是否正确匹配。

✨ 前缀与后缀表达式

中缀表达式

这是我们在日常数学运算中最常见的形式，其中运算符位于操作数的中间。例如：(3 + 4) * 5 - 6。中缀表达式直观易懂，但在计算机处理时，必须处理运算符优先级和括号，这使得解析变得相对复杂。

前缀表达式（波兰表达式）

前缀表达式（也称为波兰表示法）是一种把运算符置于操作数之前的数学表达式表示方式。前缀表达式的一个关键优点是它完全消除了处理表达式时对括号的需要，同时也不需要考虑运算符的优先级。

前缀表达式的计算方式：

• 初始化栈：准备一个空栈来保存操作数。
• 从右到左扫描前缀表达式：对于每一个扫描到的元素：
  • 如果是操作数：将其压入栈中。
  • 如果是运算符：从栈中弹出顶部的两个操作数，根据当前的运算符进行计算，然后将结果压回栈中。
• 完成计算：当整个表达式被扫描完后，栈顶元素即为计算结果。

示例： 考虑前缀表达式 + 3 4 5，表示的中缀表达式是 (3 4) + 5。计算过程如下：

• 扫描 5：压入栈。
• 扫描 4：压入栈。
• 扫描 3：压入栈。
• 扫描 ：弹出 3 和 4，计算 3 4 = 12，压入栈。
• 扫描 +：弹出 12 和 5，计算 12 + 5 = 17，压入栈。
• 栈顶的 17 就是结果。

中缀表达式转前缀表达式

将中缀表达式转换为前缀表达式涉及以下步骤：

• 初始化两个栈：一个用于操作数和括号，另一个专门用于运算符。
• 从右至左扫描中缀表达式：
  • 如果遇到操作数：直接输出（或添加到结果列表）。
  • 如果遇到运算符：如果运算符栈顶的运算符优先级大于或等于当前运算符，并且栈顶的运算符不是左括号，则将栈顶运算符弹出并输出，然后将当前运算符压入栈；否则，直接将当前运算符压入栈。
  • 如果遇到右括号：直接压入栈。
  • 如果遇到左括号：则弹出运算符直到遇到右括号，括号内的运算符按弹出顺序输出。
• 栈中剩余运算符的处理：将所有剩余运算符弹出并输出。
• 逆序输出：由于我们从右向左处理中缀表达式，最后需要将结果逆序以得到正确的前缀表达式。

示例： 将中缀表达式 A + B C - D 转换为前缀表达式：最终前缀表达式为 - + A B C D。

后缀表达式（逆波兰表达式）

后缀表达式（也称为逆波兰记法）是一种数学表达式的表示方法，其中运算符位于所有操作数的后面。这种表示法不需要括号来指示操作的优先顺序。

后缀表达式的计算方式：

• 创建一个空栈：用于存储操作数。
• 从左至右扫描后缀表达式：
  • 遇到操作数时：将其压入栈中。
  • 遇到运算符时：从栈中弹出栈顶的两个元素（注意顺序），使用运算符对这两个元素进行计算，将结果压回栈中。
• 表达式结束后：栈顶的元素即为表达式的结果。

示例： 考虑后缀表达式 3 4 + 5 * 6 -。计算过程如下：

• 3 和 4 被压入栈。
• 遇到 +，弹出 4 和 3，计算 3 + 4 = 7，结果 7 压入栈。
• 5 压入栈。
• 遇到 ，弹出 5 和 7，计算 7 5 = 35，结果 35 压入栈。
• 6 压入栈。
• 遇到 -，弹出 6 和 35，计算 35 - 6 = 29，结果 29 压入栈。
• 最终，栈顶元素 29 就是整个表达式的计算结果。

中缀表达式转后缀表达式

将中缀表达式转换为后缀表达式涉及以下步骤：

• 初始化两个栈：一个用于输出（构建最终的后缀表达式），另一个用于运算符（包括括号）。
• 从左至右扫描中缀表达式：
  • 遇到操作数时：直接输出到后缀表达式。
  • 遇到运算符时：如果栈顶运算符具有较高或相等的优先级，则弹出并输出到后缀表达式，然后将当前运算符压入栈；否则，直接将当前运算符压入栈。
  • 遇到左括号时：压入栈。
  • 遇到右括号时：弹出栈中的运算符并输出，直到遇到左括号为止（左括号弹出但不输出）。
• 扫描完毕后：将栈中剩余的运算符依次弹出并输出。

示例： 将中缀表达式 A + B C - D 转换为后缀表达式：最终得到的后缀表达式是 A B C + D -。

转换中缀表达式到后缀表达式的过程中，使用栈来处理运算符的优先级是关键，这确保了在输出后缀表达式时运算符的顺序正确地反映了运算的优先级和结合性。

✨ 解题步骤详解

以"括号匹配检验"为例，介绍如何使用栈解决问题：

问题： 给定一个包含 ()、[]、{} 的字符串，判断括号是否正确匹配。

解题步骤：

1. 创建一个空栈：用于存储遇到的左括号。
2. 从左到右扫描字符串：逐个字符处理。
3. 遇到左括号（(、[、{）：直接压入栈。
4. 遇到右括号（)、]、}）：
   • 如果栈为空，说明没有对应的左括号，直接判定不匹配。
   • 如果栈顶的左括号与当前右括号不是同一类型，判定不匹配。
   • 如果栈顶的左括号匹配，弹出栈顶元素，继续扫描。
5. 扫描结束后：如果栈为空，说明所有括号都正确匹配；如果栈不为空，说明有多余的左括号。

示例： 检验 ([{}])

• 扫描 (：压入栈，栈 = [(]
• 扫描 [：压入栈，栈 = [(, []
• 扫描 {：压入栈，栈 = [(, [, {]
• 扫描 }：栈顶 { 匹配，弹出，栈 = [(, []
• 扫描 ]：栈顶 [ 匹配，弹出，栈 = [(]
• 扫描 )：栈顶 ( 匹配，弹出，栈 = []
• 扫描结束，栈为空，匹配成功。

✨ 常见错误

1. pop 前未检查栈是否为空：对空栈执行 pop 或 top 操作会导致未定义行为或程序崩溃。每次 pop/top 前必须先用 empty() 或检查 top 指针。
2. 数组实现时栈溢出：使用固定大小数组实现栈时，push 前要检查是否已满（top >= MAX_SIZE - 1）。
3. 后缀表达式求值时操作数顺序搞反：遇到运算符时，先弹出的是右操作数，后弹出的是左操作数。对于减法和除法，顺序很重要：a b - 表示 a - b，不是 b - a。
4. 中缀转后缀时运算符优先级处理错误：要注意 * 和 / 的优先级高于 + 和 -，在比较时必须正确处理。
5. 忘记处理栈中剩余元素：中缀转后缀结束后，栈中可能还有运算符，需要全部弹出。

三、课后练习

编程练习

1. 括弧匹配检验：L3203