GESP C++ 六级：栈精讲

核心目标：理解栈的后进先出（LIFO）特性，掌握栈的两种实现方式（数组模拟与 STL stack），熟练运用栈解决括号匹配、表达式求值、进制转换、字符串处理等经典问题，理解栈与递归的关系。
栈是“只有一个口”的容器——后进先出（LIFO）；只允许在栈顶插入和删除；数组模拟用 top 指针，STL 用 push/pop/top/empty/size；经典应用是括号匹配、表达式求值、进制转换和函数调用。

一、考纲定位

根据 CCF 官方考纲，GESP 六级数据结构部分明确要求掌握栈和队列的基本概念与操作，以及它们在算法问题中的应用。

栈在六级考试中的考查分布：

考点	重要程度	典型考法
栈的基本概念（LIFO）	★★★★★	选择题高频
栈的数组模拟实现		代码填空、程序阅读
STL stack 的使用	★★★★☆	编程题
括号匹配	★★★★★	编程题高频
表达式求值	★★★★☆	编程题、代码填空
进制转换		编程题
栈与递归的关系		选择题
栈的合法出栈序列		选择题高频
栈与队列的区别	★★★★★	选择题

二、栈的基本概念

2.1 什么是栈

栈（Stack）是一种只能在一端进行插入和删除操作的线性数据结构。允许操作的一端称为栈顶（top） ，另一端称为栈底（bottom） 。

栈的核心特性是后进先出（Last In First Out，LIFO）：最后入栈的元素最先出栈。

直观比喻：栈就像一叠盘子，你只能从最上面放盘子，也只能从最上面拿盘子。最后放上去的盘子最先被拿走。

2.2 栈的基本操作

操作	英文	含义
入栈	push	在栈顶插入一个元素
出栈	pop	删除栈顶元素
取栈顶	top	读取栈顶元素（不删除）
判空	empty	判断栈是否为空
求大小	size	返回栈中元素个数

2.3 栈 vs 队列

对比项	栈	队列
操作端	只在栈顶操作	队尾入队，队头出队
特性	后进先出（LIFO）	先进先出（FIFO）
插入	push（栈顶）	push（队尾）
删除	pop（栈顶）	pop（队头）
典型应用	括号匹配、表达式求值、递归	BFS、任务调度、缓冲区

三、栈的数组模拟实现

3.1 核心思路

用一个数组 st[] 存储栈元素，用一个整数 top 记录栈顶位置。top = -1 表示空栈。

3.2 标准代码

const int N = 100005;
int st[N];       // 栈数组
int top = -1;    // 栈顶指针，-1 表示空栈

// 入栈
void push(int x) {
    st[++top] = x;
}

// 出栈
void pop() {
    if (top >= 0) top--;
}

// 取栈顶
int getTop() {
    return st[top];
}

// 判空
bool empty() {
    return top == -1;
}

// 求大小
int size() {
    return top + 1;
}

3.3 关键要点

要点	说明
top = -1	表示空栈，这是最常用的约定
入栈	先 top++，再赋值 st[top] = x
出栈	直接 top--，元素逻辑上被删除
取栈顶	st[top]，前提是 top >= 0
栈大小	top + 1
栈满判断	top == N - 1

3.4 真题示例（代码填空）

下面代码用数组模拟栈，横线处应填入（ ）。

const int N = 100005;
int st[N];
int top = -1;

void push(int x) {
 ______;
}

A. st[top++] = x;
B. st[++top] = x;
C. st[top] = x; top++;
D. top++; st[top] = x;
答案：B 或 D（两者等价，但 B 更简洁）

关键：入栈必须先移动 top，再赋值。top 初始为 -1，第一次入栈时 top 变为 0，st[0] 存入元素。

四、STL stack 的使用

C++ 标准库提供了 stack 容器，使用前需要包含头文件 <stack>。

4.1 基本用法

#include <stack>
using namespace std;

stack<int> s;        // 创建一个存储 int 的栈

s.push(10);          // 入栈
s.push(20);
s.push(30);

cout << s.top() << endl;   // 输出 30（栈顶）
s.pop();                    // 弹出栈顶
cout << s.top() << endl;   // 输出 20

cout << s.size() << endl;  // 输出 2
cout << s.empty() << endl; // 输出 0（false，不为空）

4.2 常用函数

函数	作用	示例
push(x)	入栈	s.push(10);
pop()	出栈（无返回值）	s.pop();
top()	取栈顶	int x = s.top();
empty()	判空	if (s.empty())
size()	求大小	int n = s.size();

重要注意：pop() 只删除栈顶元素，不返回被删除的值。如果需要获取栈顶值，必须先 top() 再 pop()。

int x = s.top();   // 先取
s.pop();           // 再删

4.3 使用前必须判空

if (!s.empty()) {
    int x = s.top();
    s.pop();
}

直接对空栈调用 top() 或 pop() 是未定义行为，可能导致程序崩溃。

五、经典应用一：括号匹配

5.1 问题描述

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

匹配规则：

• 每个左括号必须有一个对应的右括号。
• 左括号必须以正确的顺序闭合。
• 例如 {[()]} 合法，{[(])} 不合法。

5.2 解题思路

1. 遇到左括号，入栈。
2. 遇到右括号，检查栈顶是否为对应的左括号：
   • 是：弹出栈顶，继续。
   • 否：不匹配，返回 false。
3. 遍历结束后，栈必须为空。

5.3 代码实现

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

bool isValid(string s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);
        } else {
            if (st.empty()) return false;   // 右括号多余
            char top = st.top();
            if ((c == ')' && top == '(') ||
                (c == ']' && top == '[') ||
                (c == '}' && top == '{')) {
                st.pop();
            } else {
                return false;   // 括号不匹配
            }
        }
    }
    return st.empty();   // 左括号多余则栈不为空
}

int main() {
    string s;
    cin >> s;
    if (isValid(s)) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

5.4 复杂度

时间 O(n)，空间 O(n)。

5.5 真题示例

输入字符串 {[()]}，判断括号是否匹配。答案：匹配。
输入字符串 {[(])}，判断括号是否匹配。答案：不匹配。

六、经典应用二：表达式求值

6.1 问题描述

给定一个中缀表达式（如 3 + 4 * 2），计算其结果。

6.2 中缀转后缀（逆波兰表达式）

中缀表达式：运算符在操作数中间，如 3 + 4 * 2。
后缀表达式：运算符在操作数后面，如 3 4 2 * +。

6.3 用栈计算后缀表达式

int evalRPN(vector<string>& tokens) {
    stack<int> st;
    for (string t : tokens) {
        if (t == "+" || t == "-" || t == "*" || t == "/") {
            int b = st.top(); st.pop();
            int a = st.top(); st.pop();
            if (t == "+") st.push(a + b);
            else if (t == "-") st.push(a - b);
            else if (t == "*") st.push(a * b);
            else st.push(a / b);
        } else {
            st.push(stoi(t));   // 数字入栈
        }
    }
    return st.top();
}

6.4 中缀转后缀的算法

1. 遇到数字：直接输出。
2. 遇到左括号：入栈。
3. 遇到右括号：弹出栈顶并输出，直到遇到左括号，左括号弹出但不输出。
4. 遇到运算符：弹出栈顶所有优先级大于等于当前运算符的运算符并输出，然后当前运算符入栈。
5. 遍历结束后，弹出栈中所有运算符并输出。

运算符优先级：* / > + -。

七、经典应用三：进制转换

7.1 问题描述

将十进制数转换为其他进制（如二进制、八进制）。

7.2 用栈实现

十进制转二进制的方法：不断除以 2，取余数，最后倒序输出余数。倒序正好可以用栈实现。

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

int main() {
    int n;
    cin >> n;

    stack<int> st;
    if (n == 0) {
        cout << 0 << endl;
        return 0;
    }

    while (n > 0) {
        st.push(n % 2);   // 余数入栈
        n /= 2;
    }

    while (!st.empty()) {
        cout << st.top();  // 倒序输出
        st.pop();
    }
    cout << endl;
    return 0;
}

7.3 关键点

• 十进制转任意进制都是“除基取余，倒序排列”。
• 栈的 LIFO 特性天然适合“倒序输出”。

八、经典应用四：单调栈

8.1 什么是单调栈

单调栈是一种特殊的栈，栈内元素保持单调递增或单调递减。常用于解决“下一个更大元素”“最大矩形面积”等问题。

8.2 下一个更大元素

问题：给定数组，对每个元素找到它右边第一个比它大的元素。

vector<int> nextGreater(vector<int>& nums) {
    int n = nums.size();
    vector<int> res(n, -1);
    stack<int> st;   // 存下标，栈内对应值单调递减

    for (int i = 0; i < n; i++) {
        while (!st.empty() && nums[i] > nums[st.top()]) {
            res[st.top()] = nums[i];   // 找到了下一个更大元素
            st.pop();
        }
        st.push(i);
    }
    return res;
}

8.3 核心思想

• 维护一个单调递减的栈（从栈底到栈顶递减）。
• 当新元素比栈顶大时，栈顶元素的下一个更大元素就是新元素。
• 每个元素最多入栈一次、出栈一次，时间复杂度 O(n)。

九、栈与递归的关系

9.1 函数调用栈

递归函数的执行依赖于系统调用栈。每次递归调用都会在栈上分配一个栈帧，保存局部变量、返回地址等信息。递归返回时，栈帧被弹出。

递归深度 = 调用栈的最大高度。

9.2 递归转非递归

任何递归程序都可以用栈模拟系统调用栈，改写为迭代版本。

递归版阶乘：

int fac(int n) {
    if (n == 0) return 1;
    return n * fac(n - 1);
}

栈模拟版：

int fac(int n) {
    stack<int> st;
    while (n > 0) {
        st.push(n);
        n--;
    }
    int res = 1;
    while (!st.empty()) {
        res *= st.top();
        st.pop();
    }
    return res;
}

9.3 栈溢出

递归深度过大时，系统调用栈的空间被耗尽，导致栈溢出（Stack Overflow） ，程序崩溃。

十、合法出栈序列（高频选择题）

10.1 问题描述

给定入栈序列（如 1, 2, 3, 4），判断某个序列是否为合法的出栈序列。

10.2 判断方法

核心原则：对于出栈序列中的任意一个元素，在它之后出栈且比它先入栈的元素，必须保持逆序。

示例：入栈顺序为 1, 2, 3, 4。

出栈序列	是否合法	原因
4, 3, 2, 1	✅	全部入栈后依次出栈
1, 2, 3, 4		入一个出一个
3, 2, 4, 1		合法
3, 1, 2, 4	❌	3 出栈后，1 比 2 先出，违反逆序
4, 1, 2, 3		4 出栈后，1 比 2 先出，违反逆序

10.3 模拟验证法

用栈模拟入栈和出栈过程：

bool isValidOrder(vector<int>& pushSeq, vector<int>& popSeq) {
    stack<int> st;
    int j = 0;
    for (int x : pushSeq) {
        st.push(x);
        while (!st.empty() && st.top() == popSeq[j]) {
            st.pop();
            j++;
        }
    }
    return st.empty();
}

10.4 真题示例

入栈顺序为 1、2、3、4，以下哪个不可能是出栈顺序？
A. 1, 4, 3, 2 B. 2, 3, 4, 1 C. 4, 3, 1, 2 D. 3, 2, 1, 4
答案：C
解析：C 中 4 出栈后，1 比 2 先出，但 1 比 2 先入栈，违反了“后进先出”原则。

十一、GESP 六级栈真题精讲

真题1：栈的基本操作（选择题）

以下关于栈的说法，正确的是（ ）。
A. 栈是先进先出的数据结构
B. 栈只能在栈顶进行插入和删除
C. 栈的插入操作在栈底进行
D. 栈可以随机访问任意元素
答案：B

真题2：出栈序列判断（选择题）

入栈顺序为 A、B、C、D，以下哪个不可能是出栈顺序？
A. D, C, B, A B. A, B, C, D C. C, A, B, D D. B, D, C, A
答案：C

真题3：括号匹配（编程题）

给定一个只包含 ( 和 ) 的字符串，判断括号是否匹配。
输入：(()())，输出：Yes
输入：(()，输出：No

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

int main() {
    string s;
    cin >> s;
    stack<char> st;
    bool ok = true;
    for (char c : s) {
        if (c == '(') st.push(c);
        else {
            if (st.empty()) { ok = false; break; }
            st.pop();
        }
    }
    if (!st.empty()) ok = false;
    cout << (ok ? "Yes" : "No") << endl;
    return 0;
}

真题4：栈的数组模拟（代码填空）

下面代码用数组模拟栈，横线处应填入（ ）。

int st[100005];
int top = -1;

void pop() {
 if (______) top--;
}

答案：top >= 0

十二、易错点汇总

1. 空栈调用 top/pop：必须先 empty() 判断，否则未定义行为。
2. 数组模拟栈 top 初始值：top = -1 表示空栈，不是 0。
3. 入栈顺序写反：必须先 top++，再 st[top] = x。
4. STL pop 不返回值：pop() 只删除，不返回，需要先 top()。
5. 括号匹配忘记最终判空：遍历结束后必须检查栈是否为空。
6. 括号匹配右括号多余：遇到右括号时栈为空，直接返回 false。
7. 出栈序列判断错误：用模拟法验证，不要凭感觉。
8. 单调栈存值还是存下标：通常存下标，方便计算距离和更新结果。
9. 递归与栈的关系：递归深度 = 调用栈高度，深度过大导致栈溢出。
10. 栈与队列混淆：栈是 LIFO，队列是 FIFO，操作端不同。
11. 数组模拟栈大小不足：数组要开足够大，防止溢出。
12. 表达式求值操作数顺序：后缀表达式求值时，先弹出的是右操作数，后弹出的是左操作数。

十三、速查表

需求	数组模拟	STL stack
定义	int st[N]; int top = -1;	stack<int> s;
入栈	st[++top] = x;	s.push(x);
出栈	top--;	s.pop();
取栈顶	st[top]	s.top()
判空	top == -1	s.empty()
大小	top + 1	s.size()
头文件	无	<stack>
括号匹配	左括号入栈，右括号匹配栈顶	遍历后判空
后缀表达式	数字入栈，运算符弹出两个计算	注意操作数顺序
进制转换	余数入栈，倒序输出	除基取余
单调栈	维护单调递增/递减	存下标
出栈序列	模拟入栈出栈过程	验证合法性

十四、总结

栈是 GESP 六级数据结构模块的核心内容。

1. 栈是后进先出（LIFO）的线性结构，只能在栈顶操作。
2. 数组模拟栈：top = -1 表示空栈，入栈先 top++ 再赋值。
3. STL stack：push 入栈、pop 出栈、top 取顶、empty 判空、size 求大小。
4. pop() 不返回被删除的值，需要先 top() 再 pop()。
5. 括号匹配：左括号入栈，右括号匹配栈顶，最后判空。
6. 后缀表达式求值：数字入栈，运算符弹出两个操作数计算后入栈。
7. 进制转换：除基取余，余数入栈，倒序输出。
8. 单调栈用于找“下一个更大/更小元素”，时间复杂度 O(n)。
9. 递归依赖系统调用栈，递归深度 = 调用栈高度，过深导致栈溢出。
10. 合法出栈序列用模拟法验证：入栈序列依次入栈，匹配出栈序列则弹出。

复习建议：先把数组模拟栈和 STL stack 的基本操作写熟；再重点攻克括号匹配和表达式求值两个经典应用；然后理解单调栈的思想和出栈序列的判断方法；最后练习进制转换和递归转非递归。考试中先判断题目考的是基本操作、经典应用还是出栈序列判断，再套用对应模板作答。