★ FEATURED ARTICLE 这几年在项目里写底层模块我发现很多人对数据结构的第一反应是“背模板题”但真到了业务代码里最该被认真对待的反而是那些看起来最简单的东西。比如 C 里的 Stack 和 Queue——两个容器适配器接口少得可怜可一旦用对场景能把代码从“一团乱麻”整理成“一眼就能看懂的状态机”。这篇文章我打算把 std::stack 和 std::queue 从头到尾拆一遍先讲清楚它们为什么是容器适配器、底层到底怎么选再把所有基础操作按 API 地图捋一遍接着进入正题用括号匹配、后缀表达式求值、单调栈、BFS 遍历和滑动窗口最大值这几个经典场景带你逐步上手最后配几道能直接练手的实战习题和一份我自己踩坑后的排查清单。无论你是 C 新手还是想查漏补缺的老手这篇都值得当成随查随用的手册。1. 核心机制拆解为什么 Stack 和 Queue 是容器适配器1.1 适配器模式在 STL 中的体现先纠一个常见的认知偏差std::stack 和 std::queue 并不是独立的数据存储结构而是容器适配器。什么意思它们不自己管理内存而是把你指定的底层容器默认是 std::deque包一层暴露出一套受限的接口。这种设计有两个直接好处。第一存储实现可以随意替换业务代码不需要动第二接口被刻意收敛使用方不容易写出违背语义的操作。对比一下就明白了// 直接用 deque 的时候你能干的事情太多随机访问、遍历、任意位置插入 std::dequeint dq; dq.push_back(1); dq.push_front(2); dq[0] 100; // 随手就改了 // 包成 stack 之后你能碰的接口就那么几个 std::stackint st; st.push(1); st.push(2); // st[0] 100; // 编译错误stack 不提供随机访问很多人觉得“接口越少越不方便”但真实工程里接口少就是一份“约束契约”。团队成员看到 stack就知道这地方只做后进先出不会有人无意识地在中间位置乱插数据。这个约束的价值远大于少写几个 API 的那点便利。1.2 底层容器默认 deque但可以换成 vector 或 list默认模板参数值得注意templateclass T, class Container std::dequeT class stack; templateclass T, class Container std::dequeT class queue;默认用 deque是因为 stack 和 queue 极度依赖两端操作而 deque 在两端的插入和删除都是均摊常数时间同时内存比 list 紧凑得多。但默认不等于最优。我做过的几组压测对比大概这样底层容器stack 场景queue 场景建议deque两端操作均摊 O(1)随机访问 O(1)两端操作均摊 O(1)默认选择通用性最好vector尾部 push/pop 均摊 O(1)扩容时有拷贝/搬移开销队首 pop 是 O(n)非常差栈深度可预测时优先考虑list任意位置插入删除 O(1)但每个节点额外开销大两端操作 O(1)但缓存不友好元素很大、需要稳定迭代器时考虑如果你能预估栈的最大深度把底层容器换成 vector 通常能减少内存碎片也能利用 vector 的连续内存提升缓存命中率。写法很简单std::stackint, std::vectorint st; st.push(1); st.push(2); // 底层扩容策略和 vector 保持一致反过来如果元素是体积很大的对象vector 扩容时的搬移成本不可忽略这时 list 反而更稳。不过绝大多数场景下默认的 deque 就是最平衡的选择这一点可以放心。1.3 为什么 stack 和 queue 没有迭代器有朋友问过我既然底层容器有迭代器适配器为什么不暴露出来这正是适配器的关键设计之一它们不提供迭代器所以彻底禁止了“从中间访问”的可能性。stack 只能操作栈顶queue 只能操作队首和队尾。一旦开放迭代器你就可以从中间遍历和修改“后进先出”“先进先出”的语义就名存实亡。标准库用接口层面的限制来强制约束而不是靠程序员自觉这是很成熟的做法。1.4 自定义类型与比较规则stack 和 queue 都能容纳自定义类型但如果你要用它们提供的、等比较运算符自定义类型必须重载相应的比较逻辑。这里有个常见坑两个 stack 比较时实际是逐元素对比底层容器如果你存的自定义类型没写operator模板展开时会吐出一大串难懂的编译错误。所以自己封装类型时提前把比较运算符补齐后面会省很多事。2. 基础操作全梳理从构造到容器替换的完整 API 地图2.1 头文件与构造方式使用前分别包含头文件#include stack #include queue构造函数除了默认构造还能传入一个底层容器把已有数据直接“包”成栈或队列std::dequeint deck; deck.push_back(10); deck.push_back(20); deck.push_back(30); std::stackint st(deck); // 用 deck 初始化copy 一份 std::queueint q(deck); // 同理这种方式适合“已有序列希望用受限接口处理它”的场景比如把一个历史记录序列直接包成栈来做撤销逻辑。2.2 stack 的常用操作stack 的 API 就六个核心操作操作说明时间复杂度push(const T) / push(T)压入元素到栈顶均摊 O(1)emplace(Args...)原地构造元素省一次拷贝/移动均摊 O(1)pop()弹出栈顶元素注意不返回它O(1)top()返回栈顶元素引用O(1)empty()判断栈是否为空O(1)size()返回元素个数O(1)最容易被新手卡住的点就是pop() 不返回被弹出的元素。标准库这么做是为了避免无谓的返回值拷贝同时强迫你显式区分“看一眼栈顶”和“拿走栈顶”这两个动作。正确写法int val st.top(); st.pop();如果你存的是复杂对象emplace能省一次临时对象的创建和拷贝struct Task { int id; std::string name; Task(int i, std::string n) : id(i), name(std::move(n)) {} }; std::stackTask tasks; tasks.emplace(1, parse-config); // 原地构造不需要先 create 再 push 再析构临时对象2.3 queue 的常用操作queue 的接口和 stack 高度对称但注意用的是 front/back 而不是 top操作说明时间复杂度push(const T) / push(T)从队尾入队均摊 O(1)emplace(Args...)在队尾原地构造均摊 O(1)pop()从队首出队不返回值O(1)front()返回队首元素引用O(1)back()返回队尾元素引用O(1)empty()判断队列是否为空O(1)size()返回元素个数O(1)我确实在代码评审里见过有人把top()用在 queue 上编译器虽然会直接报错但如果反过来把front()和back()搞混那就是静默的逻辑错误了。比如你做任务调度从队尾拿任务当队首处理倒霉的是排在队列最前面的任务永远得不到处理。2.4 元素比较与整体比较两个 stack 或两个 queue 之间可以直接使用、!、、、、。比较是按底层容器内容逐元素进行的实际对应 lexicographical_compare 规则。std::stackint a; a.push(1); a.push(2); a.push(3); std::stackint b; b.push(1); b.push(2); b.push(4); if (a b) { // 从栈底向栈顶比11, 22, 34所以 a b 成立 }这个特性在实际项目里用得不多但知道它存在就够了。遇到需要判断两个栈内容是否一致的情况我会直接转到底层容器做比较因为栈顶顺序不一定是你业务里定义的“相等”语义。2.5 swap 的隐藏价值st.swap(other)或std::swap(st, other)在底层容器类型相同的情况下是常数时间操作。它交换的是容器内部句柄不是逐个拷贝元素。我做撤销系统的时候需要频繁把“当前操作栈”和“历史缓存栈”互换这个操作让我省下了大量拷贝开销配置管理类功能里尤其好使。3. 经典场景实战与代码拆解从表达式求值到滑动窗口3.1 括号匹配stack 最典型的“配对”应用业务里解析配置文件、SQL 语句、模板语法几乎都逃不开括号配对检查。用栈可以在一次遍历内完成匹配时间复杂度 O(n)空间复杂度 O(n)。思路很简单遇到左括号入栈遇到右括号检查栈顶是否匹配匹配则弹栈不匹配直接判定失败遍历结束后栈为空才算通过。#include unordered_map bool isValidBrackets(const std::string s) { std::stackchar st; std::unordered_mapchar, char match { {), (}, {], [}, {}, {} }; for (char c : s) { if (c ( || c [ || c {) { st.push(c); } else if (c ) || c ] || c }) { if (st.empty() || st.top() ! match[c]) { return false; } st.pop(); } } return st.empty(); }为什么括号匹配非要用栈因为“最近闭合”原则天然就是 LIFO。最后遇到的左括号一定最先需要被匹配这和栈的后进先出完全对应。字符扫描类的问题一旦发现配对顺序反直觉栈往往是第一选择。3.2 后缀表达式求值栈把“运算符优先级”直接踩平后缀表达式也就是逆波兰式不需要括号也不需要优先级表因为操作数一出现就压栈遇到运算符就弹出两个数计算结果再压回去。全程只需要一个栈。#include sstream int evalRPN(const std::vectorstd::string tokens) { std::stackint st; for (const auto tok : tokens) { if (tok || tok - || tok * || tok /) { int b st.top(); st.pop(); int a st.top(); st.pop(); int r 0; if (tok ) r a b; else if (tok -) r a - b; else if (tok *) r a * b; else r a / b; // 注意除法顺序 st.push(r); } else { st.push(std::stoi(tok)); } } return st.top(); }这里最容易踩坑的就是减法和除法的操作数顺序。栈是后进先出第一个 pop 出来的是“右边的操作数”第二个 pop 出来的才是“左边的操作数”。顺序反向结果就完全错了。很多模板引擎和脚本解释器内部会把用户输入的中缀表达式先转成后缀再求值就是为了避开优先级判断那堆麻烦。理解了这段代码你就理解了计算器类需求的核心。3.3 单调栈寻找“下一个更大元素”的线性解法单调栈维护的是一个单调递增或递减的序列核心价值在于当新元素破坏了栈的单调性时你就能结算一批元素的答案。经典问题给定数组对每个元素求右边第一个比它大的元素没有则返回 -1。vectorint nextGreaterElement(const vectorint nums) { int n nums.size(); vectorint res(n, -1); stackint st; for (int i 0; i n; i) { while (!st.empty() nums[i] nums[st.top()]) { res[st.top()] nums[i]; st.pop(); } st.push(i); } return res; }时间复杂度从暴力法的 O(n²) 降到 O(n)。为什么能省时间因为栈里存的是“还没找到答案的下标”它们始终保持递减序。每遇到更大的元素就一次性把该结算的待处理下标全部处理完每个下标最多入栈出栈一次。我第一次接触这个套路时最颠覆的一点是栈里存的是下标不是元素本身。因为你要定位结果数组的位置单纯存元素值根本不够。这在 stack 的实际使用里算是一个进阶技巧也让我对“栈存什么”有了更深的理解。3.4 BFS 遍历queue 天然承载广度优先广度优先搜索的核心流程是起始节点入队反复处理队首节点并把它的未访问邻居入队。“先来先处理”的顺序正好就是 queue 的 FIFO 语义。拿二叉树层序遍历为例struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} }; vectorvectorint levelOrder(TreeNode* root) { vectorvectorint result; if (!root) return result; queueTreeNode* q; q.push(root); while (!q.empty()) { int levelSize q.size(); vectorint level; for (int i 0; i levelSize; 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; }这里有个小细节容易被忽略levelSize q.size()必须在循环前存下来。因为在循环体里 front/pop 操作会持续改变队列长度如果直接用q.size()作为循环边界当前层级会多处理后面的节点层级就会混掉。在网格寻路、社交关系扩散、状态空间搜索这类问题里BFS 配合 queue 几乎是最自然的组合。我做一个地图邻接模块时用 queue 做可达性探测几百个节点一次搜索的成本完全可控。3.5 滑动窗口最大值从 queue 思路升级到双端队列滑动窗口最大值如果直接用普通 queue 模拟窗口每次找最大值要 O(k)整体 O(nk)。用双端队列做“单调队列”可以降到 O(n)。核心思路和单调栈类似但队列维护的是窗口内的候选下标且始终从大到小排列vectorint maxSlidingWindow(const vectorint nums, int k) { dequeint dq; // 存下标对应元素保持递减 vectorint res; for (int i 0; i 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; }你可能会问这里明明写的是 deque跟 queue 有什么关系因为普通 queue 的默认底层容器就是 deque而滑动窗口需要从队尾淘汰元素所以直接用底层容器操作是合理延伸。这道题考察的其实是“队列能用来做什么”的理解深度——它不是只能 push/pop 的盒子而是一种动态维护区间候选集的工具。4. 实战习题配套训练扎扎实实练手感4.1 习题一用栈反转队列内元素的顺序题目给定一个队列元素从队首到队尾依次是 1、2、3请用辅助栈把它变成 3、2、1。思路先把队列所有元素出队并压入栈顺序自然反转再从栈顶弹出依次入队就得到反转后的队列。void reverseQueue(queueint q) { stackint st; while (!q.empty()) { st.push(q.front()); q.pop(); } while (!st.empty()) { q.push(st.top()); st.pop(); } }这道题主要练的是跨结构搬运数据。queue 从队首出stack 从栈顶入两个结构各自的语义被强制用了一遍后续做更复杂的算法题这个基础动作会出现非常多次。4.2 习题二单调栈——每日温度题目给定一个数组每天的温度值返回一个新数组每个位置表示“要等多少天才会遇到更高的温度”没有则为 0。这是“下一个更大元素”的变体答案要的是下标距离。vectorint dailyTemperatures(const vectorint temps) { int n temps.size(); vectorint res(n, 0); stackint st; for (int i 0; i n; i) { while (!st.empty() temps[i] temps[st.top()]) { int prev st.top(); st.pop(); res[prev] i - prev; } st.push(i); } return res; }写完这道题单调栈的套路基本就吃透了用下标作为栈元素当新元素破坏单调性时结算栈顶的答案。后面遇到接雨水、柱状图最大矩形思路是一脉相承的。4.3 习题三用两个栈实现一个队列这是一个非常经典的工程题。有些底层容器不支持高效的队首弹出这时候可以用两个栈拼出 FIFO 语义。思路入队直接进 in 栈出队时如果 out 栈为空就把 in 栈全部倒到 out 栈再从 out 栈顶取。每个元素最多倒腾两次均摊 O(1)。class MyQueue { private: std::stackint in, out; public: void push(int x) { in.push(x); } int pop() { if (out.empty()) { while (!in.empty()) { out.push(in.top()); in.pop(); } } int val out.top(); out.pop(); return val; } int peek() { if (out.empty()) { while (!in.empty()) { out.push(in.top()); in.pop(); } } return out.top(); } bool empty() { return in.empty() out.empty(); } };这道题的价值在于让你意识到queue 的“先进先出”不一定要物理上由首尾两个口组成用两个 LIFO 结构逻辑上也能拼出 FIFO 语义。理解到这里你对“结构”和“语义”的区分就过关了。4.4 习题四队列模拟任务调度写一个小型任务调度器任务按到达顺序排队每个任务有处理时长处理器按顺序处理求每个任务从进入到处理完成的等待时间。用 queue 维护任务队列维护一个“累计完成时间”。每处理一个任务它的完成时间就是累计时间加上本身耗时等待时间就是完成时间减到达时间。这题没有高深算法但非常贴近真实开发里的异步任务顺序处理逻辑练的是 queue 的 front/pop 组合操作和边界条件检查。5. 常见问题与排查技巧实录踩过的坑都写给你5.1 空容器上调用 top() 或 pop()未定义行为的重灾区这是 stack 和 queue 使用中最常见、后果最严重的问题。在 empty() 为 true 时调用 top() 或 pop()行为未定义轻则返回垃圾值重则直接段错误。我排查过的一个线上问题最后定位到某条异常路径上stack 已经被清空代码没检查 empty 就继续走了一次 top()。修复只要加一行判断但排查过程极其痛苦。建议在所有读操作前养成习惯先if (!st.empty())再取 top。一个实用的封装是把“拿栈顶并弹出”写成辅助函数强制检查templatetypename T bool safePop(std::stackT st, T out) { if (st.empty()) return false; out st.top(); st.pop(); return true; }5.2 头文件包含的隐性依赖std::stack需要stackstd::queue需要queue。但很多开发环境里由于某些头文件比如iostream间接包含了它们代码能编译过。一旦换编译器或调整 include 顺序立刻报错而且报错信息通常是模板展开后的一长串非常难定位。我的原则是每个源文件显式包含自己用到的每一个标准头文件不要依赖间接包含。这听起来像纪律问题实际能省掉大量编译期排查时间。5.3 size_t 与 int 的符号混用size()返回size_type通常是size_t无符号类型。和 int 直接比较会产生 signed/unsigned mismatch 警告// 如果 st.size() 大于 INT_MAX这里就是灾难 for (int i 0; i st.size(); i) { }项目规模不至于这么大但也别忽视编译器警告。养成分寸感更好的写法for (size_t i 0; i st.size(); i) { } // 或者直接用 auto5.4 底层容器选型失误导致性能劣化队列如果选了 vector 做底层队首 pop 会退化到 O(n)std::queueint, std::vectorint q; // 队首 popvector.erase(begin()) 是 O(n)元素一多延迟立刻放大。一句话总结我的经验队列默认用 deque栈如果深度可预判可以考虑 vector避免在队列场景用 vector。此外 list 的节点开销在千万级操作下也相当可观不要为了“灵活性”盲目选 list。5.5 迭代器失效问题虽然适配器不暴露迭代器但你仍可能拿到底层容器做操作。这时候记住失效规则vector 扩容后迭代器全部失效deque 两端操作时迭代器不一定失效但引用可能失效list 节点操作基本不失效。我的建议很简单不要让迭代器“活过”一次 push/pop能省一大类隐蔽问题。5.6 调试技巧用状态快照验证逻辑stack 和 queue 的内部结构不像数组那样直观调试时不容易一眼看出元素组成。我的做法是在关键节点打印empty()、size()、top()/front()/back()组成“状态快照”日志。线上修过一次撤销系统的问题靠的就是在每个操作点输出size()和top()马上发现栈被提前清空的时机。最后说几句说实话stack 和 queue 的 API十分钟就能看完真正把它们用好是另一回事。之前我做过一个配方解析模块最初用数组加一堆下标判定代码又长又容易漏边界后来改成用 stack 管理嵌套层级状态入栈、出栈的时机和配置层级一一对应整个模块从 400 行缩到不足 150 行可读性也高了一个档次。如果你现在正在学数据结构或者准备面试我的建议是别急着背题亲手把上面的括号匹配、后缀表达式、单调栈、BFS 层序遍历各写一遍运行起来再倒推每一步的入栈/出栈顺序。手感就是这么练出来的。最后再分享一个小技巧当你怀疑 stack/queue 的边界处理有问题时先在纸上画出当前容器状态图标出 top 或 front 应该指向谁再对照代码逐行检查。这方法看起来原始但比空想高效得多。如果能少让你踩几个坑这篇文章就算值了。
阅读完成 · 觉得有帮助？
