C++ 栈的基础与典型应用

深入理解栈数据结构及其在信息学竞赛中的应用

栈：后进先出 (LIFO) 的数据结构

栈（Stack）是一种特殊的线性表，它只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为**栈顶 (Top)**，另一端称为**栈底 (Bottom)**。

栈的数据元素遵循**后进先出 (Last In First Out, LIFO)** 的原则。可以把它想象成一叠盘子或者一个只有一个开口的桶，最后放进去的盘子/物品总是最先被取出来。

基本操作

push(element)：将元素 element 压入栈顶。
pop()：移除栈顶元素。
top()：获取栈顶元素的值，但不移除它。
empty()：检查栈是否为空。如果栈为空，返回 true，否则返回 false。
size()：返回栈中元素的个数。

栈操作可视化演示

C++ STL 中的 `stack`

C++ 标准模板库 (STL) 提供了 stack 容器适配器，它封装了底层容器（默认是 deque），并提供了标准的栈操作接口。使用前需要包含头文件 <stack>。

// 引入 stack 头文件
#include <iostream>
#include <stack>
#include <string> // 如果栈中存储字符串等需要
using namespace std;

int main() {
    // 创建一个存储整数的栈对象
    stack<int> myStack;

    // 1. 入栈 (push) - 向栈顶添加元素
    cout << "入栈: 10, 20, 30\n";
    myStack.push(10); // 栈: [10]
    myStack.push(20); // 栈: [10, 20]
    myStack.push(30); // 栈: [10, 20, 30] (30在栈顶)

    // 2. 获取栈顶元素 (top) - 查看但不移除
    // 注意：在调用 top() 或 pop() 前，应确保栈不为空
    if (!myStack.empty()) {
        cout << "栈顶元素 (top): " << myStack.top() << endl; // 输出: 30
    }

    // 3. 获取栈的大小 (size)
    cout << "当前栈大小 (size): " << myStack.size() << endl; // 输出: 3

    // 4. 出栈 (pop) - 移除栈顶元素
    cout << "执行一次出栈 (pop)\n";
    myStack.pop(); // 移除 30, 栈: [10, 20]
    cout << "出栈后栈顶元素: " << myStack.top() << endl; // 输出: 20
    cout << "出栈后栈大小: " << myStack.size() << endl; // 输出: 2

    // 5. 检查栈是否为空 (empty)
    cout << "栈是否为空 (empty)? " << (myStack.empty() ? "是" : "否") << endl; // 输出: 否

    // 遍历并清空栈
    cout << "清空栈并打印元素: ";
    while (!myStack.empty()) {
        cout << myStack.top() << " "; // 输出栈顶元素
        myStack.pop();                   // 移除栈顶元素
    }
    cout << endl; // 输出: 20 10

    cout << "清空后栈是否为空? " << (myStack.empty() ? "是" : "否") << endl; // 输出: 是

    return 0;
}

应用一：括号匹配检测

在编程语言或数学表达式中，括号（如 (), [], {}）必须正确配对和嵌套。例如 {[()]} 是合法的，而 [(]) 或 (() 是非法的。栈是解决这类问题的理想工具。

基本思路：

遍历输入的括号字符串。
遇到**左括号** ((, [, {)，将其压入栈中。
遇到**右括号** (), ], })：
- 如果此时栈为空，说明没有对应的左括号，匹配失败。
- 如果栈不为空，取出栈顶的左括号。判断它是否与当前右括号匹配。
- 如果不匹配（例如 ] 遇到了 (），则匹配失败。
- 如果匹配，则将栈顶元素弹出，继续处理下一个字符。
遍历结束后，如果栈为空，说明所有括号都成功匹配。如果栈不为空，说明有未闭合的左括号，匹配失败。

括号匹配演示

栈状态

C++ 实现括号匹配

#include <iostream>
#include <stack>
#include <string>
#include <unordered_map> // 用于存储括号配对关系
using namespace std;

// 函数：检查括号字符串是否有效
bool isValidParentheses(const string& s) {
    stack<char> parenthesesStack; // 创建一个字符栈
    // 定义括号配对关系，方便查找
    unordered_map<char, char> pairs = {
        {')', '('},
        {']', '['},
        {'}', '{'}
    };

    // 遍历输入字符串中的每个字符
    for (char ch : s) {
        if (pairs.count(ch)) { // 如果当前字符是右括号
            // 1. 检查栈是否为空 (右括号多了)
            // 2. 或者栈顶的左括号与当前右括号不匹配
            if (parenthesesStack.empty() || parenthesesStack.top() != pairs[ch]) {
                return false; // 匹配失败
            }
            // 匹配成功，弹出栈顶的左括号
            parenthesesStack.pop();
        } else { // 如果当前字符是左括号
            // 将左括号压入栈中
            parenthesesStack.push(ch);
        }
    }

    // 遍历结束后，如果栈为空，则所有括号都匹配成功
    // 如果栈不为空，说明有未闭合的左括号
    return parenthesesStack.empty();
}

int main() {
    string str1 = "{[()()]}";
    string str2 = "([)]";
    string str3 = "(()";

    cout << "\"" << str1 << "\" is " << (isValidParentheses(str1) ? "valid" : "invalid") << endl; // 输出: valid
    cout << "\"" << str2 << "\" is " << (isValidParentheses(str2) ? "valid" : "invalid") << endl; // 输出: invalid
    cout << "\"" << str3 << "\" is " << (isValidParentheses(str3) ? "valid" : "invalid") << endl; // 输出: invalid

    return 0;
}

应用二：中缀表达式转后缀表达式

我们通常书写的数学表达式，如 a + b * c，称为**中缀表达式**，操作符位于操作数之间。计算机处理时，后缀表达式（也叫逆波兰表示法，Reverse Polish Notation, RPN）更方便，如 a b c * +，操作符位于操作数之后。

使用栈可以将中缀表达式转换为后缀表达式。转换规则如下：

初始化一个空栈（用于存放操作符）和一个空列表（用于存放后缀表达式结果）。
从左到右扫描中缀表达式。
遇到**操作数**（数字或变量）：直接将其添加到后缀表达式列表。
遇到**左括号 `(`**：将其压入操作符栈。
遇到**右括号 `)`**：持续从操作符栈顶弹出操作符并添加到后缀表达式列表，直到遇到左括号 `(`。将这对括号丢弃（不添加到后缀表达式）。
遇到**操作符**（如 +, -, *, /）：
- 比较当前操作符与栈顶操作符的优先级。
- 如果栈为空，或者栈顶是左括号 `(`，或者当前操作符优先级**高于**栈顶操作符：将当前操作符压入栈。
- 否则（当前操作符优先级**小于或等于**栈顶操作符）：持续从栈顶弹出操作符并添加到后缀表达式列表，直到满足上述条件（栈为空、栈顶为 `(` 或当前操作符优先级高于栈顶）。然后将当前操作符压入栈。
中缀表达式扫描完毕后，将操作符栈中剩余的所有操作符依次弹出并添加到后缀表达式列表。

注意：需要定义操作符的优先级（通常 *, / 高于 +, -）。相同优先级的操作符按从左到右处理（即遇到同级或低级就弹出）。

中缀转后缀演示

等待开始...

操作符栈(栈底<-->栈顶)

后缀表达式输出

C++ 实现中缀转后缀

#include <iostream>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector> // 用于存储后缀表达式序列
using namespace std;

// 定义操作符优先级
int getPriority(char op) {
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/') return 2;
    return 0; // 其他字符（如括号）优先级最低
}

// 中缀表达式转后缀表达式函数 (简化版，处理单字符变量/数字和 +-*/())
vector<string> infixToPostfix(const string& infix) {
    stack<char> opStack;       // 操作符栈
    vector<string> postfix; // 后缀表达式结果列表 (用 string 存储，方便处理多位数或变量名)

    for (int i = 0; i < infix.length(); ++i) {
        char token = infix[i];

        // 忽略空格
        if (isspace(token)) continue;

        // 如果是操作数（这里简化为字母或数字）
        if (isalnum(token)) {
            // 实际应用中可能需要处理多位数或变量名
            postfix.push_back(string(1, token));
        }
        // 如果是左括号
        else if (token == '(') {
            opStack.push(token);
        }
        // 如果是右括号
        else if (token == ')') {
            // 将栈顶操作符弹出并加入后缀表达式，直到遇到左括号
            while (!opStack.empty() && opStack.top() != '(') {
                postfix.push_back(string(1, opStack.top()));
                opStack.pop();
            }
            if (!opStack.empty()) {
                opStack.pop(); // 弹出左括号 '('
            } else {
                 // 错误：括号不匹配
                 cerr << "Error: Mismatched parentheses!" << endl;
                 return {}; // 返回空表示错误
            }
        }
        // 如果是操作符
        else {
            // 当栈不为空，栈顶不是左括号，且当前操作符优先级 <= 栈顶操作符优先级时，弹出栈顶操作符
            while (!opStack.empty() && opStack.top() != '(' && getPriority(token) <= getPriority(opStack.top())) {
                postfix.push_back(string(1, opStack.top()));
                opStack.pop();
            }
            // 将当前操作符压入栈
            opStack.push(token);
        }
    }

    // 将栈中剩余的操作符全部弹出并加入后缀表达式
    while (!opStack.empty()) {
         if (opStack.top() == '(') {
             // 错误：括号不匹配
             cerr << "Error: Mismatched parentheses!" << endl;
             return {}; // 返回空表示错误
         }
        postfix.push_back(string(1, opStack.top()));
        opStack.pop();
    }

    return postfix;
}

int main() {
    string infix = "a+b*(c-d)-e/f";
    vector<string> postfix = infixToPostfix(infix);

    cout << "Infix: " << infix << endl;
    cout << "Postfix: ";
    for (const string& s : postfix) {
        cout << s << " "; // 输出: a b c d - * + e f / -
    }
    cout << endl;

    infix = "1+2*3";
    postfix = infixToPostfix(infix);
     cout << "Infix: " << infix << endl;
    cout << "Postfix: ";
    for (const string& s : postfix) {
        cout << s << " "; // 输出: 1 2 3 * +
    }
    cout << endl;

    return 0;
}

应用三：后缀表达式求值

计算后缀表达式（RPN）的值比计算中缀表达式更直接，同样可以利用栈来完成。求值过程如下：

初始化一个空栈（用于存放操作数）。
从左到右扫描后缀表达式的每一个元素（操作数或操作符）。
如果遇到**操作数**：将其压入操作数栈。
如果遇到**操作符**：
- 从操作数栈中弹出**两个**操作数（注意顺序：先弹出的是右操作数，后弹出的是左操作数）。
- 执行该操作符对应的运算。
- 将计算结果压回操作数栈。
- （需要处理除数为零等异常情况）。
后缀表达式扫描完毕后，操作数栈中应该只剩下一个元素，这个元素就是表达式的最终计算结果。

例如：计算后缀表达式 3 4 + 2 * 7 /

遇到 3: 压栈 [3]
遇到 4: 压栈 [3, 4]
遇到 +: 弹出 4 和 3，计算 3 + 4 = 7，压栈 [7]
遇到 2: 压栈 [7, 2]
遇到 *: 弹出 2 和 7，计算 7 * 2 = 14，压栈 [14]
遇到 7: 压栈 [14, 7]
遇到 /: 弹出 7 和 14，计算 14 / 7 = 2，压栈 [2]
结束，栈中结果为 2。

后缀表达式求值演示

等待开始...

操作数栈(栈底<-->栈顶)

当前计算

-

C++ 实现后缀表达式求值

#include <iostream>
#include <stack>
#include <string>
#include <vector>
#include <sstream> // 用于方便地分割字符串
#include <stdexcept> // 用于抛出异常
using namespace std;

// 函数：计算后缀表达式的值
// 输入是以空格分隔的后缀表达式字符串
int evaluatePostfix(const string& postfixExpr) {
    stack<int> operandStack; // 操作数栈
    stringstream ss(postfixExpr); // 使用 stringstream 来分割字符串
    string token;

    // 逐个读取由空格分隔的元素
    while (ss >> token) {
        // 尝试将 token 转换为整数
        try {
            int number = stoi(token); // stoi 会在无法转换时抛出异常
            operandStack.push(number); // 如果是数字，压入操作数栈
        } catch (const invalid_argument& e) {
            // 如果不是数字，则认为是操作符
            if (operandStack.size() < 2) {
                throw runtime_error("后缀表达式错误：操作数不足！");
            }

            // 从栈顶弹出两个操作数
            int operand2 = operandStack.top(); operandStack.pop(); // 先弹出的是右操作数
            int operand1 = operandStack.top(); operandStack.pop(); // 后弹出的是左操作数

            int result = 0;
            // 根据操作符执行计算
            if (token == "+") {
                result = operand1 + operand2;
            } else if (token == "-") {
                result = operand1 - operand2;
            } else if (token == "*") {
                result = operand1 * operand2;
            } else if (token == "/") {
                if (operand2 == 0) {
                    throw runtime_error("后缀表达式错误：除数不能为零！");
                }
                result = operand1 / operand2; // 注意：整数除法
            } else {
                throw runtime_error("后缀表达式错误：遇到未知操作符 '" + token + "'！");
            }
            // 将计算结果压回栈中
            operandStack.push(result);
        }
    }

    // 表达式处理完毕后，栈中应只剩下一个元素，即最终结果
    if (operandStack.size() == 1) {
        return operandStack.top();
    } else {
        throw runtime_error("后缀表达式错误：格式不正确或操作符/操作数不匹配！");
    }
}

int main() {
    string rpn1 = "3 4 + 2 * 7 /"; // 结果: (3+4)*2/7 = 14/7 = 2
    string rpn2 = "10 2 8 * + 3 -"; // 结果: 10 + (2*8) - 3 = 10 + 16 - 3 = 23

    try {
        cout << "\"" << rpn1 << "\" = " << evaluatePostfix(rpn1) << endl; // 输出: 2
        cout << "\"" << rpn2 << "\" = " << evaluatePostfix(rpn2) << endl; // 输出: 23
    } catch (const runtime_error& e) {
        cerr << "计算出错: " << e.what() << endl;
    }

     string rpn_error = "3 4 + *"; // 错误：操作数不足
     try {
        evaluatePostfix(rpn_error);
     } catch (const runtime_error& e) {
         cerr << "计算 \"" << rpn_error << "\" 时出错: " << e.what() << endl;
     }


    return 0;
}

小测验：检验学习成果

来做几道题，看看你是否掌握了栈的基本概念和应用吧！

总结与展望

恭喜你完成了本次关于 C++ 栈的学习！让我们回顾一下关键知识点：

栈的基本概念

栈是一种**后进先出 (LIFO)** 的数据结构，主要操作包括 `push`, `pop`, `top`, `empty`, `size`。C++ STL 提供了方便的 `stack` 容器适配器。

应用一：括号匹配

利用栈的 LIFO 特性，可以有效检查表达式或代码中的括号是否配对、嵌套正确。遇到左括号入栈，遇到右括号检查栈顶是否匹配并出栈。

应用二：中缀转后缀表达式

栈是实现中缀表达式到后缀表达式（逆波兰表示法）转换的关键工具。通过比较操作符优先级和处理括号，可以生成易于计算机处理的后缀形式。

应用三：后缀表达式求值

后缀表达式的求值过程也依赖栈：遇到数字入栈，遇到操作符则弹出操作数进行计算，结果再入栈。最终栈内剩余的就是结果。

继续探索

掌握了栈，你就掌握了一种强大的解决问题的工具！栈是许多算法和数据结构的基础，例如：

深度优先搜索 (DFS) 图遍历
函数调用栈（理解递归的关键）
撤销/重做功能实现

接下来，你可以继续学习其他重要的数据结构，如**队列 (Queue)** - 先进先出 (FIFO)，**优先队列 (Priority Queue)**，以及用于处理集合合并与查询的**并查集 (Disjoint Set Union)** 等。这些都将在信息学竞赛和实际编程中发挥重要作用。

C++ 栈的基础与典型应用

栈：后进先出 (LIFO) 的数据结构

基本操作

栈操作可视化演示

C++ STL 中的 stack

应用一：括号匹配检测

C++ 实现括号匹配

应用二：中缀表达式转后缀表达式

C++ 实现中缀转后缀

应用三：后缀表达式求值

C++ 实现后缀表达式求值

小测验：检验学习成果

总结与展望

栈的基本概念

应用一：括号匹配

应用二：中缀转后缀表达式

应用三：后缀表达式求值

继续探索

C++ STL 中的 `stack`