第7章 stack（栈）容器详解

stack 是 STL 中的容器适配器，基于序列式容器（默认 deque，也可指定 vector）封装而成，核心遵循"先进后出（LIFO，Last In First Out）"原则，仅支持在栈顶进行插入、删除和访问操作，屏蔽了原容器的其他操作，简化了使用场景。

🎯 本章学习目标

学完本章，你将能够：

理解栈的"先进后出"（LIFO）核心思想
熟练使用 stack 的 push、pop、top、empty、size 等基本操作
理解 stack 是容器适配器，掌握底层容器的选择
掌握括号匹配等栈的经典应用算法
能用栈模拟递归，避免栈溢出
理解栈与队列的核心区别
在实际问题中识别并应用栈的思想
了解栈的常见误区与注意事项

🗺️ 本章知识图谱

stack 栈
├── 核心特性
│   ├── 先进后出（LIFO）
│   ├── 容器适配器
│   ├── 仅栈顶操作
│   └── 无迭代器
├── 基本用法
│   ├── 定义与头文件
│   ├── push（入栈）
│   ├── pop（出栈）
│   ├── top（访问栈顶）
│   ├── empty（判空）
│   └── size（大小）
├── 底层实现
│   ├── 默认 deque
│   ├── 可选 vector
│   └── 底层容器对比
├── 经典应用
│   ├── 括号匹配
│   ├── 逆序输出
│   ├── 递归模拟
│   └── 表达式求值
├── 注意事项
│   ├── 无 clear 方法
│   ├── 不可遍历
│   └── 空栈访问 top 崩溃
└── 适用场景与选型

一、核心特性

🍎 生活比喻：stack 就像食堂里摞盘子——最后放上去的盘子在最上面，你要拿盘子也只能从最上面拿。你不能从中间抽盘子，也不能直接看下面有什么盘子。

容器适配器：非独立容器，依赖底层容器（deque/vector）实现功能；
先进后出：最后插入的元素最先被删除，仅栈顶元素可访问；
无迭代器：不支持随机访问，无法遍历栈中所有元素（需弹出元素才能访问）；
高效操作：栈顶插入（push）、删除（pop）、访问（top）效率均为 O(1)。

🔥 高频考点：栈的 LIFO 特性是选择题的高频考点，经常考"以下哪个数据结构是先进后出"之类的题目。

二、定义与头文件

使用 stack 需包含 <stack> 头文件，定义语法简洁，支持指定底层容器（默认 deque）。

基本定义

cpp

#include <stack>  // stack头文件
using namespace std;

// 1. 默认底层容器（deque），存储int类型
stack<int> st;

// 2. 指定底层容器为vector
stack<int, vector<int>> st_vec;

// 3. 存储其他类型（如string）
stack<string> st_str;

三、常用操作（核心必记）

stack 的操作非常简洁，仅围绕"栈顶"展开，以下是最常用的操作，结合代码示例说明。

完整示例代码

cpp

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

int main() {
    // 定义一个存储int类型的栈
    stack<int> st;
    
    // 1. 插入元素（push，栈顶插入）
    st.push(10);
    st.push(20);
    st.push(30);
    st.push(40);  // 此时栈内元素：10（栈底）→ 20 → 30 → 40（栈顶）
    
    // 2. 访问栈顶元素（top，仅访问，不删除）
    cout << "栈顶元素：" << st.top() << endl;  // 输出：40
    
    // 3. 删除栈顶元素（pop，仅删除，不返回）
    st.pop();  // 删除40，此时栈顶为30
    cout << "pop后栈顶元素：" << st.top() << endl;  // 输出：30
    
    // 4. 判空（empty）
    if (st.empty()) {
        cout << "栈为空" << endl;
    } else {
        cout << "栈非空" << endl;  // 输出：栈非空
    }
    
    // 5. 获取栈的大小（size）
    cout << "栈中元素个数：" << st.size() << endl;  // 输出：3
    
    // 6. 清空栈（无clear()方法，需通过pop循环删除）
    while (!st.empty()) {
        st.pop();
    }
    cout << "清空后栈的大小：" << st.size() << endl;  // 输出：0
    
    return 0;
}

操作汇总表

操作	语法	说明
插入	push(元素)	在栈顶插入一个元素，效率 O(1)
删除	pop()	删除栈顶元素，无返回值，效率 O(1)
访问栈顶	top()	返回栈顶元素，不删除，效率 O(1)
判空	empty()	栈为空返回 true，否则返回 false
获取大小	size()	返回栈中元素的个数
清空	无 clear()	需通过循环 pop() 删除所有元素

💡 小技巧：stack 没有 clear() 方法，清空栈的标准写法是 while (!st.empty()) st.pop();。也可以用技巧 stack<int>().swap(st); 来快速清空（交换一个空栈）。

四、底层实现与选择

stack 的底层容器可指定，默认是 deque，也可选择 vector，两者的区别如下：

1. 默认底层容器：deque

优势：deque 支持双端插入/删除，作为 stack 的底层容器，栈顶操作（push/pop）效率高，且 deque 的内存管理更灵活，避免 vector 扩容时的内存拷贝；
适用场景：大多数日常开发场景，无需手动指定，使用默认即可。

2. 指定底层容器：vector

优势：vector 的内存连续，栈顶访问（top）效率略高于 deque；
劣势：vector 在栈底插入/删除效率低（但 stack 仅操作栈顶，不影响），扩容时会有内存拷贝；
适用场景：需要极致栈顶访问效率，且元素个数相对固定（避免频繁扩容）的场景。

示例：指定 vector 为底层容器

cpp

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

int main() {
    stack<int, vector<int>> st;
    st.push(1);
    st.push(2);
    cout << "栈顶：" << st.top() << endl;  // 输出：2
    return 0;
}

五、常见误区

⚠️ 易错点 1：误以为 stack 有 clear() 方法。stack 没有内置的 clear()，需通过循环 pop() 删除所有元素，或者用 stack<int>().swap(st) 技巧。

⚠️ 易错点 2：试图遍历 stack。stack 不支持迭代器，无法直接遍历，需弹出元素才能访问（弹出后元素会被删除）。如果需要遍历，应该用 vector 或 deque。

⚠️ 易错点 3：混淆 push 和 pop 的作用。push 仅在栈顶插入，pop 仅删除栈顶元素，均不影响栈底及中间元素。

⚠️ 易错点 4：访问空栈的 top()。空栈调用 top() 或 pop() 会导致未定义行为（程序崩溃），需先通过 empty() 判断栈是否非空。

🔥 高频考点：空栈调用 top()/pop() 的后果，经常出现在判断题中。

六、实战场景

stack 的"先进后出"特性，适合以下场景：

1. 括号匹配（算法题高频）

判断一个字符串中的括号（()、[]、{}）是否匹配，利用 stack 存储左括号，遇到右括号时弹出栈顶元素，判断是否匹配。

示例代码：

cpp

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

bool isMatch(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 != '(') || 
                (c == ']' && top != '[') || 
                (c == '}' && top != '{')) {
                return false;
            }
        }
    }
    // 遍历结束后，栈为空则匹配，否则不匹配
    return st.empty();
}

int main() {
    string s1 = "({[]})";
    string s2 = "({[)]}";
    cout << isMatch(s1) << endl;  // 输出：1（匹配）
    cout << isMatch(s2) << endl;  // 输出：0（不匹配）
    return 0;
}

🔥 高频考点：括号匹配是栈最经典的应用，几乎是算法竞赛和考试的必考题。

2. 递归模拟

某些递归场景（如阶乘、斐波那契）可通过 stack 模拟，避免递归深度过大导致栈溢出。

3. 逆序输出

将元素依次压入栈，再依次弹出，即可实现逆序输出。

示例代码：

cpp

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

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    stack<int> st;
    
    // 压入栈
    for (int x : arr) {
        st.push(x);
    }
    
    // 弹出栈（逆序输出）
    cout << "逆序输出：";
    while (!st.empty()) {
        cout << st.top() << " ";
        st.pop();
    }
    cout << endl;  // 输出：5 4 3 2 1
    return 0;
}

4. 表达式求值（进阶）

栈也常用于表达式求值（如中缀转后缀、后缀表达式计算），这是数据结构中的经典应用。

七、stack 与 queue 对比

特性	stack（栈）	queue（队列）
核心原则	先进后出（LIFO）	先进先出（FIFO）
操作位置	仅栈顶	队尾插入、队头删除
访问元素	top()（栈顶）	front()、back()
底层容器	默认 deque	默认 deque
典型应用	括号匹配、递归模拟	BFS、任务排队
生活比喻	摞盘子	排队买票

八、🔖 本章小结

stack 是一种简单、高效的容器适配器，核心优势是"先进后出"的特性和 O(1) 的栈顶操作效率。使用时需注意：无 clear() 方法、不支持遍历、访问 top() 前需判空。日常开发和算法题中，括号匹配、递归模拟、逆序输出是其最常见的应用场景，默认使用 deque 作为底层容器即可满足大多数需求。

九、📝 实战练习

练习题 1（选择题）

题目： stack 遵循的核心原则是？

A. 先进先出（FIFO） B. 先进后出（LIFO） C. 随机访问 D. 优先级排序

🔑 点击查看答案与解析

答案： B

**解析：**stack（栈）的核心特性是先进后出（Last In First Out），最后入栈的元素最先出栈。A 是 queue（队列）的特性，C 是 vector、deque 的特性，D 是 priority_queue 的特性。

练习题 2（判断题）

题目： stack 支持使用迭代器遍历所有元素（）

🔑 点击查看答案与解析

答案： 错误

**解析：**stack 是容器适配器，屏蔽了底层容器的迭代器接口，不支持遍历。要访问栈中元素只能通过 top() 访问栈顶，或弹出元素依次访问。如果需要遍历，应该直接使用底层容器（如 vector、deque）。

练习题 3（选择题）

题目： stack 的默认底层容器是？

A. vector B. list C. deque D. array

🔑 点击查看答案与解析

答案： C

**解析：**stack 默认底层容器是 deque。deque 支持双端操作，且内存管理比 vector 更灵活，不会像 vector 那样有扩容拷贝的问题。也可以手动指定 vector 或 list 作为底层容器。

练习题 4（程序阅读题）

题目： 阅读以下代码，写出输出结果：

cpp

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

int main() {
    stack<int> st;
    st.push(1);
    st.push(2);
    st.push(3);
    cout << st.top() << " ";
    st.pop();
    st.push(4);
    cout << st.top() << " ";
    st.pop();
    cout << st.top() << endl;
    return 0;
}

🔑 点击查看答案与解析

答案： 3 4 2

解析：

push(1) → 栈：[1]
push(2) → 栈：[1, 2]
push(3) → 栈：[1, 2, 3]
top() → 输出 3
pop() → 删除 3，栈：[1, 2]
push(4) → 栈：[1, 2, 4]
top() → 输出 4
pop() → 删除 4，栈：[1, 2]
top() → 输出 2

最终输出：3 4 2

练习题 5（选择题）

题目： 以下关于 stack 的说法，错误的是？

A. stack 的 push、pop、top 操作时间复杂度都是 O(1) B. stack 没有 clear() 方法 C. 空栈调用 top() 会导致未定义行为 D. stack 支持在任意位置插入元素

🔑 点击查看答案与解析

答案： D

解析：

A 正确：栈顶操作都是 O(1)
B 正确：stack 没有 clear()，需要循环 pop
C 正确：空栈访问 top() 或 pop() 会崩溃
D 错误：stack 只能在栈顶操作，不能在任意位置插入

练习题 6（编程题）

题目： 给定一个只包含字符 ( 和 ) 的字符串，判断括号是否有效（即每个左括号都有对应的右括号，且顺序正确）。

**输入格式：**一行字符串，只包含 ( 和 ) **输出格式：**有效输出 Yes，无效输出 No

样例输入 1：

(()())

样例输出 1：

Yes

样例输入 2：

())

样例输出 2：

No

🔑 点击查看答案与解析

参考代码：

cpp

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

int main() {
    string s;
    cin >> s;
    stack<char> st;
    
    for (char c : s) {
        if (c == '(') {
            st.push(c);  // 左括号入栈
        } else {
            // 右括号
            if (st.empty()) {
                // 没有匹配的左括号
                cout << "No" << endl;
                return 0;
            }
            st.pop();  // 弹出一个左括号
        }
    }
    
    // 栈为空说明所有左括号都匹配了
    if (st.empty()) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    
    return 0;
}

**解析：**这是括号匹配的简化版（只有一种括号）。核心思路：遇到左括号入栈，遇到右括号时如果栈空则无效，否则弹出一个左括号。最后栈空则完全匹配。这道题是栈最经典的应用题。

练习题 7（编程题）

题目： 使用栈实现字符串的反转。输入一个字符串，输出反转后的字符串。 **输入格式：**一行，一个不含空格的字符串。 **输出格式：**一行，反转后的字符串。

样例输入：

hello

样例输出：

olleh

🔑 点击查看答案与解析

参考代码：

cpp

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

int main() {
    string s;
    cin >> s;
    stack<char> st;
    
    // 每个字符依次入栈
    for (char c : s) {
        st.push(c);
    }
    
    // 依次出栈，得到反转后的字符串
    string result;
    while (!st.empty()) {
        result += st.top();
        st.pop();
    }
    
    cout << result << endl;
    return 0;
}

**解析：**利用栈"先进后出"的特性，先把所有字符压入栈，再依次弹出，自然就得到了反转后的字符串。这是栈的一个简单但典型的应用。

十、📊 考点总结表

知识点	重要程度	出题形式	易错点
LIFO 特性	⭐⭐⭐⭐⭐	选择题、判断题	与 FIFO 混淆
push/pop/top 操作	⭐⭐⭐⭐⭐	选择题、编程题	pop 不返回值
空栈访问 top/pop	⭐⭐⭐⭐	判断题、选择题	忘记判空导致崩溃
无 clear() 方法	⭐⭐⭐	选择题、判断题	误以为有 clear
无迭代器、不可遍历	⭐⭐⭐	判断题	试图用 for 循环遍历
底层容器（默认 deque）	⭐⭐⭐	选择题	误以为默认是 vector
括号匹配算法	⭐⭐⭐⭐⭐	编程题、阅读题	边界条件处理
栈的时间复杂度 O(1)	⭐⭐⭐⭐	选择题	与其他容器混淆

⭐ 必背速记卡

┌──────────────────────────────────────┐
│  stack 必背速记卡                     │
├──────────────────────────────────────┤
│  1. 先进后出 LIFO，后进先出           │
│  2. 栈顶操作：push、pop、top          │
│  3. 所有栈顶操作时间复杂度 O(1)       │
│  4. 默认底层容器是 deque              │
│  5. 没有 clear()，需循环 pop 清空     │
│  6. 没有迭代器，不能直接遍历          │
│  7. 空栈调用 top/pop 会崩溃           │
│  8. top() 只访问不删除，pop 只删不返  │
│  9. 经典应用：括号匹配、逆序输出       │
│  10. 与 queue 区别：LIFO vs FIFO     │
└──────────────────────────────────────┘

第7章 stack（栈）容器详解 ​

🎯 本章学习目标 ​

🗺️ 本章知识图谱 ​

一、核心特性 ​

二、定义与头文件 ​

基本定义 ​

三、常用操作（核心必记） ​

完整示例代码 ​

操作汇总表 ​

四、底层实现与选择 ​

1. 默认底层容器：deque ​

2. 指定底层容器：vector ​

示例：指定 vector 为底层容器 ​

五、常见误区 ​

六、实战场景 ​

1. 括号匹配（算法题高频） ​

2. 递归模拟 ​

3. 逆序输出 ​

4. 表达式求值（进阶） ​

七、stack 与 queue 对比 ​

八、🔖 本章小结 ​

九、📝 实战练习 ​

练习题 1（选择题） ​

练习题 2（判断题） ​

练习题 3（选择题） ​

练习题 4（程序阅读题） ​

练习题 5（选择题） ​

练习题 6（编程题） ​

练习题 7（编程题） ​

十、📊 考点总结表 ​

⭐ 必背速记卡 ​

第7章 stack（栈）容器详解

🎯 本章学习目标

🗺️ 本章知识图谱

一、核心特性

二、定义与头文件

基本定义

三、常用操作（核心必记）

完整示例代码

操作汇总表

四、底层实现与选择

1. 默认底层容器：deque

2. 指定底层容器：vector

示例：指定 vector 为底层容器

五、常见误区

六、实战场景

1. 括号匹配（算法题高频）

2. 递归模拟

3. 逆序输出

4. 表达式求值（进阶）

七、stack 与 queue 对比

八、🔖 本章小结

九、📝 实战练习

练习题 1（选择题）

练习题 2（判断题）

练习题 3（选择题）

练习题 4（程序阅读题）

练习题 5（选择题）

练习题 6（编程题）

练习题 7（编程题）

十、📊 考点总结表

⭐ 必背速记卡