GESP 6级

stack 和 queue

6级 · 指针/STL/复杂度
💡 为什么重要

stack（栈）和 queue（队列）是两种最基本的受限数据结构。栈的"后进先出"特性是括号匹配、函数调用栈、表达式求值等问题的核心。队列的"先进先出"特性是BFS（广度优先搜索）的必备工具。GESP 6级考试几乎必考这两种容器的应用场景。

📖 前置知识
  • vector 的基本操作（push_back、pop_back、size、empty）
  • for 循环和 while 循环
  • 字符串的基本处理
🔍 什么是栈（Stack）？

栈是一种后进先出（LIFO, Last In First Out）的数据结构。想象一摞盘子：你只能从最上面放盘子，也只能从最上面取盘子。最后放上去的盘子最先被取走。

操作只有三种：

  • push：往栈顶放入一个元素
  • pop：从栈顶取出一个元素
  • top：查看栈顶元素（不取走）
📐 stack 操作
#include <stack>
stack<int> st; // 创建空栈
st.push(x) // 压入x到栈顶
st.pop() // 弹出栈顶元素（无返回值）
st.top() // 返回栈顶元素（不弹出）
st.size() // 元素个数
st.empty() // 是否为空
💻 stack 代码详解
📝 示例1：stack 基本操作
#include <iostream>
#include <stack>            // 必须包含这个头文件
using namespace std;

int main() {
    stack<int> st;            // 创建一个空栈

    // 压入元素（像摞盘子）
    st.push(10);               // 栈: [10]
    st.push(20);               // 栈: [10, 20]（20在栈顶）
    st.push(30);               // 栈: [10, 20, 30]（30在栈顶）

    // 查看栈顶（不取走）
    cout << "栈顶: " << st.top() << endl;
    // 输出: 栈顶: 30

    // 弹出栈顶（取走盘子）
    st.pop();                   // 弹出30，栈变成 [10, 20]
    cout << "弹出后栈顶: " << st.top() << endl;
    // 输出: 弹出后栈顶: 20

    // 查看大小
    cout << "大小: " << st.size() << endl;
    // 输出: 大小: 2

    // 依次弹出所有元素（栈空时结束）
    while (!st.empty()) {
        cout << st.top() << " ";  // 先看再弹
        st.pop();
    }
    cout << endl;               // 输出: 20 10（后进先出！）

    return 0;
}
📝 示例2：经典应用——括号匹配
#include <iostream>
#include <stack>
#include <string>
using namespace std;

bool isBalanced(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();            // 查看栈顶
            st.pop();                        // 弹出栈顶

            // 检查是否匹配
            if (c == ')' && top != '(') return false;
            if (c == ']' && top != '[') return false;
            if (c == '}' && top != '{') return false;
        }
    }
    return st.empty();  // 栈空=全部配对成功
}

int main() {
    cout << isBalanced("()[]{}") << endl;   // 1（true）
    cout << isBalanced("([{}])") << endl;   // 1（true）
    cout << isBalanced("(]") << endl;        // 0（false）
    cout << isBalanced("(((") << endl;       // 0（false）
    return 0;
}
🔍 什么是队列（Queue）？

队列是一种先进先出（FIFO, First In First Out）的数据结构。想象排队买票：先来的人先买到票离开。

操作有四种：

  • push：在队尾放入元素
  • pop：从队头取走元素
  • front：查看队头元素
  • back：查看队尾元素
📐 queue 操作
#include <queue>
queue<int> q; // 创建空队列
q.push(x) // 在队尾加入x
q.pop() // 移除队头元素（无返回值）
q.front() // 返回队头元素
q.back() // 返回队尾元素
q.size() // 元素个数
q.empty() // 是否为空
💻 queue 代码详解
📝 示例3：queue 基本操作
#include <iostream>
#include <queue>
using namespace std;

int main() {
    queue<int> q;             // 创建空队列

    // 入队（像排队）
    q.push(10);                // 队列: [10]
    q.push(20);                // 队列: [10, 20]（20在队尾）
    q.push(30);                // 队列: [10, 20, 30]（30在队尾）

    // 查看队头和队尾
    cout << "队头: " << q.front() << endl;  // 输出10
    cout << "队尾: " << q.back() << endl;   // 输出30

    // 出队（先进先出）
    q.pop();                    // 弹出10，队列: [20, 30]
    cout << "出队后队头: " << q.front() << endl;
    // 输出: 出队后队头: 20

    // 依次出队
    while (!q.empty()) {
        cout << q.front() << " ";  // 先看再弹
        q.pop();
    }
    cout << endl;               // 输出: 20 30（先进先出！）

    return 0;
}
📝 示例4：经典应用——BFS（广度优先搜索）
#include <iostream>
#include <queue>
using namespace std;

// 简单的BFS示例：从节点1开始，逐层访问
// 图的邻接表表示
vector<int> adj[6];  // 6个节点的图（编号1~5）

int main() {
    // 建图（无向图）
    adj[1] = {2, 3};    // 1连接2和3
    adj[2] = {1, 4};    // 2连接1和4
    adj[3] = {1, 5};    // 3连接1和5
    adj[4] = {2};        // 4连接2
    adj[5] = {3};        // 5连接3

    bool visited[6] = {false};  // 记录是否访问过
    queue<int> q;              // BFS用的队列

    // 从节点1开始BFS
    q.push(1);                  // 起点入队
    visited[1] = true;          // 标记为已访问

    while (!q.empty()) {
        int u = q.front();      // 取出队头
        q.pop();                // 弹出队头
        cout << u << " ";      // 访问节点u

        // 把u的所有未访问邻居入队
        for (int v : adj[u]) {
            if (!visited[v]) {
                visited[v] = true;   // 标记（避免重复访问）
                q.push(v);           // 入队
            }
        }
    }
    cout << endl;
    // 输出: 1 2 3 4 5（逐层访问）

    return 0;
}
⚠️ 易错点
  • pop() 没有返回值：st.pop() 和 q.pop() 都不返回值！要先 top() 或 front() 获取值，再 pop
  • 对空栈/空队列操作：对空的 stack 调 top()、对空的 queue 调 front() 都是未定义行为。先用 empty() 检查
  • 栈和队列没有下标访问：不能用 st[0] 或 q[0]，只能访问栈顶或队头
  • BFS 中忘记标记 visited：如果不标记已访问，队列中可能反复放入同一个节点，导致死循环
  • 括号匹配忘记检查栈空：遇到右括号时，如果栈已空（没有左括号匹配），应该返回 false
🎯 练习建议
  • 入门：用 stack 将一个整数按位拆分并倒序输出（如 1234 → 4 3 2 1）
  • 进阶：实现完整的括号匹配（支持三种括号：()、[]、{}）
  • 挑战：用两个栈实现一个队列
  • BFS 练习：在网格迷宫中，用 BFS 找到从起点到终点的最短路径
  • 思考：为什么 BFS 用队列而 DFS 用栈（或递归）？
← 上一个：vector 容器 📖 返回主目录 下一个：链表概念 →