C++ 核心数据结构：Stack 与 Queue 类深度解析
std::stack 和 std::queue 是 C++ 标准库中非常重要的容器适配器（Container Adapter）。它们不自己存储数据，而是基于其他容器（默认是 std::deque）进行二次封装，提供受限的接口，实现“后进先出”（LIFO）和“先进先出”（FIFO）的语义。
理解它们是掌握 C++ 容器体系、算法应用、面试题（如括号匹配、层次遍历）的关键。
一、核心概念对比
| 特性 | std::stack | std::queue |
|---|---|---|
| 逻辑语义 | 栈（LIFO） | 队列（FIFO） |
| 默认底层容器 | std::deque<T> | std::deque<T> |
| 主要操作 | push、pop、top | push、pop、front、back |
| 能否随机访问 | 不支持 | 不支持 |
| 时间复杂度（核心操作） | O(1) | O(1) |
| 空间复杂度 | O(n) | O(n) |
| 线程安全 | 非线程安全 | 非线程安全 |
| 头文件 | <stack> | <queue> |
二、std::stack 深度解析
1. 模板定义
template<
class T,
class Container = std::deque<T>
> class stack;2. 核心成员函数（C++11/17/20 完整版）
| 函数 | 作用 | 时间复杂度 | 异常安全 | 说明 |
|---|---|---|---|---|
push(const T&) | 入栈（拷贝） | O(1) | 强异常安全 | C++11 前主要方式 |
push(T&&) | 入栈（移动） | O(1) | 强异常安全 | 推荐使用 |
emplace(Args&&...) | 原地构造入栈 | O(1) | 强异常安全 | C++11 最推荐，避免拷贝/移动 |
pop() | 出栈（不返回元素） | O(1) | noexcept | 经典设计：不返回值，需先 top() |
top() | 访问栈顶元素 | O(1) | noexcept | 返回引用，可修改 |
empty() | 是否为空 | O(1) | noexcept | |
size() | 元素个数 | O(1) | noexcept | |
swap(stack&) | 交换两个栈 | O(1) | noexcept | C++11 新增 |
3. 为什么默认底层是 deque 而不是 vector？
vector在尾部push_back虽然摊销 O(1)，但扩容时会拷贝所有元素。deque是双端队列，两端操作都是 O(1)，且内存块式管理，扩容代价更低。- 栈只需要尾部操作，但
deque提供了更优的内存行为。
推荐写法（现代 C++）：
std::stack<int> s; // 默认 deque
std::stack<int, std::vector<int>> s2; // 自定义底层三、std::queue 深度解析
1. 模板定义
template<
class T,
class Container = std::deque<T>
> class queue;2. 核心成员函数
| 函数 | 作用 | 时间复杂度 | 说明 |
|---|---|---|---|
push(const T&) / push(T&&) | 入队（队尾） | O(1) | |
emplace(Args&&...) | 原地构造入队 | O(1) | 强烈推荐 |
pop() | 出队（队头） | O(1) | 不返回值 |
front() | 访问队头元素 | O(1) | 只能读写队头 |
back() | 访问队尾元素 | O(1) | 只能读写队尾 |
empty() / size() | 判断空 / 大小 | O(1) | |
swap(queue&) | 交换两个队列 | O(1) |
注意：queue 不提供 top()，而是 front() 和 back()。
四、实战代码示例
1. 使用 stack 实现括号匹配（经典面试题）
bool isValid(std::string s) {
std::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();
}2. 使用 queue 实现二叉树层次遍历（BFS）
std::vector<std::vector<int>> levelOrder(TreeNode* root) {
std::vector<std::vector<int>> result;
if (!root) return result;
std::queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int size = q.size();
std::vector<int> level;
for (int i = 0; i < size; ++i) {
TreeNode* node = q.front(); q.pop();
level.push_back(node->val);
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
result.push_back(level);
}
return result;
}3. 自定义底层容器示例
// 用 vector 实现 stack（空间更紧凑）
std::stack<int, std::vector<int>> stk_vec;
// 用 list 实现 queue（频繁中间删除场景）
std::queue<int, std::list<int>> q_list;五、重要设计哲学与注意事项
- pop() 不返回值
这是 C++ 容器适配器最经典的设计之一：分离修改和访问，保证异常安全（如果返回引用，pop 时可能抛异常导致元素丢失）。 - emplace vs push
emplace是 C++11 引入的重大改进，能在容器内原地构造，避免不必要的拷贝/移动，性能更好。 - 底层容器选择建议
- 绝大多数情况：保持默认 deque（综合最佳）
- 内存极致敏感 + 只在尾部操作 →
vector - 需要频繁在中间删除 →
list（极少使用）
- 线程安全
标准库的 stack/queue 非线程安全。多线程环境下需自行加锁，或使用第三方并发队列（如 TBB、moodycamel::ConcurrentQueue）。
六、扩展：priority_queue（优先队列）
虽然不是本次主题，但常与 queue 一起出现：
- 默认是大顶堆（
std::less） - 支持自定义比较器
- 底层默认也是
std::vector
std::priority_queue<int> maxHeap; // 大顶堆
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap; // 小顶堆总结口诀：
- Stack：只关心栈顶（
top + push + pop） - Queue：只关心队头和队尾（
front + back + push + pop） - 优先使用
emplace，理解 pop 不返回值的设计哲学 - 默认 deque 最稳，需要极致优化时再换底层
如果你想继续深入以下任意方向，请告诉我：
std::deque底层实现原理（分块数组）- 手写一个线程安全的
ConcurrentStack priority_queue完整详解 + TopK 应用- Stack/Queue 在算法题中的高频技巧
- C++23 新增的相关特性
随时说，我继续展开！
