GESP C++六级数据结构精讲：栈、队列与STL实现及算法应用

GESP C++六级官方考试大纲中，第7条考点回归到了最基础也是最常用的两个线性数据结构：栈 (Stack) 和 队列 (Queue)。

栈和队列是算法世界的“左膀右臂”。如果说数组和链表是存储数据的“地基”，那么栈和队列就是基于这些地基构建的“规则容器”。它们不改变数据的存储方式，而是规定了数据进出的顺序。掌握它们，是理解复杂算法的前提。

一、栈 (Stack)

1.1 基本定义

栈是一种后进先出(LIFO, Last In First Out) 的线性表。其核心限制在于：仅允许在表的一端进行插入和删除运算。这一端被称为栈顶 (Top)，相对的另一端称为栈底 (Bottom)。

1.2 生活中的类比

• 弹夹：最后压进去的子弹，第一个被射出。
• 一摞盘子：洗好的盘子往上叠（入栈），取用时只能拿最上面的（出栈）。
• 浏览器的“后退”按钮：访问的网页依次入栈，点后退时，最近访问的页面先出栈。

1.3 核心操作

• Push (入栈/压栈)：把数据放到栈顶。
• Pop (出栈/弹栈)：移除栈顶的数据。
• Top (取栈顶)：查看栈顶的数据（不移除）。
• Empty (判空)：检查栈是否为空。

1.4 C++ STL 实现

在C++中，我们可以直接使用标准库 <stack>，无需手动模拟。

#include <iostream>
#include <stack> // 引入栈头文件
using namespace std;

int main() {
    stack<int> s; // 定义一个存储 int 的栈

    // 1. 入栈 push
    s.push(10);
    s.push(20);
    s.push(30);
    // 此时栈内结构（从底到顶）：10 -> 20 -> 30

    // 2. 取栈顶 top
    cout << "栈顶元素: " << s.top() << endl; // 输出 30

    // 3. 出栈 pop
    s.pop(); // 移除 30
    cout << "弹出一个后，栈顶元素: " << s.top() << endl; // 输出 20

    // 4. 判空 empty 和 大小 size
    if (!s.empty()) {
        cout << "栈不为空，大小为: " << s.size() << endl; // 输出 2
    }
    return 0;
}

输出：

栈顶元素: 30
弹出一个后，栈顶元素: 20
栈不为空，大小为: 2

1.5 应用场景

• 函数调用栈：程序运行时的递归调用。
• 括号匹配检验：判断表达式中的括号是否合法。
• 表达式求值：将中缀表达式转换为后缀表达式并计算。
• 深度优先搜索 (DFS)：DFS的本质就是递归，而递归的底层实现依赖于栈。想系统学习这类基础算法，可以查阅算法与数据结构专题。

1.6 经典案例：后缀表达式求值

题目描述

给定一个后缀表达式（字符串数组），包含整数和运算符 +, -, *, /。请计算其结果。

• 输入：["2", "1", "+", "3", "*"]
• 输出：9
• 解释：该表达式等价于 (2 + 1) * 3 = 9。

解题思路

利用栈的LIFO特性：

1. 遇到数字：转换后入栈。
2. 遇到运算符：弹出栈顶两个数进行计算（注意顺序），将结果入栈。
3. 结束：栈中剩余的唯一数值即为结果。

代码实现

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

int evalRPN(vector<string>& tokens) {
    stack<int> st;
    for (const string& s : tokens) {
        if (s == "+" || s == "-" || s == "*" || s == "/") {
            int b = st.top(); st.pop(); // 栈顶是右操作数
            int a = st.top(); st.pop(); // 次顶是左操作数
            if (s == "+") st.push(a + b);
            else if (s == "-") st.push(a - b);
            else if (s == "*") st.push(a * b);
            else if (s == "/") st.push(a / b);
        } else {
            st.push(stoi(s)); // 字符串转整数入栈
        }
    }
    return st.top();
}

int main() {
    vector<string> tokens = {"4", "13", "5", "/", "+"}; // 4 + (13 / 5)
    cout << "Result: " << evalRPN(tokens) << endl; // Output: 6
    return 0;
}

二、队列 (Queue)

2.1 基本定义

队列是一种先进先出(FIFO, First In First Out) 的线性表。其限制在于：只允许在表的一端（队尾）进行插入，在另一端（队头）进行删除。

2.2 生活中的类比

• 食堂排队打饭：先来的同学先打饭（先出队），后来的同学排在队尾（入队）。
• 打印机任务队列：先提交的打印任务先被执行。

2.3 核心操作

• Push / Enqueue (入队)：把数据加到队尾。
• Pop / Dequeue (出队)：移除队头的数据。
• Front (取队头)：查看队头的数据。
• Back (取队尾)：查看队尾的数据。

2.4 C++ STL 实现

使用标准库 <queue>。

#include <iostream>
#include <queue> // 引入队列头文件
using namespace std;

int main() {
    queue<string> q; // 定义一个存储 string 的队列

    // 1. 入队 push
    q.push("张三");
    q.push("李四");
    q.push("王五");
    // 此时队列结构（从头到尾）：张三 -> 李四 -> 王五

    // 2. 访问队头 front 和 队尾 back
    cout << "现在轮到谁打饭: " << q.front() << endl; // 张三
    cout << "队尾排的是谁: " << q.back() << endl;   // 王五

    // 3. 出队 pop
    q.pop(); // 张三打完饭走了
    cout << "下一个轮到: " << q.front() << endl; // 李四

    return 0;
}

输出：

现在轮到谁打饭: 张三
队尾排的是谁: 王五
下一个轮到: 李四

2.5 应用场景

• 广度优先搜索 (BFS)：用于图或树的层序遍历，求解最短路径。
• 任务调度：操作系统中的CPU任务调度，遵循先到先服务原则。
• 消息缓冲区：网络通信中的数据包排队处理。

2.6 经典案例：迷宫最短路径 (BFS)

题目描述

给定一个 n x m 的迷宫（0为通路，1为障碍），求从起点 (0,0) 到终点 (n-1, m-1) 的最短步数。

解题思路

BFS (广度优先搜索) 是解决无权图最短路径的经典算法，其核心正是利用队列的FIFO特性实现“层层扩散”：

1. 初始化：起点入队，步数记为0，标记已访问。
2. 扩散循环：
   a. 取出队头当前位置。
   b. 若是终点，返回当前步数。
   c. 向四个方向探索新位置。
   d. 若新位置合法（在界内、是通路、未访问），则记录步数（当前步数+1）、标记访问并入队。
3. 结束：若队列为空仍未到达终点，则说明无通路。

代码实现

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

struct Node {
    int x, y, step;
};

int bfs(vector<vector<int>>& maze) {
    int n = maze.size();
    int m = maze[0].size();
    vector<vector<bool>> visited(n, vector<bool>(m, false));
    queue<Node> q;

    q.push({0, 0, 0}); // 起点入队
    visited[0][0] = true;

    // 方向数组：右、左、下、上
    int dx[] = {0, 0, 1, -1};
    int dy[] = {1, -1, 0, 0};

    while (!q.empty()) {
        Node curr = q.front();
        q.pop();

        // 到达终点
        if (curr.x == n - 1 && curr.y == m - 1) return curr.step;

        for (int i = 0; i < 4; i++) {
            int nx = curr.x + dx[i];
            int ny = curr.y + dy[i];

            // 越界、障碍、已访问检查
            if (nx >= 0 && nx < n && ny >= 0 && ny < m &&
                maze[nx][ny] == 0 && !visited[nx][ny]) {
                visited[nx][ny] = true;
                q.push({nx, ny, curr.step + 1}); // 新位置入队
            }
        }
    }
    return -1; // 无法到达
}

int main() {
    // 0: 通路， 1: 墙
    vector<vector<int>> maze = {
        {0, 1, 0, 0, 0},
        {0, 1, 0, 1, 0},
        {0, 0, 0, 0, 0},
        {0, 1, 1, 1, 0},
        {0, 0, 0, 1, 0}
    };
    cout << "Min Steps: " << bfs(maze) << endl; // Output: 8
    return 0;
}

三、循环队列 (Circular Queue)

3.1 基本定义

循环队列是队列的一种优化实现。它将普通队列的线性存储空间（如数组）在逻辑上视为一个首尾相接的环。目的是高效利用空间，避免因队头出队导致数组前端产生无法使用的“空洞”（假溢出问题）。它依然严格遵循 FIFO 原则。

3.2 为什么需要循环队列？

用普通数组模拟队列时，队头(head)和队尾(tail)指针会不断后移。当tail到达数组末端，即使前面因出队空出大量位置，也无法再插入新元素，造成“假溢出”。循环队列通过取模运算让指针在数组末尾“绕回”开头，从而复用空间。

3.3 核心公式与判空判满

假设数组最大容量为 MAX_SIZE。

• 入队下标移动：tail = (tail + 1) % MAX_SIZE;
• 出队下标移动：head = (head + 1) % MAX_SIZE;
• 判空条件：head == tail
• 判满条件（常用牺牲一个单元法）：(tail + 1) % MAX_SIZE == head
• 元素个数：(tail - head + MAX_SIZE) % MAX_SIZE

理解循环队列的指针移动和边界条件是数据结构学习中的一个重要基础。

3.4 手写循环队列示例

以下是GESP考试中可能出现的代码逻辑，展示了如何用数组手动实现一个循环队列。

#include <iostream>
using namespace std;

const int MAX_SIZE = 5; // 实际只能存 4 个元素，留 1 个位置区分空/满
int q[MAX_SIZE];
int head = 0, tail = 0;

// 入队
bool enqueue(int val) {
    if ((tail + 1) % MAX_SIZE == head) { // 队列满
        cout << "队列满，无法插入: " << val << endl;
        return false;
    }
    q[tail] = val;
    tail = (tail + 1) % MAX_SIZE; // 循环移动队尾指针
    return true;
}

// 出队
bool dequeue() {
    if (head == tail) { // 队列空
        cout << "队列空，无法删除" << endl;
        return false;
    }
    cout << "出队: " << q[head] << endl;
    head = (head + 1) % MAX_SIZE; // 循环移动队头指针
    return true;
}

int main() {
    enqueue(1);
    enqueue(2);
    enqueue(3);
    enqueue(4);
    enqueue(5); // 队列容量为5，存满4个即判满，此次入队会失败
    dequeue();  // 出队 1
    enqueue(5); // 此时前端有空位，可以成功入队 5
    return 0;
}

四、栈与队列对比总结

特性	栈 (Stack)	队列 (Queue)
进出规则	LIFO (后进先出)	FIFO (先进先出)
操作端	仅一端 (栈顶)	两端 (队头出，队尾入)
STL容器	std::stack	std::queue
典型算法	DFS、递归、表达式求值	BFS、任务调度、缓冲区
生活类比	弹夹、一摞盘子	排队打饭、打印机队列

对于GESP C++六级考试，重点在于：

1. 熟练调用STL：在编程题中能快速使用 stack 和 queue 解决问题。
2. 理解循环队列原理：能在选择题中，根据给定的 head、tail 和 MAX_SIZE，正确计算入队出队后的新下标或当前元素个数。

掌握了栈和队列这两个基础而强大的“规则容器”，你就掌握了控制数据流动的关键“交通规则”，这为后续学习更复杂的图论和算法打下了坚实的数据结构基础。