C++：stack适配器

前言：在 C++ 标准模板库（STL）中，stack（栈）是一种先进先出（LIFO, Last-In-First-Out） 的容器适配器（container adapter），它基于其他基础容器（如 deque、vector 或 list）实现，仅提供栈的核心操作接口，隐藏了底层容器的复杂细节。

一、stack 的核心特性

1、LIFO 原则：最后插入的元素最先被删除，只能从容器的顶部（栈顶）进行插入、删除和访问操作。

2、容器适配器：stack 本身不直接管理内存，而是依赖一个底层容器（默认是 deque）来存储数据，stack 仅封装了一组接口来限制对底层容器的访问（只允许栈顶操作）。

3、无迭代器：stack 不支持迭代器，无法遍历容器中的元素（体现了栈的 “封装性”，仅暴露必要操作）。

二、底层实现（容器适配器）

stack 的实现依赖于底层容器，该容器必须支持以下操作：

• push_back()：在尾部插入元素（对应栈的压入）
• pop_back()：删除尾部元素（对应栈的弹出）
• back()：访问尾部元素（对应栈顶元素）
• empty()：判断容器是否为空
• size()：返回元素个数

STL 中默认使用 deque 作为底层容器（因 deque 两端操作效率高），但也可以指定其他容器（如 vector 或 list），只要满足上述操作要求。

指定底层容器的示例：

#include <stack>
#include <vector>
#include <list>

// 用 vector 作为底层容器的 stack
std::stack<int, std::vector<int>> stack_vec;

// 用 list 作为底层容器的 stack
std::stack<int, std::list<int>> stack_list;

三、常用接口与示例

stack 的接口设计简洁，仅提供栈的核心操作：

1. 构造与初始化

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

// 1. 默认构造（底层容器为 deque）
stack<int> st1;

// 2. 用底层容器初始化
deque<int> dq = {1, 2, 3};
stack<int> st2(dq); // 栈顶元素为 3（因 deque 尾部元素是 3）

2. 元素访问

接口	功能	备注
top()	返回栈顶元素的引用	若栈为空，访问会导致未定义行为（通常崩溃）

示例：

stack<int> st;
st.push(10);
st.push(20);
cout << st.top() << endl; // 输出 20（栈顶是最后插入的元素）

3. 容量操作

接口	功能
empty()	判断栈是否为空（为空返回 true，否则 false）
size()	返回栈中元素的个数

示例：

stack<int> st;
cout << st.empty() << endl; // 输出 1（true，栈为空）
st.push(1);
cout << st.size() << endl;  // 输出 1

4. 修改操作（核心）

接口	功能	时间复杂度
push(val)	在栈顶插入元素 val	O (1)（依赖底层容器的 push_back）
pop()	删除栈顶元素（无返回值）	O (1)（依赖底层容器的 pop_back）
swap(st)	交换两个栈的内容（包括底层容器的数据）	O(1)

示例：栈的压入与弹出

stack<int> st;

// 压入元素（栈顶依次变为 1 → 2 → 3）
st.push(1);
st.push(2);
st.push(3);

// 弹出元素（栈顶依次变为 2 → 1 → 空）
st.pop();  // 移除 3
st.pop();  // 移除 2
cout << st.top() << endl; // 输出 1

四、stack 与其他容器的对比

容器 / 适配器	核心特性	访问方式	典型场景
stack	LIFO（后进先出）	仅栈顶操作，无迭代器	函数调用栈、表达式求值、括号匹配
queue	FIFO（先进先出）	仅队头 / 队尾操作，无迭代器	任务调度、消息队列
vector	随机访问	支持下标和迭代器，尾部操作高效	动态数组、缓存数据

注意：stack 不是独立的容器，而是 “适配器”，其功能依赖于底层容器，但接口被简化为纯栈操作，适合需要严格遵循 LIFO 原则的场景。

五、使用注意事项

1、栈为空时的操作：
调用 top() 或 pop() 前，必须先用 empty() 检查栈是否为空，否则会导致未定义行为（程序可能崩溃）。

if (!st.empty()) {
    st.pop(); // 安全操作
}

2、底层容器的选择：

• 默认的 deque 适合大多数场景（两端操作高效，无内存溢出风险）。
• 若需要更快的随机访问（且能容忍可能的内存重新分配），可选用 vector。
• 若需要稳定的迭代器（插入 / 删除不导致迭代器失效），可选用 list。

3、无遍历功能：

stack 不提供迭代器，无法遍历所有元素（设计初衷是限制访问方式）。若需遍历，需手动弹出元素并暂存（但会破坏栈结构）。

六、典型应用场景

1、括号匹配：检查表达式中的括号是否成对出现（如 ()、[]、{}）。

2、函数调用栈：模拟程序运行时的函数调用与返回（每调用一个函数压栈，返回时弹栈）。

3、表达式求值：实现后缀表达式（逆波兰表达式）的计算。

4、深度优先搜索（DFS）：用栈存储待访问节点，实现递归的非递归版本。

总结：stack 是 STL 中实现 “后进先出” 逻辑的容器适配器，基于底层容器（默认 deque）实现，接口简洁，仅支持栈顶的插入、删除和访问。它适合需要严格遵循 LIFO 原则的场景，通过封装底层容器的接口，保证了操作的安全性和简洁性。