C++的Stack和Queue，说实话是STL里最容易被低估的一组容器。学完vector和list之后，很多人觉得栈和队列就是“不给我迭代器、只能push/pop的简化容器”，但真到了算法题和工程里，函数调用栈、括号匹配、浏览器前进后退、任务调度、BFS层序遍历，背后全是这两个东西在工作。这篇指南我打算从底层容器适配器的机制讲起，把stack和queue的接口差异、底层容器选型、常见误用和经典实战全部过一遍，从基础夯实一路写到能随手写出单调栈和层序遍历。内容适合刚学完STL基础的同学，也适合想补容器细节的中级开发者，读完之后你会发现自己对“接口受限”这件事有了完全不同的理解。
1. 基础夯实：Stack与Queue的本质是什么
1.1 Stack：后进先出的世界
栈（Stack）是一种操作受限的线性表，只允许在同一端进行插入和删除操作。这一端叫栈顶（top），另一端叫栈底。元素的进出顺序是后进先出（LIFO，Last In First Out）。
生活里最常见的类比就是叠盘子：你最后放上去的盘子，第一个被拿走；最先放进去的盘子反而压在最底下。如果你把一摞书从第一本放到第五本，想拿到第一本就必须先把上面四本全部移开。这个“只能从一端操作”的约束，恰恰构成了栈的独特价值。
在计算机世界里，栈无处不在。函数调用栈是栈，递归过程中每进入一层函数就把返回地址和局部变量压栈，函数结束再弹出；很多虚拟机的字节码执行模型也是栈式结构；浏览器的返回功能本质上也是维护了一个“访问历史栈”；编辑器里的undo操作同样是栈。理解了LIFO，你就理解了这些场景的底层逻辑。
栈的核心操作其实只有两个：压入（push）和弹出（pop）。另外还需要能查看栈顶元素（top）、判断是否为空（empty）、获取元素个数（size）。注意栈没有“查看栈底”的操作，也没有从中间取元素的操作——这是它和vector、list最大的区别。
1.2 Queue：先进先出的世界
队列（Queue）同样是操作受限的线性表，但它的规则和我们平时排队买票一样：新来的人站到队伍末尾（队尾），离开的人永远从队伍最前面走（队头）。元素的进出顺序是先进先出（FIFO，First In First Out）。
队列的术语有两个容易混淆的端点：队头（front）和队尾（back）。插入操作叫入队（push），发生在队尾；删除操作叫出队（pop），发生在队头；查看当前活跃元素是查看队头（front）；如果你想看队尾刚刚入队的元素，用back。
队列在系统设计里的地位非常高。消息队列是队列，任务调度器是队列，事件循环里的待处理事件也是队列。广度优先搜索（BFS）依赖队列来逐层扩展节点，这个会在后面的实战部分展开。很多人在学BFS时没想明白一个问题：为什么BFS要用队列而不是栈？因为BFS要求“先进入的节点先被访问”，自然映射到FIFO语义。
1.3 容器适配器：误解的起点
理解stack和queue的关键，在于认识到它们并不是真正的“容器”，而是容器适配器（Container Adapters）。
什么是适配器？用一句话解释：适配器是一个包装层，它把一个容器包装成另一个接口。底层仍然是真正的存储结构，只不过适配器只对外暴露一组受限的接口。你把vector包装成栈，用户就看不到push_back、pop_back、insert这些泛化操作，只能看到push、pop、top这几个栈语义的操作。
标准库中，stack和queue默认的底层容器都是deque（双端队列）。当然这不是绝对的，你可以通过模板参数更换底层容器，比如：
std::stack<int, std::vector<int>> st1; // 用vector做栈的底层 std::stack<int, std::list<int>> st2; // 用list做栈的底层 std::queue<int, std::list<int>> q1; // 用list做队列的底层值得特别强调的是：queue不能用vector作为底层容器，因为vector没有pop_front操作。stack可以用vector、deque、list，因为栈只需要在一端操作；queue需要队头出队，所以底层容器必须支持pop_front，deque和list满足条件，vector不满足。这个限制不是“编译报错说语义不对”，而是vector缺少成员函数导致编译失败，很多人第一次接触时容易懵。
2. 核心接口与实操要点
2.1 Stack的接口速查与使用禁忌
std::stack的标准接口不多，但每个都有讲究。列一张速查表：
| 接口 | 作用 | 注意事项 |
|---|---|---|
| push(x) | 入栈，把x放到栈顶 | C++11后与emplace相比会多一次拷贝/移动 |
| emplace(args...) | 原地构造元素入栈 | 比push更高效，适合复杂类型 |
| pop() | 弹出栈顶元素 | 不返回被删除元素，这点非常反直觉 |
| top() | 返回栈顶元素引用 | 空栈调用是未定义行为 |
| empty() | 判断栈是否为空 | 循环pop前务必检查 |
| size() | 返回元素个数 | 某些实现下O(1)，但别依赖性能差异 |
最容易踩的坑就是pop()和top()的配合。很多人刚从vector思维转到stack，会惯性写成st.pop()然后还想拿到被弹出的值，但C++的栈设计里pop()的返回类型是void，它只负责删除元素。你必须在pop之前先用top()拿到引用：
int val = st.top(); // 先取 st.pop(); // 再删为什么要这样设计？这涉及一个异常安全问题。如果pop()直接返回元素，返回值涉及一个临时对象的构造/拷贝，而这发生在元素从容器中移除之前还是之后？若先拷贝元素再删除，拷贝过程抛出异常，导致元素丢失；若先删除再返回，元素已经没了。C++选择了“没有异常风险”的路径：pop只负责删除，top负责读取，两者分离。这是标准库设计反复权衡的结果，值得记住。
另一个坑是空栈调用top()或pop()造成未定义行为。标准库不检查空栈，它默认调用者保证栈非空。程序可能不崩、可能崩溃、可能弹出奇怪的数据，全看运气。正确姿势是：
if (!st.empty()) { int val = st.top(); st.pop(); }2.2 Queue的接口速查与常见误读
std::queue的接口比stack多一个front/back的概念，但缺了top。速查表：
| 接口 | 作用 | 注意事项 |
|---|---|---|
| push(x) | 入队，放到队尾 | 和stack一样，push有emplace优化空间 |
| emplace(args...) | 原地构造元素入队 | 优先使用，尤其对象类型 |
| pop() | 出队，删除队头元素 | 同样不返回被删元素 |
| front() | 返回队头元素引用 | 空队列未定义行为 |
| back() | 返回队尾元素引用 | 同样注意空队列 |
| empty() | 判断队列是否为空 | BFS循环里的常规守卫 |
| size() | 返回元素个数 | O(1)由标准保证 |
Queue常见的理解错位是：有人把front和top混用。stack里查看当前活跃元素叫top，queue里叫front，这不是同一个概念。还有，很多人会下意识地认为queue支持遍历，但容器适配器不提供begin()和end()，你不能用范围for遍历一个queue。
实际上，适配器不暴露迭代器是有意为之。适配器的意义是“隐藏底层容器的全部非必要接口，保证只能按栈或队列的语义操作”。如果你需要遍历一个队列的当前内容，说明你选错了数据结构——应该直接使用deque或者list，而不是queue。
2.3 底层容器的选择策略
默认用deque是因为deque在两端操作都是常数时间，且内存管理比list更紧凑。但如果对性能有极致要求，或者有特殊场景，需要手动换底层容器。
做一个对比：
| 底层容器 | 适合包装成 | 优点 | 缺点 |
|---|---|---|---|
| vector | stack | 内存连续，缓存命中率高；扩容有均摊O(1) | 栈顶是vector末尾，没问题；不适合queue |
| deque | stack / queue | 两端O(1)操作；内存分段，随机访问O(1) | 缓存局部性略差于vector；中间插入性能差 |
| list | stack / queue | 无扩容搬迁；不需要连续内存 | 每个节点额外指针开销；缓存不友好；老实现size()可能O(n) |
实测下来，如果只是做一个普通的栈结构，用vector做底层往往比deque更快，因为vector的连续内存对CPU缓存非常友好，即使扩容时发生搬移，均摊后还是划算的。而deque为了保证两端都能伸缩，采用分块结构，每次访问要多一次指针跳转，有少量额外开销。
但工程上我一般还是用默认的deque，原因很简单：接口语义清晰，代码可读性好，绝大多数场景的性能差异在几百纳秒级别，根本影响不了业务。只有当性能剖析明确显示栈操作是瓶颈时，才会考虑换成vector。
3. 高级玩法：从原理到核心实战
3.1 用Stack实现括号匹配
括号匹配是栈最经典的应用场景：编译器在语法分析阶段检查括号是否成对、顺序是否正确。思路非常直观：遇到左括号就入栈，遇到右括号就检查栈顶是否是对应的左括号，是则弹出，不是则直接报错。遍历结束后，如果栈不为空，说明有左括号没有闭合。
bool isValid(const 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 topCh = st.top(); if ((c == ')' && topCh != '(') || (c == ']' && topCh != '[') || (c == '}' && topCh != '{')) { return false; } st.pop(); } } return st.empty(); }这个实现里有个小细节：只用字符本身的ASCII关系也能判断，比如右括号的ASCII码比对应左括号大1或2，但可读性差。我更喜欢显式的switch或if判断，代码一眼能看懂。时间复杂度O(n)，空间复杂度O(n)，n为字符串长度。
括号匹配非常适合用来理解“栈顶即最近未匹配元素”这个本质。你遇到的每一个右括号，最需要匹配的一定是最近一个未匹配的左括号——这正好是栈顶的含义。这就是为什么栈是解决嵌套问题的天然工具。
3.2 用Queue实现二叉树的层序遍历
二叉树层序遍历，又称广度优先遍历，要求按层从上到下、从左到右输出节点。这个过程的核心就是队列。根节点先入队，然后循环：每轮记录当前队列大小，这个大小就是当前层的节点数；从队头拿出节点、访问，再把它的左右孩子分别入队。
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 levelSize = q.size(); std::vector<int> level; for (int i = 0; i < levelSize; ++i) { TreeNode* cur = q.front(); q.pop(); level.push_back(cur->val); if (cur->left) q.push(cur->left); if (cur->right) q.push(cur->right); } result.push_back(level); } return result; }注意这里为什么要先把q.size()存到levelSize，而不用i < q.size()？因为循环过程中会有新的节点不断入队，q.size()是动态变化的。如果直接写for (int i = 0; i < q.size(); ++i)，每一轮循环都会重新计算size，导致一层遍历时把下一层刚入队的节点也一起弹出，层就分不清了。这个细节点在面试中经常出现，建议记牢。
这种“按层取size”的写法还有一个通用价值：它不仅适用于二叉树，也适用于图的多源BFS、状态空间的按层搜索。凡是需要知道“当前层有多少个节点”的场景，都可以用这个模板。
3.3 用Stack实现逆波兰表达式求值
逆波兰表达式又称后缀表达式，把运算符写在操作数后面，例如"2 1 + 3 *"等价于(2 + 1) * 3。求值时遇到数字就入栈，遇到运算符就弹出两个操作数计算结果，再把结果压回栈。运算结束后栈顶就是最终结果。
int evalRPN(std::vector<std::string>& tokens) { std::stack<int> st; for (const std::string& t : tokens) { if (t == "+" || t == "-" || t == "*" || t == "/") { int b = st.top(); st.pop(); int a = st.top(); st.pop(); if (t == "+") st.push(a + b); else if (t == "-") st.push(a - b); else if (t == "*") st.push(a * b); else st.push(a / b); } else { st.push(std::stoi(t)); } } return st.top(); }这里有两个实操细节值得强调。第一，先弹出的b是右操作数，后弹出的a是左操作数。减法a-b和除法a/b都有顺序，写反了结果就错了。因为栈是LIFO，"2 1 -"里先弹出1，后弹出2，对应计算是2 - 1，不是1 - 2。第二，除法在C++中向零截断，而逆波兰表达式的语义通常也要求向零截断，这里直接用a / b是符合语义的，不需要额外处理。
逆波兰表达式求值最让我喜欢的点是：它把“栈的临时存储作用”展现得淋漓尽致。操作数先来，但不知道它何时会被使用，所以暂存在栈里；一旦遇到运算符，就要从栈里取出最近的两个操作数。这种“延迟等待、近者优先”的机制，是栈的天然属性。
3.4 进阶技巧：单调栈与单调队列
单调栈解决的是“找左边或右边第一个比当前元素大/小的元素”这类问题。以“每个元素右边第一个更大的元素”为例，核心思路是维护一个从栈底到栈顶递减的栈。遍历数组时，如果当前元素比栈顶元素大，说明当前元素就是栈顶元素的“下一个更大元素”，弹出栈顶并记录答案；然后把当前元素下标入栈，继续比较。
std::vector<int> nextGreaterElement(const std::vector<int>& nums) { int n = nums.size(); std::vector<int> res(n, -1); std::stack<int> st; // 存下标 for (int i = 0; i < n; ++i) { while (!st.empty() && nums[st.top()] < nums[i]) { res[st.top()] = nums[i]; st.pop(); } st.push(i); } return res; }单调栈的复杂度是O(n)，因为每个元素最多入栈一次、出栈一次。暴力解法是O(n^2)。理解单调栈的关键在于：为什么是“单调”？因为栈中保留下来的元素都是当前尚未找到答案的候选者，且越靠近栈顶的元素越“新”。当新元素到达时，所有比它小的候选者都会被它“解决”，这正好让栈维持了一个单调的顺序。
单调队列常用于滑动窗口类问题，例如求窗口内的最大值。维护一个从队头到队尾递减的双端队列，队列中存的是下标。每次窗口右移，先移除队头已经滑出窗口的下标，然后从队尾弹出所有值小于等于当前元素的下标，再把当前元素下标入队。这样队头始终是当前窗口的最大值。
std::vector<int> maxSlidingWindow(const std::vector<int>& nums, int k) { std::deque<int> dq; // 存下标，队头到队尾递减 std::vector<int> res; for (int i = 0; i < (int)nums.size(); ++i) { if (!dq.empty() && dq.front() <= i - k) dq.pop_front(); while (!dq.empty() && nums[dq.back()] <= nums[i]) dq.pop_back(); dq.push_back(i); if (i >= k - 1) res.push_back(nums[dq.front()]); } return res; }这里用的是std::deque而不是std::queue，原因是我们既要操作队头也要操作队尾。这正是deque和queue的微妙关系：queue是deque的受限版本，当队列语义无法满足需求时，应该果断换成deque。这个例子也提醒我，不要为了“用某个容器”而强行使用适配器，工具终究要为场景服务。
4. 常见问题与排查技巧实录
4.1 top()和pop()的配合失误
我在帮别人review代码时，不止一次看到这样的写法：
int val = st.top(); st.pop(); // 然后又想用val这本身没问题，正确。更多的问题出在另一种：
st.pop(); int val = st.top(); // 想取刚被删掉的那个元素，已经来不及了如果你调用了pop()再去top()，取到的是新的栈顶元素，逻辑完全错乱。还有一种更隐蔽的：先持有了top()返回的引用，再pop()，然后还使用这个引用。top()返回的是容器内元素的引用，pop()会销毁该元素，这个引用就悬空了，产生未定义行为。
正确的顺序一定是“先top拷贝，再pop删除”。如果想删除并处理所有元素，正确的循环是：
while (!st.empty()) { int val = st.top(); st.pop(); // 处理val }4.2 空容器上调用top/front的灾难
空栈上调用top()、空队列上调用front()，都是未定义行为，但系统不会提醒你。有时候程序“碰巧”没崩，你根本发现不了问题，直到堆上被破坏或者某次运行返回了一个巨大的随机数字，排查起来极费时间。
我自己的经验是，凡是在循环里频繁调用top()/front()的地方，一律先写empty判断。不要相信“队列刚开始肯定非空”“栈里肯定还有元素”这种直觉。特别是场景涉及条件分支、输入有时为空时，防御性判断成本极低，收益极高。
提示：在使用容器适配器时，把“先判断empty，再访问front/top”当成类似“开文件要检查是否打开成功”的习惯来培养。
4.3 容器适配器无法遍历
stack、queue都没有begin()和end()，所以不能直接对它们进行范围for循环或使用任何迭代器算法。想要查看队列的全部内容时，最直接的办法是改用deque或list。如果一定要保留queue接口，可以声明时换底层容器，但访问底层容器成员c是受保护的，标准并未提供合法访问路径。
这其实是一个很好的“提醒信号”：当你发现自己需要遍历一个栈或队列时，意味着你的数据结构选择可能不合适。栈和队列的定位是“按特定顺序存取元素”，遍历本身违背了它们的语义。我在工程中见过不少人用queue存了一批任务，后来又需要统计中间某个值，硬生生在queue里翻找，最终代码越写越乱。后来我们把数据换成deque，再用队列语义包了一层接口，才彻底理清。
4.4 性能与内存的隐忧
stack和queue的性能完全取决于底层容器。默认deque的好处是两端操作复杂度都是常数级，且不像vector扩容那样频繁搬移大量数据。但deque的分块设计意味着一次元素访问要经过“定位到块”和“块内偏移”两步，对CPU缓存不够友好。
我自己做过简单压力测试（数据量级为1000万次push/pop），vector底层的stack比deque底层快10%左右，list底层则慢出一倍多。队列场景下，deque底层的queue比list底层的queue快，因为list的节点分配次数多、内存碎片化。这些数据在不同机器上会有波动，但趋势稳定。
需要注意的一点是：如果隐式使用了list作为底层（某些人为了“稳定迭代器”选择了list），在个别旧版本标准库实现中，size()可能不是O(1)。C++11之后标准才明确要求O(1)，但早期实现确实有O(n)的，意味着频繁调用size()会拖慢整体。
5. 实操心得与个人经验分享
5.1 我踩过的几个坑
第一个坑发生在一次处理日志事件的模块里。我用queue缓存待写入的事件，然后在另一个线程消费。当时的代码在消费时不判断empty就直接pop，偶发崩溃。问题是consumer线程和producer线程的竞争导致队列短暂为空，崩溃极难复现。后来加锁之前先empty判断，确认问题出自空队列的未定义访问。
第二个坑和引用失效有关。我用stack存任务对象，某段代码先拿了task = st.top()的引用，然后调用了另一个函数往同一个栈里继续push，之后又用这个引用。push导致底层容器扩容，引用失效，数据全部变成垃圾值。从那以后我凡是取栈顶元素做业务逻辑，一律拷贝出来，不保留引用。
第三个坑是在一个消息中间件的模拟场景里。我用queue做消息列表，后来需求变成“支持高优先级消息插到队首”，发现queue根本做不到，只能换成deque。换成deque后，又发现原本用queue时写死的front/back接口需要改。这点提醒我：如果功能需求里有高频“特殊入口”操作，一开始就不要用queue。
5.2 关于刷题与面试的实用建议
算法面试里栈和队列是高频考查点，除了括号匹配、逆波兰表达式、层序遍历这类基础题，单调栈几乎是“下一个更大元素”所有变体题的标准解法。我的建议是先把基础接口练熟，尤其是pop/top配合、循环控制size这类细节，再过渡到单调栈、单调队列、拓扑排序、循环队列等进阶课题。
如果你在准备竞赛或大量刷题，可以考虑直接用数组模拟栈和队列，比如用一个int stk[N]加一个int topIndex。数组模拟的好处是免去STL封装带来的函数调用开销和debug复杂度，在数据量极大、时间卡得很紧时非常实用。多数时候STL足够，但能写出数组模拟的版本，对底层行为的理解也更清晰。
5.3 工程上的选型参考
工程代码里，我一般遵循以下选型习惯：任务处理类、消息流类、BFS类问题，直接用std::queue，简单直观；需要同时从两端操作或频繁查看队尾，用std::deque；撤销历史、表达式求值、递归转非递归，用std::stack；需要遍历队列所有元素或稳定访问中间元素，则回到vector或list，不要为了“用适配器”而勉强自己。
另一个经验是：在涉及多线程共享队列的场景，std::queue本身没有线程安全保证，加锁才是核心。我见过很多人在并发时反复纠结该用lock还是lockfree队列，忽略了std::queue本身不保证并发安全这一前提。并发队列用锁保护是最稳的起点，性能不足时再做无锁队列优化，不要一上来就上复杂结构。
最后再分享一个小技巧：如果你需要在栈/队列的调试中快速查看内容，最省事的办法是临时把底层容器类型换掉，因为声明一个std::stack<int, std::vector<int>> st以后，虽然容器成员是protected的，但你可以通过继承来暴露它，比如class DebugStack : public std::stack<int, std::vector<int>> { public: using std::stack<int, std::vector<int>>::c; };。这是非标准的hack，只建议用来调试，不建议留在生产代码里。常规项目里我更推荐直接开日志或者使用调试器观察内存，省心。
