开篇不废话直接说C 标准库里有很多容器但要说面试考得最多、写题最常用、实际项目里也躲不掉的stack和queue绝对占一席。这两个名字翻译过来就是栈和队列前者是后进先出后者是先进先出光是这个概念就能延伸出一堆算法题比如括号匹配、逆波兰表达式、二叉树层序遍历。这篇文章不打算只讲怎么调用push、pop这几个接口我会把容器适配器这个底层逻辑讲透再带着你手写一版能跑的模拟实现最后把实际工程里踩过的坑一并列出来。不管你是刚学完链表和 vector 想进阶的初学者还是准备面试想快速捡起 STL 底层细节的选手这篇文章应该都能给你一点不一样的视角。至少看完之后你再去读任何一份开源代码里的std::stackint, std::vectorint不会觉得这是什么玄学。1. 先搞清楚stack 和 queue 到底是什么1.1 容器适配器这个概念很多初学者第一次看到std::stack的声明会蒙圈它不是容器吗怎么模板参数里还有一个Containertemplateclass T, class Container std::dequeT class stack;答案其实就在这段声明里stack本身并不是真正意义上的容器它只是在一个已有容器上面做了一层封装。这个已有容器默认是deque双端队列但你可以手动改成vector或者list。这种把一个现成的线性容器改造成另一种数据结构的对外接口的东西在 STL 里叫容器适配器。这个概念用生活类比最好理解你有一台能装水的饮水机底层容器给它加一个加热模块它就变成了热水器加一个制冷模块它就变成了冰水机。stack做的事情也很像对deque限制只能在一头放入和取出对外表现就是后进先出对deque限制一端进、另一端出对外表现就是先进先出。这也是为什么stack和queue的文档页面通常和vector、list分开排列它们属于容器适配器分类而不是序列容器分类。理解这一点非常重要因为它决定了我们后面模拟实现时的设计思路不是从零写内存管理而是复用底层容器只重写语义。1.2 stack 能干什么接口一览std::stack的接口少得可怜五个手指头能数完。这里我直接给你列清楚顺便标注了每个接口的作用接口作用复杂度注意点push(const T value)入栈在栈顶添加元素O(1) 均摊底层容器是 vector 时可能触发扩容pop()出栈移除栈顶元素O(1)不返回被删除元素这一点很多人第一次会踩坑top()返回栈顶元素的引用O(1)空栈调用是未定义行为empty()判断栈是否为空O(1)循环判断时一定要先查空size()返回栈中元素个数O(1)注意返回的是size_type和 int 比较要小心pop()不返回值这是 C 标准里一个反直觉但很经典的设计。它避免了一个问题如果pop返回栈顶元素的副本那就必须先拷贝一份再销毁原元素这个拷贝在元素类型很大的时候会有性能损耗而且在异常抛出时容易导致容器状态不一致。Java 的Stack.pop()会返回对象C 选择了性能优先的路线所以你需要先top()拿到值再pop()把它删掉。还有一个容易被忽略的细节top()返回的是引用这意味着你可以直接修改栈顶元素比如st.top() 42;是可以编译通过的。这在某些需要对栈顶做原地操作的算法里很实用但也容易让人误以为top()返回的是副本改了半天发现原数据没变回过头来才醒悟。1.3 queue 能干什么接口一览std::queue的接口比stack多了个back()因为队列需要同时操作两端。接口作用复杂度注意点push(const T value)入队在队尾添加元素O(1) 均摊底层 deque 两端插入都是常数复杂度pop()出队移除队头元素O(1)同样不返回被删除元素front()返回队头元素的引用O(1)可以修改空队列调用是未定义行为back()返回队尾元素的引用O(1)可以修改empty()判断队列是否为空O(1)遍历时用size()返回队列元素个数O(1)--queue的经典匹配场景是 BFS广度优先搜索。比如迷宫最短路径、二叉树的层序遍历、拓扑排序全都靠先进先出这个特性。举个最直观的例子你从起点出发把所有相邻的可达位置加入队列然后按顺序处理先加入的位置永远先被处理这就保证了一层一层往外扩的效果。但注意queue没有提供clear()接口也没有迭代器。这在 STL 容器里算是阉割版不过这不是缺陷而是刻意为之——适配器的意义就是对外只暴露符合数据结构语义的接口不希望你把一个队列当成数组随机访问。如果你真的需要清空一个队列常见做法是std::queueint().swap(q);或者直接重新赋一个新对象。2. 标准库里的实现秘密为什么底层是 deque2.1 deque 到底是什么要搞明白 stack 和 queue 的默认底层容器为什么是deque得先弄清楚deque本身是个什么样的容器。deque是double-ended queue的缩写中文叫双端队列它的核心能力是头尾两端都能 O(1) 插入和删除。deque的底层实现不是一段连续的内存而是由一块块定长的缓冲区组成的分段连续结构。它维护一个中控器map中控器里存着指向各个缓冲区的指针。因为多了一层指针跳转deque的随机访问比vector慢一点但在头部插入、尾部插入、头部删除、尾部删除这四个操作上它都能做到真正的常数时间不会像vector头部插入一样引起整体搬移。如果你没接触过deque的内存模型可以用搬家公司来类比vector是一辆大卡车货物必须码得整整齐齐搬一件进去有时候要先把整车货重新排一遍deque是一排分散的小仓库每间仓库放固定数量的货中间靠一辆调度车连接。你要在队伍最前面加一件货只需要找离得最近的那个仓库看它还有没有空位没有就新开一间调度车记一下位置就行不需要动其他仓库的东西。2.2 stack 为什么要用 deque 当默认底层有人会问stack只在一端操作用vector不是更简单吗用deque是不是过度设计答案要从两个角度看。第一deque的尾部插入和删除本来就是 O(1)而且deque 在扩容的时候不需要复制旧元素。这一点是deque和vector最本质的区别vector 扩容是一次分配一块更大的内存然后把旧元素逐个拷贝或移动过去deque 扩容只是新增一块缓冲区原有缓冲区里的元素原地不动。stack入栈频繁如果底层的 vector 在扩容时会卡一下性能波动就比较明显。尤其是在要求稳定延迟的环境里比如游戏引擎的帧循环、实时音频处理一次几毫秒甚至几十毫秒的卡顿都是不可接受的。deque 通过分段存储避免了大规模复制天然更平滑。第二个角度更实际queue需要在头部删、尾部加如果用vector做底层pop_front()会引发所有元素前移直接变成 O(n)如果用list虽然头尾操作都是 O(1)但每个节点都要额外存两个指针内存开销巨大而且节点分散在堆上缓存命中率很差。deque同时解决了这两个问题头尾操作 O(1)内存还是相对连续的缓冲区块缓存友好度远高于链表。所以标准库把默认底层设为deque是同时照顾了 stack 和 queue 两种适配器的需求。如果你想节省内存也可以显式指定std::stackint, std::vectorint在很多算法题场景下这是更优选择因为 vector 的连续内存缓存命中率是几个容器里最高的。我自己刷题时基本都会这么写后面会细说。2.3 顺手聊聊 priority_queue 和底层适配其实同一个适配器套路还衍生出第三个常见结构std::priority_queue优先级队列默认底层也是vector但它是基于堆heap实现的。templateclass T, class Container std::vectorT, class Compare std::lessT class priority_queue;priority_queue和queue虽然名字里都有 queue但语义完全不同它不是先进先出而是优先级最高的先出。默认情况下std::lessT配合vector实现的是大顶堆也就是top()返回的是最大元素。如果你想实现小顶堆要把比较器改成std::greaterT。这里有个很常见的误区很多初学者以为priority_queue的底层是普通的平衡树或者有序数组。实际上 STL 里给的是一套push_heap / pop_heap / make_heap算法族在 vector 上维护二叉堆。堆的插入和删除都是 O(logn)但你不需要自己写堆代码直接用就行。如果你在模拟实现阶段能把这三个容器适配器的共性抽取出来你对 STL 的理解会再上一个台阶。3. 手写一个能用的 stack 与 queue 模拟实现3.1 采用什么样的设计思路接下来是这篇文章的重头戏自己实现一个stack和一个queue。既然是模拟实现我建议不要搞那种自己从头写链表再实现栈的硬核方案而是尽量贴近 STL 的原版设计——用模板参数指定底层容器默认给 deque只暴露 stack / queue 应有的语义接口。这种设计最大的好处是拆解清晰你只需要关注适配这一层逻辑而不需要重复实现内存分配。同时它能让你真正理解 STL 里stack的代码为什么要长成那样。下面的代码我给足注释建议你直接抄进自己的练习项目里跑一遍。#pragma once #include deque namespace my { templateclass T, class Container std::dequeT class stack { public: using container_type Container; using value_type typename Container::value_type; using size_type typename Container::size_type; using reference typename Container::reference; bool empty() const { return c.empty(); } size_type size() const { return c.size(); } reference top() { return c.back(); } void push(const T value) { c.push_back(value); } void pop() { c.pop_back(); } protected: Container c; }; templateclass T, class Container std::dequeT class queue { public: using container_type Container; using value_type typename Container::value_type; using size_type typename Container::size_type; using reference typename Container::reference; bool empty() const { return c.empty(); } size_type size() const { return c.size(); } reference front() { return c.front(); } reference back() { return c.back(); } void push(const T value) { c.push_back(value); } void pop() { c.pop_front(); } protected: Container c; }; }核心思路就一句话栈的栈顶对应底层容器的尾部队列的队头对应底层容器的头部。所以 stack 的top()就是c.back()queue 的pop()就是c.pop_front()。除此之外所有成员函数基本都是转发。你可能会问为什么不把 stack 和 queue 抽象成一个公共基类在标准库的设计里它们确实互不相关因为适配的语义不同强行用继承只会把代码搞复杂。这里的protected成员c是故意这样设计的——一方面允许派生类在必要时访问底层容器另一方面又不希望外部直接操作它。3.2 实现细节与几个容易被忽略的点我上面给出的实现是一个最精简版本但如果你要把它用到自己的练习项目里还应该考虑下面三个问题。第一个问题是为什么要提供 const 版本的重载。标准库里的top()、front()、back()都有 const 和非 const 两个重载。上面的代码只写了非 const 版本在 const 对象上调用就会报错。完整的写法应该补上const_reference top() const { return c.back(); }第二个问题是移动语义和完美转发。C11 以后标准库的stack::push除了push(const T)还要求支持push(T)入栈一个临时对象的时候可以避免一次拷贝。另外 STL 还有一个emplace接口它直接在底层容器里原位构造对象连移动都能省掉。比如stackstd::pairint, int s; s.emplace(3, 5); // 不需要先构造 pair 再拷贝第三个问题是底层容器的选择会影响我们能做什么。比如std::stackbool, std::vectorbool会有问题因为vectorbool是一个特化版本存储的是位top()返回的引用不是真正的 bool 引用很容易踩坑。如果你就是想写一个内存紧凑的栈建议用deque默认值或者自己包装一个基于uint8_t的容器。3.3 测试代码验证我们写的能用写完模拟实现之后一定要做测试。我建议至少覆盖空栈、入栈出栈顺序、大元素类型这三个维度。下面这段测试代码可以直接复制去跑#include iostream #include string #include vector #include my_stack_queue.h int main() { my::stackint s; for (int i 1; i 5; i) s.push(i); while (!s.empty()) { std::cout s.top() ; s.pop(); } std::cout std::endl; my::queueint q; for (int i 1; i 5; i) q.push(i); while (!q.empty()) { std::cout q.front() ; q.pop(); } std::cout std::endl; // 用 vector 做底层容器的 stack my::stackstd::string, std::vectorstd::string vs; vs.push(hello); vs.push(world); while (!vs.empty()) { std::cout vs.top() ; vs.pop(); } std::cout std::endl; return 0; }运行结果应该是5 4 3 2 1 1 2 3 4 5 world hello如果输出顺序和上面一致说明你的模拟实现基本是正确的。这里还要多说一句my::stackstd::string, std::vectorstd::string能编译通过的原因是因为我们的实现只依赖底层容器的push_back、pop_back、back、empty、size这几个接口vector全部支持。这就是适配器的优雅之处——只要底层容器满足接口要求就能被适配。4. 经典应用场景括号匹配与层序遍历4.1 用 stack 解决括号匹配问题栈最经典的入门算法题就是括号匹配。给定一个只包含()[]{}的字符串判断括号是否闭合正确。这个问题的标准解法是遍历字符串如果是左括号就入栈如果是右括号就和栈顶元素比对匹配就弹出不匹配直接返回 false。很多人能背出这个思路但写代码时会在几个细节上翻车。这里我给出一个带详细注释的写法#include stack #include string #include unordered_map bool isValid(const std::string str) { std::stackchar st; // 用哈希表把右括号映射到对应的左括号代码会更简洁 std::unordered_mapchar, char mapping { {), (}, {], [}, {}, {} }; for (char ch : str) { if (ch ( || ch [ || ch {) { st.push(ch); } else { // 栈为空却遇到右括号一定是非法字符串 if (st.empty()) return false; if (st.top() ! mapping[ch]) return false; st.pop(); } } // 遍历结束之后栈应该为空否则说明有左括号没闭合 return st.empty(); }这段代码有两个非常容易忽略的地方。第一遇到右括号时如果栈是空的说明前面没有左括号和它匹配这时要立刻返回 false不需要再看后面的字符。第二最后一定要判断st.empty()因为像((()这样的字符串遍历完了栈里还有内容括号并不闭合。在实际笔试里这个题的变体会加上通配符或者只考虑一种括号但核心思路不变用栈保存未匹配的左括号右括号出现的时候就去看栈顶是否匹配。4.2 用 queue 实现二叉树层序遍历栈解决的是最近关联的问题队列解决的则是逐层推进的问题。二叉树层序遍历就是一个经典代表。层序遍历要求按层输出节点同一层从左到右排列。用 queue 的思路天然契合先把根节点入队然后循环每处理一个节点就把它的左右孩子入队。这里我给出一个按层分组的版本它能区分出每一层的边界这样才能输出第一行是根节点第二行是左右孩子这种格式#include queue #include vector struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} }; std::vectorstd::vectorint levelOrder(TreeNode* root) { std::vectorstd::vectorint result; if (root nullptr) return result; std::queueTreeNode* q; q.push(root); while (!q.empty()) { int levelSize q.size(); // 关键先记录当前层的节点数 std::vectorint currentLevel; for (int i 0; i levelSize; i) { TreeNode* node q.front(); q.pop(); currentLevel.push_back(node-val); if (node-left) q.push(node-left); if (node-right) q.push(node-right); } result.push_back(currentLevel); } return result; }这里最关键的代码是int levelSize q.size();。因为队列里的元素是动态变化的你在处理当前层节点时又会不断把下一层节点加进去。如果不先记录当前层的节点数for循环里的判断条件会越变越长最后当前层和下一层混在一起输出的就不是按层分组的结果了。这个模式在刷题里出现频率极高。比如二叉树右视图二叉树的锯齿形遍历每个树行找最大值这些题都是在层序遍历框架上稍微改一下逻辑。建议你把上面这个模板背熟做题时直接改中间的处理逻辑就行。4.3 用 stack 模拟递归过程还有一个容易被忽视但实际工程里很常用的场景用栈模拟递归避免递归调用的栈溢出。递归的本质是系统维护了一个调用栈。每进入一层递归就往栈里压入函数参数和返回地址每返回一层就弹出栈顶。所以理论上任何递归都能改写成显式栈迭代。比如二叉树的前序遍历递归写法非常简洁void preorder(TreeNode* root) { if (root nullptr) return; visit(root-val); preorder(root-left); preorder(root-right); }如果树的深度非常大比如退化成一条链的 10 万层树递归会直接爆掉系统调用栈。改成显式栈以后栈的内容存在堆上空间限制宽裕很多void preorderIterative(TreeNode* root) { if (root nullptr) return; std::stackTreeNode* st; st.push(root); while (!st.empty()) { TreeNode* node st.top(); st.pop(); visit(node-val); // 注意顺序先压右孩子再压左孩子 if (node-right) st.push(node-right); if (node-left) st.push(node-left); } }这里有一个经典的反直觉点为了保证先访问左子树压栈的时候必须先压右后压左因为栈是后进先出的。如果你反过来先压左再压右访问顺序就完全错了。这种栈方向的反直觉问题在实际写代码时非常容易暴露出对栈语义理解不深的问题。5. 常见问题与排查技巧实录5.1 空容器调用 top、front、pop 会发生什么std::stack::top()、std::queue::front()、std::queue::back()在容器为空时是未定义行为这意味着你依赖库的实现可能返回垃圾值可能崩溃也可能碰巧不崩。pop()同理。标准库不会帮你做安全检查因为每次操作都检查会增加额外开销破坏 C 追求零开销的原则。这意味着调用这些接口之前你必须自己确认栈或队列非空。我见过很多初学者在 while 循环里漏掉empty()判断直到某次调用top()返回了一个负数才意识到问题。我自己的习惯是凡是涉及top()、pop()的代码写完后先数一遍有没有在它们之前加空判断编译器不会帮你抓这种错只能靠细心。如果你实在不确定某段逻辑是否会出现空栈情况可以加一个防御性的断言至少调试阶段能帮你快速定位问题#include cassert assert(!st.empty()); int value st.top(); st.pop();5.2 底层容器选择vector vs deque vs list我在文章前面多次提到底层容器可以替换这里用一个表格把所有组合的优劣整理清楚方便你在不同场景下做选择底层容器stack 尾部操作queue 头部删除内存特性适用场景deque默认优秀O(1) 且扩容无复制优秀O(1)分段连续缓存中等通用首选安全vector优秀O(1)扩容有复制很差O(n)完全连续缓存最好刷算法题、数据量确定list优秀O(1)优秀O(1)节点分散内存开销大元素需要频繁中间插入删除单独说一句刷题场景如果你在做力扣这类在线评测且每次输入规模都事先知道用std::stackint, std::vectorint通常性能更好。因为 vector 是连续内存CPU 缓存命中率高而且刷题时栈的扩容次数有限复制成本可以忽略。但生产环境里如果你写一个通用模块我不建议随便换掉默认的 deque因为你不确定调用方会往里面塞多少数据deque 的稳定性更符合通用组件的要求。5.3 引用失效问题为什么 top 返回的引用来不及用top()返回的是底层容器元素的引用这个引用在后续的操作中可能失效。比如底层是 vector 的 stack在你调用push触发扩容后vector 会重新分配内存之前拿到的top()引用就指向了被释放的旧内存再访问就是悬垂引用。看这段错误代码std::stackint, std::vectorint st; st.push(1); int ref st.top(); // 获取引用 st.push(2); // 可能触发扩容ref 失效 ref 100; // 未定义行为可能修改到无效地址解决办法很简单如果要在入栈之后继续操作栈顶元素不要缓存引用每次需要时重新调用top()。这个坑在实际写代码时很隐蔽因为deque扩容不会搬移旧元素所以用默认底层时大概率不炸但一换成 vector 底层问题就出现了。我的建议是只要容器可能在引用生命周期内发生结构性变化就要重新获取引用或使用拷贝。5.4 自定义类型进容器拷贝、移动与 emplace如果你往 stack 或 queue 里放自定义对象要注意元素的构造方式。st.push(obj)的方式会对对象做一次拷贝或移动如果你不想多这一次操作可以用 C11 引入的emplace在底层容器内直接构造#include queue struct Task { int id; std::string name; Task(int i, std::string n) : id(i), name(std::move(n)) {} }; int main() { std::queueTask tasks; tasks.emplace(1, write article); tasks.emplace(2, review code); // 避免了 Task 临时对象的拷贝 }emplace的原理是把参数完美转发给容器在已分配好的内存上直接调用构造函数。当你的自定义类型构造代价较高比如带有 std::string、std::vector 成员时这个优化是实打实的。不过要注意如果底层容器是 vectoremplace仍然可能在扩容时搬移元素只是少了一次入栈时临时对象的拷贝。5.5 如何清空 stack 或 queue标准库的 stack 和 queue 都没有提供clear()这是初学者最容易吐槽的一个点。清空一个std::stack最简单的方式是直接赋一个新对象std::stackint st; st.push(1); st.push(2); st std::stackint(); // 赋值一个新的空栈或者用 swap 技巧让空容器和当前容器交换内容std::stackint empty; st.swap(empty);queue同理。如果你用的是std::queueint().swap(q)这种写法注意它先构造一个临时空队列再用 swap 把内容换走临时对象析构时释放内存。这种方式能顺便把底层容器的容量也降下来适合处理用完想释放内存的场景。6. 最后再分享一点我的实操体会写这篇文章时我特意把模拟实现的代码又跑了一遍。说实话STL 标准库里的 stack 和 queue 本身并不复杂真正的难点往往藏在你以为你会了的地方。比如我在自测时曾试着用std::list作为 queue 的底层容器然后去打印每个元素发现节点分散在堆上缓存命中率确实比 deque 差了不少这个结论只有自己测过才有体感。如果你学到这里想进一步深入我建议你可以做三个小练习第一自己实现一个基于动态数组的 stack并手动处理扩容逻辑对比 std::vector 的扩容策略第二实现一个循环队列绕过容器适配器直接用定长数组模拟面试里这道题出现频率极高第三用 stack 和 queue 分别实现用栈实现队列和用队列实现栈这两个经典题目做完之后你对两者语义的反差会有更深刻的记忆。我在实际项目里最常用到 stack 的场景反而是文本解析。比如处理带有嵌套结构的 DSL 配置遇到左括号就入栈遇到右括号就出栈顺便做一层括号与层级的配对校验。queue 则更多出现在生产者消费者模型和异步任务调度里任务按到达顺序排队执行。理解它们的使用与模拟实现之后你在读这类业务代码时会发现很多所谓的高深设计说白了就是在做容器语义的包装。