1. 理解Stack与Queue的核心特性
在C++标准模板库(STL)中，stack和queue是两种最基础的容器适配器。它们通过限制底层容器的访问方式，强制实现了特定的数据访问规则。
**stack（栈）**遵循LIFO（Last In First Out，后进先出）原则，就像餐厅里叠放的餐盘：
- 你只能从最顶部取放餐盘
- 最后放上去的餐盘会被最先取走
- 典型应用：函数调用栈、表达式求值、撤销操作
#include <stack> std::stack<int> s; // 默认基于deque实现 s.push(1); // 栈顶：1 s.push(2); // 栈顶：2 → 1 s.pop(); // 移除2，栈顶变回1**queue（队列）**遵循FIFO（First In First Out，先进先出）原则，如同超市收银台前的队伍：
- 新顾客从队尾加入
- 只有队首的顾客能结账离开
- 典型应用：任务调度、消息队列、广度优先搜索
#include <queue> std::queue<int> q; q.push(1); // 队尾：1 q.push(2); // 队尾：2 ← 1 q.pop(); // 移除1，队首变为2关键区别：stack只允许操作一端（栈顶），而queue允许操作两端（队头出、队尾入）
2. Stack的完整操作指南
2.1 底层容器选择
stack默认使用deque作为底层容器，但也可以指定其他容器：
stack<int, vector<int>> s1; // 基于vector stack<int, list<int>> s2; // 基于list选择建议：
- deque（默认）：头尾操作都是O(1)，内存占用均衡
- vector：连续内存，但扩容时需要整体拷贝
- list：无需扩容，但内存不连续且额外指针开销
2.2 核心接口详解
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| push(x) | O(1) | 将x压入栈顶，等同于emplace(x) |
| pop() | O(1) | 移除栈顶元素（不返回该元素！必须先调用top()获取） |
| top() | O(1) | 返回栈顶元素的引用（可修改栈顶值：s.top() = 10;） |
| size() | O(1) | 返回当前元素数量（返回类型为size_t，注意与有符号整数的比较问题） |
| empty() | O(1) | 判断是否为空（比size() == 0更直观） |
| emplace() | O(1) | 直接构造元素，避免拷贝：s.emplace(1, "abc")而非push(MyClass(1, "abc")) |
2.3 典型错误防范
- 空栈访问：调用top()或pop()前必须检查empty()
// 错误示范 std::stack<int> s; s.pop(); // 未定义行为！ // 正确做法 if (!s.empty()) { s.pop(); }- 误用pop()返回值：C++中pop()返回void，需先top()再pop()
// 错误示范 int val = s.pop(); // 编译错误！ // 正确做法 int val = s.top(); s.pop();3. Queue的深度使用解析
3.1 容器选择策略
queue默认使用deque，也可基于list实现：
queue<int, list<int>> q; // 推荐使用list为什么不建议用vector？
- vector的pop_front()需要移动所有元素，时间复杂度O(n)
- deque和list的pop_front()都是O(1)
3.2 关键接口对比
| 操作 | stack版本 | queue版本 | 差异说明 |
|---|---|---|---|
| 插入 | push(x) | push(x) | stack在栈顶，queue在队尾 |
| 删除 | pop() | pop() | stack删栈顶，queue删队头 |
| 访问 | top() | front() | queue额外提供back()访问队尾 |
| 构造插入 | emplace() | emplace() | 两者用法相同 |
3.3 线程安全注意事项
标准库的queue不是线程安全的！多线程环境下需要额外同步：
#include <mutex> std::queue<int> msg_queue; std::mutex mtx; // 生产者线程 void producer() { std::lock_guard<std::mutex> lock(mtx); msg_queue.push(42); } // 消费者线程 void consumer() { std::lock_guard<std::mutex> lock(mtx); if (!msg_queue.empty()) { int msg = msg_queue.front(); msg_queue.pop(); } }4. 经典算法实战
4.1 最小栈（LeetCode 155）
设计一个支持push、pop、top操作，并能常数时间检索最小元素的栈。
解决方案：使用辅助栈同步记录最小值
class MinStack { stack<int> data_stack; stack<int> min_stack; // 栈顶始终为当前最小值 public: void push(int val) { data_stack.push(val); if (min_stack.empty() || val <= min_stack.top()) { min_stack.push(val); } } void pop() { if (data_stack.top() == min_stack.top()) { min_stack.pop(); } data_stack.pop(); } int top() { return data_stack.top(); } int getMin() { return min_stack.top(); } };4.2 用队列实现栈（LeetCode 225）
仅使用队列的基本操作实现栈。
技巧：在每次push后反转队列顺序
class MyStack { queue<int> q; public: void push(int x) { q.push(x); // 将前n-1个元素移到队尾 for (int i = 1; i < q.size(); ++i) { q.push(q.front()); q.pop(); } } int pop() { int val = q.front(); q.pop(); return val; } int top() { return q.front(); } bool empty() { return q.empty(); } };4.3 二叉树的层序遍历（LeetCode 102）
使用队列实现BFS：
vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> result; if (!root) return result; queue<TreeNode*> q; q.push(root); while (!q.empty()) { int level_size = q.size(); vector<int> current_level; for (int i = 0; i < level_size; ++i) { TreeNode* node = q.front(); q.pop(); current_level.push_back(node->val); if (node->left) q.push(node->left); if (node->right) q.push(node->right); } result.push_back(current_level); } return result; }5. 性能优化与底层原理
5.1 内存分配策略
deque：分段连续存储，由多个固定大小的数组块组成
- 优点：扩容时只需新增块，无需移动现有数据
- 缺点：迭代器比vector复杂，内存局部性稍差
list：双向链表结构
- 优点：无需连续内存，插入删除都是O(1)
- 缺点：额外指针开销，缓存不友好
5.2 时间复杂度对比
| 操作 | vector实现 | deque实现 | list实现 |
|---|---|---|---|
| push | O(1)均摊 | O(1) | O(1) |
| pop | O(1) | O(1) | O(1) |
| 随机访问 | O(1) | O(1) | O(n) |
5.3 自定义内存分配器
对于高频操作场景，可自定义分配器提升性能：
#include <memory_resource> std::pmr::monotonic_buffer_resource pool; std::pmr::polymorphic_allocator<int> alloc(&pool); // 使用自定义分配器的栈 std::stack<int, std::pmr::deque<int>> s(alloc);6. 工业级应用案例
6.1 线程池任务调度
class ThreadPool { queue<function<void()>> tasks; mutex queue_mutex; condition_variable cv; vector<thread> workers; public: ThreadPool(size_t threads) { for (size_t i = 0; i < threads; ++i) { workers.emplace_back([this] { while (true) { function<void()> task; { unique_lock<mutex> lock(queue_mutex); cv.wait(lock, [this] { return !tasks.empty(); }); task = move(tasks.front()); tasks.pop(); } task(); } }); } } void enqueue(function<void()> task) { { unique_lock<mutex> lock(queue_mutex); tasks.push(move(task)); } cv.notify_one(); } };6.2 游戏中的事件系统
struct GameEvent { enum Type { COLLISION, UI_EVENT, ACHIEVEMENT }; Type type; time_t timestamp; // 事件数据... }; class EventSystem { queue<GameEvent> events; priority_queue<GameEvent> delayed_events; public: void pushEvent(GameEvent&& event) { if (event.timestamp <= current_time()) { events.push(move(event)); } else { delayed_events.push(move(event)); } } void processEvents() { while (!events.empty()) { dispatchEvent(events.front()); events.pop(); } while (!delayed_events.empty() && delayed_events.top().timestamp <= current_time()) { events.push(delayed_events.top()); delayed_events.pop(); } } };7. 进阶技巧与陷阱规避
7.1 迭代器失效问题
stack和queue本身不提供迭代器，但底层容器可能产生失效：
std::stack<int, std::vector<int>> s; s.push(1); auto* vec = &s.c; // 获取底层vector的引用 vec->insert(vec->begin(), 0); // 破坏栈结构！7.2 异常安全保证
STL操作提供以下异常保证：
- push/emplace：强异常保证（操作失败则完全回滚）
- pop：不抛出异常（C++标准强制要求）
- top/front/back：无异常（仅返回引用）
7.3 自定义比较函数（优先队列）
虽然不属于标准queue，但priority_queue常与queue配合使用：
auto cmp = [](const Task& a, const Task& b) { return a.priority < b.priority; }; priority_queue<Task, vector<Task>, decltype(cmp)> pq(cmp);8. 现代C++的最佳实践
8.1 使用emplace避免拷贝
struct Point { int x, y; }; std::stack<Point> s; s.push({1, 2}); // 构造临时对象+拷贝 s.emplace(1, 2); // 直接在栈上构造8.2 移动语义优化
std::string prepare_data(); std::stack<std::string> stack; // 低效做法 std::string data = prepare_data(); stack.push(data); // 拷贝 // 高效做法 stack.push(prepare_data()); // 移动构造8.3 C++17的节点操作
虽然stack/queue不直接支持，但底层容器可进行节点操作：
std::stack<int, std::list<int>> s1, s2; s1.push(42); // 转移元素所有权（无拷贝） auto node = s1.c.extract(s1.top()); // 获取底层list的节点 s2.push(std::move(node.value()));
