GESP 六级 第 01 讲：栈、队列与循环队列

本讲定位：六级最稳的送分块。三套新大纲真题里，单选第 4、5 题固定是「栈的模拟」和「循环队列的 front/rear 模拟」，判断题再出 2～3 题，合计 10～14 分，而且全是手工模拟，不需要任何算法思维。这是六级性价比最高的一讲。

同时，栈和队列是后面两讲的地基：DFS 靠栈（递归就是系统帮你压栈），BFS 靠队列。六级第 05、06 讲会反复回到本讲。

对应官方大纲：六级知识块 6「栈和队列」——栈、队列、循环队列。

前置知识：四级第 02 讲（数组与指针）、五级第 04 讲（链表）。

代码说明：本讲代码均已用 g++ 11.5（-std=c++11）编译运行验证，所有标注的输出均为本机实测。

1. 栈：后进先出

栈（stack）是只能在一端进出的线性表。 那一端叫栈顶（top），另一端叫栈底（bottom）。

$$ \boxed{\textbf{LIFO：Last In, First Out —— 后进先出}} $$

生活中的模型：一摞盘子。最后放上去的盘子，最先被拿走。

1.1 三个核心操作

还有两个辅助操作：empty() 判空、size() 问个数。

1.2 手工模拟（必须让学生画）

真题原型：2026 年 6 月六级单选第 4 题。 文本编辑器把用户输入的字符依次压入栈 S，用户依次输入 X, Y, Z, W 后，连续执行两次撤销（每次撤销弹出栈顶一个字符），问此时栈从栈底到栈顶的内容。

画一个竖着的格子，从下往上长：

输入 X        输入 Y        输入 Z        输入 W        撤销          撤销
                                        ┌───┐
                                        │ W │←顶
                            ┌───┐       ├───┤       ┌───┐
                            │ Z │←顶    │ Z │       │ Z │←顶
                ┌───┐       ├───┤       ├───┤       ├───┤       ┌───┐
                │ Y │←顶    │ Y │       │ Y │       │ Y │       │ Y │←顶
    ┌───┐       ├───┤       ├───┤       ├───┤       ├───┤       ├───┤
    │ X │←顶    │ X │       │ X │       │ X │       │ X │       │ X │←底
    └───┘       └───┘       └───┘       └───┘       └───┘       └───┘

答案是 X Y。

⚠️ 读题两个坑：

1. 题目问的是「从栈底到栈顶」，答案要写 X Y；如果写成 Y X，就是把顺序倒了。每次读到栈的题，先圈出题目问的是哪个方向。
2. 「撤销两次」是弹出两个元素，不是弹出后又放回去。

1.3 STL 的 stack

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

int main() {
    stack<int> s;
    s.push(10);
    s.push(20);
    s.push(30);

    cout << s.top() << endl;   // 看栈顶
    s.pop();                   // 弹掉栈顶
    cout << s.top() << endl;
    cout << s.size() << endl;
    cout << (s.empty() ? "empty" : "not empty") << endl;
    return 0;
}

输出：