当前没有测试数据。

一、【我们为什么学它？】

栈是解决“顺序依赖”类问题的神器，比如判断括号是否匹配、计算表达式值、模拟递归（DFS）过程等；在CSP-J竞赛中，栈常出现在基础编程题（如括号匹配、模拟操作题），也是CSP-S中复杂算法（如单调栈优化）的基础，掌握它能搞定至少10%-15%的竞赛基础分。

二、【它到底是什么？】

核心定义

栈（Stack）是一种后进先出（LIFO, Last In First Out） 的线性数据结构——就像你往弹夹里装子弹，最后装进去的那颗，会最先被打出来；也像叠盘子，最后叠上去的盘子，要先拿下来才能拿到下面的。

直白解释

栈只有一个“出入口”，数据只能从这个口“进（压入）”和“出（弹出）”，永远只能操作最顶端的元素，底层元素必须等上层都取走才能访问。

核心语法示例（C++标准写法）

#include <iostream>
// 引入栈的标准头文件，符合C++14/17规范
#include <stack>
using namespace std;

int main() {
    // 定义一个存储整数的栈，stack<数据类型> 栈名
    stack<int> st;

    // 1. 压入元素（往栈顶加数据）
    st.push(10);
    st.push(20);
    st.push(30); // 此时栈内：10（底）→20→30（顶）
 
    // 2. 访问栈顶元素（只能看，不能改）
    cout << "栈顶元素：" << st.top() << endl; // 输出30

    // 3. 弹出栈顶元素（删除栈顶，无返回值）
    st.pop(); // 此时栈内：10→20（顶）

    // 4. 判断栈是否为空
    if (!st.empty()) {
        cout << "栈非空，当前元素个数：" << st.size() << endl; // 输出2
    }

    return 0;
}

运行结果：

栈顶元素：30
栈非空，当前元素个数：2

三、【在竞赛中怎么用？】

经典例题：括号合法匹配

题目描述：给定一个只包含 ()、[]、{} 的字符串，判断括号是否合法。 合法条件：1）每个左括号都有对应的右括号； 2）括号嵌套顺序正确（如([)]不合法）。

代码示例

#include <iostream>
#include <stack>
#include <string>
using namespace std;

// 判断括号是否匹配的核心函数
bool is_valid(const string& s) {
    stack<char> st;
    for (char c : s) {
        // 左括号：压入栈
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);
        } else {
            // 右括号：先检查栈是否为空（无左括号匹配）
            if (st.empty()) {
                return false;
            }
            // 取出栈顶左括号，判断是否匹配
            char top_char = st.top();
            st.pop();
            if ((c == ')' && top_char != '(') || 
                (c == ']' && top_char != '[') || 
                (c == '}' && top_char != '{')) {
                return false;
            }
        }
    }
    // 遍历结束后，栈必须为空（所有左括号都匹配）
    return st.empty();
}

int main() {
    string s;
    cout << "请输入括号字符串：";
    cin >> s;
    if (is_valid(s)) {
        cout << "括号合法！" << endl;
    } else {
        cout << "括号不合法！" << endl;
    }
    return 0;
}

输入输出示例

• 输入：([]){} → 输出：括号合法！
• 输入：([)] → 输出：括号不合法！
• 输入：{} → 输出：括号合法！
• 输入：({ → 输出：括号不合法！

【解题思路点拨】

1. 核心思想：利用栈“后进先出”的特性，匹配最近的左括号——遇到左括号就压栈，遇到右括号就检查栈顶是否是对应的左括号；
2. 边界处理：如果遇到右括号时栈为空（没有左括号匹配），直接判定不合法；
3. 最终校验：遍历完字符串后，栈必须为空（否则有未匹配的左括号）。

四、【千万小心！】

易错点1：访问空栈的top()或pop()

• 错误原因：栈为空时调用st.top()（取栈顶）或st.pop()（弹栈），会触发C++运行时错误（程序崩溃），竞赛中这种错误直接丢分；
• 正确做法：每次调用top()/pop()前，必须用st.empty()检查栈是否非空（如例题中处理右括号时先判断if (st.empty())）。

易错点2：混淆栈的“后进先出”逻辑

• 错误原因：比如处理括号时，把右括号和栈底元素匹配（而非栈顶），导致逻辑错误（如([)]误判为合法）；
• 正确做法：牢记栈只能操作栈顶元素，所有匹配/处理都要针对栈顶，比如例题中右括号只和st.top()比较。

易错点3：多组测试用例时未清空栈

• 错误原因：竞赛中若有多组输入（如多组括号字符串），上一组的栈元素会残留，导致下一组判断错误；
• 正确做法：每组测试用例处理前，用while (!st.empty()) st.pop();清空栈，或在每组用例中重新定义栈（局部变量自动清空）。

五、【快来练练手】

练习题：4567. 合法括号

题目背景：给定只包含()的字符串，计算最少需要添加多少个括号，才能让字符串合法（如())需要添加1个左括号，((需要添加2个右括号）。

输入要求：输入一行只包含(和)的字符串（长度1≤n≤1000）； 输出要求：输出一个整数，表示最少需要添加的括号数量。

示例：

• 输入：()) → 输出：1
• 输入：(( → 输出：2
• 输入：()() → 输出：0

总结

1. 栈的核心特性是后进先出，只能操作栈顶元素，核心操作：push()（压栈）、pop()（弹栈）、top()（取栈顶）、empty()（判空）；
2. 竞赛中使用栈必须先判空再访问栈顶/弹栈，多组用例要清空栈；
3. 括号匹配是栈的经典应用，核心逻辑是“左括号压栈，右括号匹配栈顶”。