GESP 6级 · stack和queue容器

📖概念讲解

【考点 · 6级】STL适配器容器 stack/queue —— 两个受限访问的容器，分别实现后进先出（LIFO）和先进先出（FIFO）。

stack（栈）只能操作栈顶：push 进、pop 出、top 看顶。queue（队列）只能操作队首和队尾：push 进队尾、pop 出队首、front 看队首。它们的底层默认都是 deque，但你不需要管底层，只管用接口就行。

⚠️ 易错：stack/queue 没有迭代器，不能用 for 遍历！想看内容只能逐个 pop。另外 empty() 判断空、size() 看大小，这些通用方法别忘了。

💻代码示例

栈和队列的核心操作对比：

#include <iostream>
#include <stack>
#include <queue>
using namespace std;
int main() {
    stack<int> st;          // 定义一个整数栈（LIFO）
    st.push(10);             // 栈: [10]
    st.push(20);             // 栈: [10, 20]
    st.push(30);             // 栈: [10, 20, 30]，30在栈顶
    cout << "栈顶: " << st.top() << endl;   // 输出30，top()看栈顶
    st.pop();                // 弹出栈顶30，栈变为 [10, 20]
    cout << "弹出后栈顶: " << st.top() << endl; // 输出20
    cout << "栈大小: " << st.size() << endl;   // 输出2
    cout << "---队列演示---" << endl;
    queue<int> q;           // 定义一个整数队列（FIFO）
    q.push(100);             // 队列: [100]
    q.push(200);             // 队列: [100, 200]
    q.push(300);             // 队列: [100, 200, 300]
    cout << "队首: " << q.front() << endl;    // 输出100，front()看队首
    q.pop();                // 弹出队首100，队列变为 [200, 300]
    cout << "弹出后队首: " << q.front() << endl; // 输出200
    cout << "队尾: " << q.back() << endl;     // 输出300，back()看队尾
    cout << "队列大小: " << q.size() << endl;  // 输出2
    return 0;
}
// 输出
// 栈顶: 30
// 弹出后栈顶: 20
// 栈大小: 2
// ---队列演示---
// 队首: 100
// 弹出后队首: 200
// 队尾: 300
// 队列大小: 2

⚡ 记忆口诀：栈 = 后进先出（往桶里放盘子，只能从顶拿）；队列 = 先进先出（排队买奶茶，先来先走）。queue 有 front() 和 back()，stack 只有 top()！

🧩互动小测

题目 1：栈的操作顺序

依次执行 push(1)、push(2)、push(3)、pop()、top()，栈顶元素是？

题目 2：queue的弹出顺序

依次 push(A)、push(B)、push(C)、pop()、pop()，剩下什么？

题目 3：哪个说法正确？

🏋️动手练一练

📝 编程练习

题目：用栈实现括号匹配检查。
给定一个只包含 () 的字符串，判断括号是否合法匹配。合法的定义：每个左括号都有对应的右括号，且嵌套正确。

输入示例：()()() → 合法 | (()) → 合法 | (() → 不合法

提示：遇到左括号就 push 进栈，遇到右括号就检查栈是否为空再 pop，最后检查栈是否清空。

参考答案：

#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 ? "合法" : "不合法") << endl;
    return 0;
}

要点：核心思想 —— 栈记录"还没匹配的左括号数量"。遇到右括号时栈空就是非法（右括号多了），最后栈非空也是非法（左括号多了）。O(n) 时间，O(n) 空间。

📝易错点提醒

pop() 不返回值！ 要先 top() 取值再 pop() 弹出，很多同学写 int x = st.pop() 是错的
不能遍历！ stack/queue 没有 begin()/end()，想看内容只能逐个弹出来
queue 有 front() 和 back()，stack 只有 top() —— 别混用！queue 没有 top()，stack 没有 front()
空容器调用 top()/front()/back() 是未定义行为！ 一定要先 empty() 检查
#include 头文件别忘： stack 需要 <stack>，queue 需要 <queue>

📘stack和queue容器

📖概念讲解

💻代码示例

🧩互动小测

题目 1：栈的操作顺序

题目 2：queue的弹出顺序

题目 3：哪个说法正确？

🏋️动手练一练

📝 编程练习

📝易错点提醒