一、总体概览
| 类型 | 所属类别 | 底层实现（默认） | 访问模式 | 特点 |
|---|
stack | 容器适配器 | deque | LIFO（后进先出） | 只在一端（栈顶）操作 |
queue | 容器适配器 | deque | FIFO（先进先出） | 队尾插入、队头删除 |
list | 序列容器 | 双向链表 | 双向顺序访问 | 任意位置高效插入/删除，不支持随机访问 |
注：stack和queue属于容器适配器，它们通过封装底层容器（默认deque）来提供特定的接口。
而list是独立的容器，直接管理内存。
二、区别与联系
1. 区别
| 特性 | stack | queue | list |
|---|
| 元素访问 | 只能访问栈顶top() | 只能访问队头front()和队尾back() | 双向迭代，可用begin()/end()遍历所有元素 |
| 插入操作 | push()（只从顶部） | push()（只从尾部） | push_front()/push_back()/insert() |
| 删除操作 | pop()（只从顶部） | pop()（只从头部） | pop_front()/pop_back()/erase() |
| 随机访问 | ❌ 不支持 | ❌ 不支持 | ❌ 不支持（但可用迭代器遍历） |
| 底层结构 | 默认deque，也可用vector/list | 默认deque，也可用list | 双向链表 |
| 迭代器支持 | ❌ 无迭代器 | ❌ 无迭代器 | ✅ 双向迭代器 |
| 常用场景 | 深度优先搜索、表达式求值 | 广度优先搜索、任务队列 | 需要频繁中间插入/删除的序列 |
2. 联系
三、stack详解
定义
#include <stack> std::stack<T, Container> s; // Container 默认 deque<T>
常用接口
| 函数 | 说明 | 返回值 |
|---|
push(const T& val) | 将val压入栈顶 | void |
pop() | 弹出栈顶元素（无返回值） | void |
top() | 返回栈顶元素的引用 | T&/const T& |
empty() | 判断栈是否为空 | bool |
size() | 返回栈中元素个数 | size_type |
示例
std::stack<int> st; st.push(1); st.push(2); int top = st.top(); // 2 st.pop(); // 弹出2
四、queue详解
定义
#include <queue> std::queue<T, Container> q; // Container 默认 deque<T>
常用接口
| 函数 | 说明 | 返回值 |
|---|
push(const T& val) | 将val放入队尾 | void |
pop() | 弹出队头元素（无返回值） | void |
front() | 返回队头元素的引用 | T&/const T& |
back() | 返回队尾元素的引用 | T&/const T& |
empty() | 判断队列是否为空 | bool |
size() | 返回队列中元素个数 | size_type |
示例
std::queue<int> q; q.push(1); q.push(2); int front = q.front(); // 1 int back = q.back(); // 2 q.pop(); // 移除1
五、list详解
定义
#include <list> std::list<T> lst;
常用接口（按功能分组）
1. 迭代器（遍历用）
| 函数 | 说明 |
|---|
begin()/end() | 正向迭代器 |
rbegin()/rend() | 反向迭代器 |
cbegin()/cend() | const 正向迭代器 |
2. 容量
| 函数 | 说明 |
|---|
empty() | 是否为空 |
size() | 元素个数 |
3. 访问（仅支持首尾直接访问）
| 函数 | 说明 |
|---|
front() | 返回第一个元素的引用 |
back() | 返回最后一个元素的引用 |
4. 插入与删除
| 函数 | 说明 |
|---|
push_front(const T& val) | 头部插入 |
pop_front() | 删除头部元素 |
push_back(const T& val) | 尾部插入 |
pop_back() | 删除尾部元素 |
insert(pos, val) | 在迭代器pos位置插入val（支持多个重载） |
erase(pos)/erase(first, last) | 删除一个或一段元素 |
clear() | 清空所有元素 |
5. 特殊操作（链表特有）
| 函数 | 说明 |
|---|
splice(pos, other) | 将另一个 list 的元素移动到pos前 |
remove(const T& val) | 删除所有等于val的元素 |
remove_if(predicate) | 删除满足条件的元素 |
unique() | 删除连续的重复元素（需先排序） |
merge(other) | 合并两个已排序的 list |
sort() | 对元素排序（不支持 std::sort，用自己的成员函数） |
reverse() | 反转链表 |
示例
std::list<int> lst = {1, 2, 3, 2, 4}; lst.push_front(0); // 0,1,2,3,2,4 lst.remove(2); // 删除所有2 -> 0,1,3,4 lst.sort(); // 0,1,3,4 lst.reverse(); // 4,3,1,0 // 用迭代器遍历 for (auto it = lst.begin(); it != lst.end(); ++it) { std::cout << *it << " "; }
六、使用建议与注意事项
需要 LIFO 行为→stack
需要 FIFO 行为→queue
需要任意位置插入删除，或需要双向迭代→list
stack和queue不提供迭代器，因此不能遍历内部元素（除非通过pop逐个取出）。
list的插入/删除不会使迭代器失效（除了指向被删除元素的迭代器），这是它相对于vector的一大优势。
若想要随机访问，应使用vector或deque，而非list。
三者都支持自定义底层容器，例如：
std::stack<int, std::vector<int>> st; // 基于 vector std::queue<int, std::list<int>> q; // 基于 list
七、总结表格
| 操作 | stack | queue | list |
|---|
| 头部插入 | ❌ | ❌ | ✅push_front |
| 尾部插入 | ✅push | ✅push | ✅push_back |
| 中间插入 | ❌ | ❌ | ✅insert |
| 头部删除 | ❌ | ✅pop | ✅pop_front |
| 尾部删除 | ✅pop | ❌ | ✅pop_back |
| 访问任意位置 | ❌ | ❌ | ❌ (需迭代器) |
| 访问首元素 | ❌ | ✅front | ✅front |
| 访问末元素 | ✅top | ✅back | ✅back |
| 遍历所有元素 | ❌ | ❌ | ✅ 迭代器 |
| 是否适配器 | ✅ | ✅ | ❌ |
