提到STL里的stack和queue很多人的第一反应是“这不就是个栈和队列嘛能有什么可讲的”。但你真动手去写一个高性能的栈或队列或者在算法题里因为底层容器选错而超时的时候就会意识到一个关键问题这两个东西在STL里压根不配叫“容器”它们只是站在别的容器肩膀上的“适配器”。这篇内容我想从适配器的本质讲起一步一步带着大家把它俩的底层逻辑拆开能手写模拟实现也能在实际算法场景里用得明明白白。1. 先搞懂一件事stack/queue不是容器是适配器1.1 为什么标准库不单独给它们设计内存结构stack和queue在STL里的官方分类是container adapter也就是容器适配器。它们自己不管理内存、不分配空间也不存储数据——所有数据都存放在一个底层容器对象里面stack和queue只是把这个底层容器的接口“改头换面”了一下。这听起来很抽象但你想想实际需求就清楚了。栈只需要五个操作判空、求大小、取顶、压入、弹出。队列多一个“取队首”再往外推一个“取队尾”。就这么点接口有必要像vector那样维护一段连续内存或者像list那样折腾一套双向链表节点吗完全没有。标准库的设计哲学是轻重分离内存布局的脏活累活交给专用容器stack和queue只是像一个“接线员”把底层容器的部分接口暴露出来屏蔽掉不该露的。这也就是为什么stack 的底层可以是deque也可以是vector甚至可以是一个自己写的链表类——只要这个容器支持back()、push_back()、pop_back()它就能被“适配”成栈。接口约束是唯一的门槛。1.2 适配器的本质封装、屏蔽、保留最小接口适配器这个模式本质上做三件事。第一是封装。stack内部持有一个底层容器的实例用户传入的数据都进到底层容器里。第二是屏蔽。vector明明支持随机访问但stack不给你operator[]不给你begin()/end()——你没法遍历没法按下标改元素。第三是保留最小接口。只暴露栈语义需要的那几个操作不多给一个。这三件事放在一起来看就是一个非常典型的“接口收窄”。为什么要收窄因为有的时候限制反而是安全。栈这个数据结构的使用者不应该关心底层是数组还是链表也不需要有能力去跳过栈顶直接访问中间元素。你一旦把vector的完整能力暴露出来谁都能写出s[0]这种代码那栈的“后进先出”约束就形同虚设了。所以标准库宁愿让你用起来“笨”一点也要保证数据结构的语义不被破坏。这个设计思路写业务代码的时候同样值得借鉴对外暴露的接口永远是最小的底层实现再灵活也是私有细节。1.3 顺带看一眼priority_queue这个“同门师兄弟”说到适配器必须顺带提一下priority_queue。它是“优先队列”适配器默认底层容器是vector再加上堆排序算法每次push和pop都维持堆结构保证top()拿到的是优先级最高的元素。这三个适配器有个共同点都不提供迭代器都对底层容器的接口做二次筛选。但priority_queue和stack/queue有一个本质差异。前两者的适配逻辑是纯“接口映射”你来一个数据我往里放按顺序进出。priority_queue则是“算法介入”——它是在底层容器的数据之上每时每刻维护一个大顶堆默认用less比较器。这也是为什么priority_queue的默认底层是vector而不是deque堆排序需要频繁的随机访问vector的连续内存性能优势最明显。2. 默认底层为什么是deque拆开看deque的“两副面孔”2.1 deque的分段连续存储结构stack和queue的默认底层容器都是deque不是vector也不是list。这个选择背后的原因值得掰开揉碎讲清楚。deque的全称是double-ended queue双端队列。它的物理结构是“分段连续”的内部维护一个中控器可以理解为一个指针数组每个指针指向一段固定大小的连续缓冲区。元素被分散在若干块内存里块与块之间不连续但deque对外表现像一段连续内存支持operator[]随机访问。往头部插入元素时deque只需要在中控器前面挂一个新的缓冲区往尾部插入也是同理。双端的push和pop都是摊还O(1)。每个缓冲区内部按顺序填满所以随机访问虽然要经过“中控器定位缓冲区指针 缓冲区内部偏移”两步但整体依然很快。2.2 和vector、list的取舍对比默认底层为什么是deque把三种容器摆在一起比较就一目了然了。维度vectordequelist尾部插入/删除O(1) 摊还O(1)O(1)头部插入/删除O(n)O(1)O(1)随机访问O(1)极快O(1)多一次间接O(n)内存连续性完全连续分段连续不连续节点分散额外内存开销低低-中高每个节点存指针适用适配器stackstack / queuestack / queuevector支持尾部O(1)插入但头部插入是O(n)所以它可以做栈的底层没法做队列的底层——队列需要pop_frontvector的pop_front会把所有元素往前挪代价根本扛不住。list头尾插入都是O(1)理论上做queue的底层完全没问题但它的问题在于内存不连续、节点携带额外指针开销、随机访问是O(n)性能在绝大多数场景下不如deque。deque两边都能O(1)随机访问也没退化到list那个程度综合下来就是最均衡的选择。2.3 deque的“隐藏成本”deque最佳并不代表没有代价。分段连续的内存结构意味着operator[]比vector多一次指针间接。缓存局部性上vector把数据塞在一整块连续内存里遍历时CPU缓存命中率极高deque则可能在不同缓冲区之间跳来跳去。如果你写的是高性能遍历代码vector的优势是实打实的。另一个隐藏成本是deque的迭代器活得比较“沉”。它不仅要记录当前位置还要记录当前缓冲区的位置和中控器的位置迭代器体积比vector的裸指针大得多。不过对普通业务代码来说这些差异通常感知不到。等真正到了性能瓶颈你会通过profiler看到deque的问题而不是靠肉眼猜测。3. 手写模拟实现模板参数 组合复用25行代码说清设计精髓3.1 核心代码MyStack / MyQueue理解了适配器的思想之后模拟实现其实就是一句话的事内部组合一个底层容器对象然后把接口转发过去。template typename T, typename Container std::dequeT class MyStack { public: // 元素访问 T top() { return c.back(); } const T top() const { return c.back(); } // 容量 bool empty() const { return c.empty(); } size_t size() const { return c.size(); } // 修改 void push(const T value) { c.push_back(value); } void push(T value) { c.push_back(std::move(value)); } void pop() { c.pop_back(); } // 交换 void swap(MyStack other) { c.swap(other.c); } private: Container c; // 核心组合一个底层容器 };队列的实现几乎是对称的差异只在操作的选择上。template typename T, typename Container std::dequeT class MyQueue { public: // 元素访问 T front() { return c.front(); } const T front() const { return c.front(); } T back() { return c.back(); } const T back() const { return c.back(); } // 容量 bool empty() const { return c.empty(); } size_t size() const { return c.size(); } // 修改 void push(const T value) { c.push_back(value); } void push(T value) { c.push_back(std::move(value)); } void pop() { c.pop_front(); } private: Container c; };就是这么简单。栈的所有操作映射到back那一侧队列的push映射到back、pop映射到front。底层容器换成一个list代码一行都不用改语义依然正确。这就是组合复用和一个简单模板参数的威力。3.2 为什么底层容器作为模板参数是关键设计你会注意到模拟实现里唯一“有技术含量”的地方不在任何逻辑上而是那个默认参数Container std::deque 。这个设计让使用者能动态决定适配器下面垫的是谁的“屁股”。默认是deque因为它在绝大多数场景下最均衡。但细节控可以写成std::stackint, std::vector 牺牲push_front的能力换来更紧凑的内存布局想专门定制某种特殊内存池容器也完全可以只要新容器满足接口要求。这样设计带来的灵活度来源于适配器本身“不拥有数据”的本质。底层容器是提供给适配器的服务方双方只有接口约定没有血缘关系。这也是为什么标准库里stack/queue的声明长这样templateclass T, class Container std::dequeT class stack; templateclass T, class Container std::dequeT class queue;3.3 pop为什么不返回元素异常安全的设计考量有编程经验的人一定会问为什么取栈顶要分两步top()和pop()不能设计成int x stack.pop()把元素弹出来顺带返回答案是异常安全。如果pop负责删除元素并返回被删元素的副本返回这个副本需要一次拷贝构造拷贝构造可能抛异常。一旦抛了异常栈顶元素可能已经被删也可能没被删——状态就暧昧了。更糟的是先拷贝出元素、再真正删除的分步操作里如果第二步还没执行就抛异常数据丢失但状态又表现为正常。所以标准库强制top()和pop()分开。top返回的是栈顶元素的引用不修改容器状态异常安全pop只负责删元素不产生新的对象同样不会抛异常除非容器底层操作抛。两步拼起来每一步都是强异常安全保证的。这个设计哲学在你写自己的库的时候特别值得抄。3.4 模拟实现与标准库的差距上面的代码能跑、能通过绝大多数测试但和标准库的真实实现比还有几个差距要说明。第一是成员类型。标准库的stack会声明value_type、container_type、size_type等嵌套类型方便编写泛型代码时做类型萃取。第二是分配器支持。标准库允许你往stack里传入allocator让元素的内存分配策略可控。第三是emplace系列。C11之后标准库容器支持emplace()在底层容器内直接构造元素省掉一次移动拷贝。把这几项一并加上代码行数会多不少。不过理解核心语义的话最基本的版本已经足够。写模拟实现的意义不在于和标准库逐字节对齐而在于通过亲手转发接口彻底体会到“适配器”三个字究竟在说什么。4. 算法实战一stack的三个典型场景从最近匹配到延迟匹配4.1 括号匹配栈为何天然适合“最近匹配”栈最直观的算法价值是处理“最近关联”问题。给定一个只包含括号的字符串判断括号是否合法闭合是再经典不过的入门题。bool isBalanced(const std::string s) { std::stackchar st; for (char ch : s) { if (ch ( || ch [ || ch {) { st.push(ch); } else { if (st.empty()) return false; char top st.top(); if ((ch ) top ! () || (ch ] top ! [) || (ch } top ! {)) { return false; } st.pop(); } } return st.empty(); }这个问题的核心洞察是字符串里最后出现的左括号必须匹配最先出现的右括号。这天然就是一个“后进先出”的顺序和栈的语义严丝合缝。每次看到右括号栈顶元素就是它应该对应的那个左括号。如果不是括号不合法如果栈空了右括号多余最后栈非空左括号剩余。三个分支逻辑全齐了。值得强调的是复杂度。这个算法的时间复杂度O(n)空间复杂度最坏O(n)。在括号嵌套深度很高、但字符串不长的时候空间复杂度就是瓶颈。如果你知道括号嵌套深度有上限比如只有三层那么用一个固定大小的数组模拟栈空间可以做到O(1)。4.2 逆波兰表达式操作数栈的经典应用逆波兰表达式RPN也叫后缀表达式特点是运算符跟在操作数后面。计算机解析它不需要考虑优先级和括号。这是栈在表达式求值领域最经典的出场。int evalRPN(const std::vectorstd::string tokens) { std::stackint st; for (const std::string 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(); }最容易写错的地方是操作数顺序。先弹出的是b右操作数再弹出的是a左操作数。做减法和除法的时候a和b交换位置会产生完全不同的结果。我第一次写的时候就在这翻过车遇到10和3相减先弹3后弹10十减三是7没问题但要是顺序搞反了变成三减十直接负数。写这类代码第一步先在心里给栈画个图。4.3 单调栈下一个更大元素的“延迟匹配”思想括号匹配是“立即匹配”单调栈则是“延迟匹配”。它做的事情是遍历到一个元素时先不确定这个元素的答案把它先存在栈里“观察”直到后面出现满足条件的元素再去结算之前存下的那些元素。以经典的“每日温度”为例。给定每天温度数组要求输出气温升高需要等待的天数。std::vectorint dailyTemperatures(const std::vectorint temperatures) { int n temperatures.size(); std::vectorint res(n, 0); std::stackint st; // 存下标栈底到栈顶温度单调递减 for (int i 0; i n; i) { while (!st.empty() temperatures[i] temperatures[st.top()]) { res[st.top()] i - st.top(); st.pop(); } st.push(i); } return res; }这个算法的精妙之处在于维护了一个“温度递减”的栈。栈里存的下标对应的温度是从栈底到栈顶严格递减的。遍历到新温度时只要它比栈顶温度高说明栈顶那个位置找到了第一个更高的温度立刻结算如果新温度更低它自己入栈等待未来某天结算。每个元素最多入栈一次、出栈一次总复杂度O(n)。单调栈的变体非常广。柱状图中最大矩形面积、接雨水等一堆看似不相干的问题底层都是这套延迟匹配的思想。理解了一个场景其他场景基本就是换换比较条件和结算逻辑。5. 算法实战二queue与deque的三个典型场景5.1 层序遍历先固定当前层大小这个细节树的层序遍历是queue最直观的应用。逐层访问节点顺序天然是先进先出。但有一个细节不亲手写一遍很容易掉坑。std::vectorstd::vectorint levelOrder(TreeNode* root) { std::vectorstd::vectorint res; if (!root) return res; std::queueTreeNode* q; q.push(root); while (!q.empty()) { int levelSize q.size(); // 关键先固定当前层节点数 std::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); } res.push_back(level); } return res; }关键点是进入循环后第一件事就是把q.size()存下来。因为处理当前层节点的过程中会把下一层的孩子节点也push进队列q.size()会不断变大。如果不先固定layerSizefor循环会失控把下一层的节点混进当前层的vector。5.2 BFS拓扑排序入度为0的节点队列拓扑排序解决的是“有依赖关系的任务谁先谁后”的问题。Kahn算法用队列实现BFS思路非常清晰不断把入度为0的节点入队一个个出队并在每次出队时把这个节点能到达的邻居入度减一。邻居入度一旦归零意味着它的所有前置依赖都已经处理完可以入队了。std::vectorint topoSort(int n, const std::vectorstd::vectorint edges) { std::vectorint indegree(n, 0); std::vectorstd::vectorint adj(n); for (const auto e : edges) { adj[e[0]].push_back(e[1]); indegree[e[1]]; } std::queueint q; for (int i 0; i n; i) { if (indegree[i] 0) q.push(i); } std::vectorint res; while (!q.empty()) { int u q.front(); q.pop(); res.push_back(u); for (int v : adj[u]) { if (--indegree[v] 0) q.push(v); } } // 出现环时res长度不足n return res.size() n ? res : std::vectorint{}; }这里queue的作用是保存“当前可以直接执行的候选任务”。queue本身不承担任何逻辑判断它像一个传送带入度为0的任务被放在传送带上一个个被消化。如果最终res长度小于n说明图中存在环——有些节点的入度永远不会归零永远等不到被处理的机会。5.3 滑动窗口最大值用deque实现单调队列滑动窗口最大值问题在很多地方都叫“单调队列”。它用的数据结构实际上是deque而不是queue但和queue的FIFO思想同源。先看代码。std::vectorint maxSlidingWindow(const std::vectorint nums, int k) { std::vectorint res; std::dequeint dq; // 存下标队首到队尾单调递减 for (int i 0; i (int)nums.size(); i) { // 1. 删除窗口外的元素窗口左边界离开 if (!dq.empty() dq.front() i - k) dq.pop_front(); // 2. 删除队尾所有比当前元素小的元素 while (!dq.empty() nums[dq.back()] nums[i]) dq.pop_back(); // 3. 当前元素入队 dq.push_back(i); // 4. 窗口形成后队首就是最大值 if (i k - 1) res.push_back(nums[dq.front()]); } return res; }这个算法的思路是维护一个“从队首到队尾递减”的下标队列。队首永远是当前窗口最大值。每次滑动窗口先看看队首下标是否已经被滑出窗口左边界如果是就弹出然后清理队尾所有比新元素小的元素因为它们在新元素存在的整个生命周期里永远不可能成为最大值。剩下的数字从队首到队尾是一个递减序列队首直接取最大值。为什么用deque因为需要两端同时操作队首要弹出过期的元素队尾要弹出较小的元素再压入新元素。这个双端操作的需求恰恰是deque的设计初衷。这里也能看出适配器和算法场景是密不可分的正确的数据结构选型往往直接决定了算法能不能写出O(n)的复杂度。6. 实战中的易错点与选型建议6.1 queue和stack没有clear()清空方式的代价用惯了vector很多人会自然地以为queue会有clear()结果编译直接报错。stack和queue这两个适配器故意不提供clear()接口。清空它们常见做法是// 方式1pop到空 while (!q.empty()) q.pop(); // 方式2直接用临时对象赋值 q std::queueint(); // 方式3stack同理 std::stackint emptyStack; s.swap(emptyStack);方式1是O(n)的需要逐个调用pop。方式2和方式3实际上是O(1)的只是把内部底层容器的所有权整个换掉了。工程代码里推荐直接用方式3swap是成员函数开销极小。在面试或笔试题里如果要求“清空栈/队列”这些细节是能反映功底的。6.2 不可遍历的接口设计为什么不是缺陷stack和queue没有迭代器很多人刚接触的时候抱怨“不方便”。但换个角度想这反而是设计者刻意为之的防御。vector之所以强大是因为它承诺随机访问和遍历能力。但栈的价值恰恰在于“只能碰栈顶”队列的价值在于“只能从头进出”。一旦允许遍历就能绕过数据结构的语义限制直接摸到内部状态。限制接口本质上是保护数据结构操作的正确性。如果在实际开发中你真的需要遍历一个栈里的全部元素合理的做法不是“给栈加迭代器”而是退一步审视设计这里到底需不需要栈也许vector本身才是更合适的容器。6.3 vector当栈使可以queue别硬上list我实际写代码的经验是栈的实现用std::stack很顺手但如果我自己要写一个需要频繁遍历的栈结构会直接用vector配合size成员手动维护栈顶位置。vector的内存连续性带来的缓存优势在大量访问场景下非常明显。stack的top()按常数时间返回栈顶的引用本质上也只是vector.back()的包装。queue的选型就没那么大自由度了。如果数据量小、且不需要随机访问list能勉强当queue底层但每个元素多存一两个指针cache不友好。deque在绝大多数情况下是平衡点。只有在极端低延迟、队列长度极长的场景我才会考虑自己写环形数组来替代——但那个场景我会直接用std::vector维护head/tail两个下标而不是真的去“实现一个queue”。6.4 性能实测中的几个心得最后说几个我实际调试和测试中遇到的教训。deque的operator[]确实比vector慢。差别不大大概几个百分点但在百万级以上的循环里可以稳定复现。如果写的是热路径代码而且元素数量充足vector优先。优先使用emplace而非push。C11之后stack和queue都转发支持emplace。emplace直接在底层容器中构造对象免掉了“临时对象构造 移动拷贝”两步。对string这种非平凡类型收益尤其明显。我实测过emplace比push加移动构造省掉一个临时string的构造和析构在百万次入栈场景下能差出肉眼可见的时间。swap是个被低估的成员函数。stack和queue都带swap成员交换两个栈或两个队列代价极低。实测它只是交换底层容器的内部指针不会搬动任何元素。在需要批量重建数据结构的场景先用临时对象swap一下比逐个pop快几个数量级。STL真正要做的事不是替你保存数据而是在需要的地方用最少的状态变化完成对数据的操作。适配器只是把这个哲学用到了极致而已。 
长河君 · 2026/10/14 21:56:51 · 阅读 1.2k STL stack和queue：容器适配器的底层原理与算法实战
提到STL里的stack和queue很多人的第一反应是“这不就是个栈和队列嘛能有什么可讲的”。但你真动手去写一个高性能的栈或队列或者在算法题里因为底层容器选错而超时的时候就会意识到一个关键问题这两个东西在STL里压根不配叫“容器”它们只是站在别的容器肩膀上的“适配器”。这篇内容我想从适配器的本质讲起一步一步带着大家把它俩的底层逻辑拆开能手写模拟实现也能在实际算法场景里用得明明白白。1. 先搞懂一件事stack/queue不是容器是适配器1.1 为什么标准库不单独给它们设计内存结构stack和queue在STL里的官方分类是container adapter也就是容器适配器。它们自己不管理内存、不分配空间也不存储数据——所有数据都存放在一个底层容器对象里面stack和queue只是把这个底层容器的接口“改头换面”了一下。这听起来很抽象但你想想实际需求就清楚了。栈只需要五个操作判空、求大小、取顶、压入、弹出。队列多一个“取队首”再往外推一个“取队尾”。就这么点接口有必要像vector那样维护一段连续内存或者像list那样折腾一套双向链表节点吗完全没有。标准库的设计哲学是轻重分离内存布局的脏活累活交给专用容器stack和queue只是像一个“接线员”把底层容器的部分接口暴露出来屏蔽掉不该露的。这也就是为什么stack 的底层可以是deque也可以是vector甚至可以是一个自己写的链表类——只要这个容器支持back()、push_back()、pop_back()它就能被“适配”成栈。接口约束是唯一的门槛。1.2 适配器的本质封装、屏蔽、保留最小接口适配器这个模式本质上做三件事。第一是封装。stack内部持有一个底层容器的实例用户传入的数据都进到底层容器里。第二是屏蔽。vector明明支持随机访问但stack不给你operator[]不给你begin()/end()——你没法遍历没法按下标改元素。第三是保留最小接口。只暴露栈语义需要的那几个操作不多给一个。这三件事放在一起来看就是一个非常典型的“接口收窄”。为什么要收窄因为有的时候限制反而是安全。栈这个数据结构的使用者不应该关心底层是数组还是链表也不需要有能力去跳过栈顶直接访问中间元素。你一旦把vector的完整能力暴露出来谁都能写出s[0]这种代码那栈的“后进先出”约束就形同虚设了。所以标准库宁愿让你用起来“笨”一点也要保证数据结构的语义不被破坏。这个设计思路写业务代码的时候同样值得借鉴对外暴露的接口永远是最小的底层实现再灵活也是私有细节。1.3 顺带看一眼priority_queue这个“同门师兄弟”说到适配器必须顺带提一下priority_queue。它是“优先队列”适配器默认底层容器是vector再加上堆排序算法每次push和pop都维持堆结构保证top()拿到的是优先级最高的元素。这三个适配器有个共同点都不提供迭代器都对底层容器的接口做二次筛选。但priority_queue和stack/queue有一个本质差异。前两者的适配逻辑是纯“接口映射”你来一个数据我往里放按顺序进出。priority_queue则是“算法介入”——它是在底层容器的数据之上每时每刻维护一个大顶堆默认用less比较器。这也是为什么priority_queue的默认底层是vector而不是deque堆排序需要频繁的随机访问vector的连续内存性能优势最明显。2. 默认底层为什么是deque拆开看deque的“两副面孔”2.1 deque的分段连续存储结构stack和queue的默认底层容器都是deque不是vector也不是list。这个选择背后的原因值得掰开揉碎讲清楚。deque的全称是double-ended queue双端队列。它的物理结构是“分段连续”的内部维护一个中控器可以理解为一个指针数组每个指针指向一段固定大小的连续缓冲区。元素被分散在若干块内存里块与块之间不连续但deque对外表现像一段连续内存支持operator[]随机访问。往头部插入元素时deque只需要在中控器前面挂一个新的缓冲区往尾部插入也是同理。双端的push和pop都是摊还O(1)。每个缓冲区内部按顺序填满所以随机访问虽然要经过“中控器定位缓冲区指针 缓冲区内部偏移”两步但整体依然很快。2.2 和vector、list的取舍对比默认底层为什么是deque把三种容器摆在一起比较就一目了然了。维度vectordequelist尾部插入/删除O(1) 摊还O(1)O(1)头部插入/删除O(n)O(1)O(1)随机访问O(1)极快O(1)多一次间接O(n)内存连续性完全连续分段连续不连续节点分散额外内存开销低低-中高每个节点存指针适用适配器stackstack / queuestack / queuevector支持尾部O(1)插入但头部插入是O(n)所以它可以做栈的底层没法做队列的底层——队列需要pop_frontvector的pop_front会把所有元素往前挪代价根本扛不住。list头尾插入都是O(1)理论上做queue的底层完全没问题但它的问题在于内存不连续、节点携带额外指针开销、随机访问是O(n)性能在绝大多数场景下不如deque。deque两边都能O(1)随机访问也没退化到list那个程度综合下来就是最均衡的选择。2.3 deque的“隐藏成本”deque最佳并不代表没有代价。分段连续的内存结构意味着operator[]比vector多一次指针间接。缓存局部性上vector把数据塞在一整块连续内存里遍历时CPU缓存命中率极高deque则可能在不同缓冲区之间跳来跳去。如果你写的是高性能遍历代码vector的优势是实打实的。另一个隐藏成本是deque的迭代器活得比较“沉”。它不仅要记录当前位置还要记录当前缓冲区的位置和中控器的位置迭代器体积比vector的裸指针大得多。不过对普通业务代码来说这些差异通常感知不到。等真正到了性能瓶颈你会通过profiler看到deque的问题而不是靠肉眼猜测。3. 手写模拟实现模板参数 组合复用25行代码说清设计精髓3.1 核心代码MyStack / MyQueue理解了适配器的思想之后模拟实现其实就是一句话的事内部组合一个底层容器对象然后把接口转发过去。template typename T, typename Container std::dequeT class MyStack { public: // 元素访问 T top() { return c.back(); } const T top() const { return c.back(); } // 容量 bool empty() const { return c.empty(); } size_t size() const { return c.size(); } // 修改 void push(const T value) { c.push_back(value); } void push(T value) { c.push_back(std::move(value)); } void pop() { c.pop_back(); } // 交换 void swap(MyStack other) { c.swap(other.c); } private: Container c; // 核心组合一个底层容器 };队列的实现几乎是对称的差异只在操作的选择上。template typename T, typename Container std::dequeT class MyQueue { public: // 元素访问 T front() { return c.front(); } const T front() const { return c.front(); } T back() { return c.back(); } const T back() const { return c.back(); } // 容量 bool empty() const { return c.empty(); } size_t size() const { return c.size(); } // 修改 void push(const T value) { c.push_back(value); } void push(T value) { c.push_back(std::move(value)); } void pop() { c.pop_front(); } private: Container c; };就是这么简单。栈的所有操作映射到back那一侧队列的push映射到back、pop映射到front。底层容器换成一个list代码一行都不用改语义依然正确。这就是组合复用和一个简单模板参数的威力。3.2 为什么底层容器作为模板参数是关键设计你会注意到模拟实现里唯一“有技术含量”的地方不在任何逻辑上而是那个默认参数Container std::deque 。这个设计让使用者能动态决定适配器下面垫的是谁的“屁股”。默认是deque因为它在绝大多数场景下最均衡。但细节控可以写成std::stackint, std::vector 牺牲push_front的能力换来更紧凑的内存布局想专门定制某种特殊内存池容器也完全可以只要新容器满足接口要求。这样设计带来的灵活度来源于适配器本身“不拥有数据”的本质。底层容器是提供给适配器的服务方双方只有接口约定没有血缘关系。这也是为什么标准库里stack/queue的声明长这样templateclass T, class Container std::dequeT class stack; templateclass T, class Container std::dequeT class queue;3.3 pop为什么不返回元素异常安全的设计考量有编程经验的人一定会问为什么取栈顶要分两步top()和pop()不能设计成int x stack.pop()把元素弹出来顺带返回答案是异常安全。如果pop负责删除元素并返回被删元素的副本返回这个副本需要一次拷贝构造拷贝构造可能抛异常。一旦抛了异常栈顶元素可能已经被删也可能没被删——状态就暧昧了。更糟的是先拷贝出元素、再真正删除的分步操作里如果第二步还没执行就抛异常数据丢失但状态又表现为正常。所以标准库强制top()和pop()分开。top返回的是栈顶元素的引用不修改容器状态异常安全pop只负责删元素不产生新的对象同样不会抛异常除非容器底层操作抛。两步拼起来每一步都是强异常安全保证的。这个设计哲学在你写自己的库的时候特别值得抄。3.4 模拟实现与标准库的差距上面的代码能跑、能通过绝大多数测试但和标准库的真实实现比还有几个差距要说明。第一是成员类型。标准库的stack会声明value_type、container_type、size_type等嵌套类型方便编写泛型代码时做类型萃取。第二是分配器支持。标准库允许你往stack里传入allocator让元素的内存分配策略可控。第三是emplace系列。C11之后标准库容器支持emplace()在底层容器内直接构造元素省掉一次移动拷贝。把这几项一并加上代码行数会多不少。不过理解核心语义的话最基本的版本已经足够。写模拟实现的意义不在于和标准库逐字节对齐而在于通过亲手转发接口彻底体会到“适配器”三个字究竟在说什么。4. 算法实战一stack的三个典型场景从最近匹配到延迟匹配4.1 括号匹配栈为何天然适合“最近匹配”栈最直观的算法价值是处理“最近关联”问题。给定一个只包含括号的字符串判断括号是否合法闭合是再经典不过的入门题。bool isBalanced(const std::string s) { std::stackchar st; for (char ch : s) { if (ch ( || ch [ || ch {) { st.push(ch); } else { if (st.empty()) return false; char top st.top(); if ((ch ) top ! () || (ch ] top ! [) || (ch } top ! {)) { return false; } st.pop(); } } return st.empty(); }这个问题的核心洞察是字符串里最后出现的左括号必须匹配最先出现的右括号。这天然就是一个“后进先出”的顺序和栈的语义严丝合缝。每次看到右括号栈顶元素就是它应该对应的那个左括号。如果不是括号不合法如果栈空了右括号多余最后栈非空左括号剩余。三个分支逻辑全齐了。值得强调的是复杂度。这个算法的时间复杂度O(n)空间复杂度最坏O(n)。在括号嵌套深度很高、但字符串不长的时候空间复杂度就是瓶颈。如果你知道括号嵌套深度有上限比如只有三层那么用一个固定大小的数组模拟栈空间可以做到O(1)。4.2 逆波兰表达式操作数栈的经典应用逆波兰表达式RPN也叫后缀表达式特点是运算符跟在操作数后面。计算机解析它不需要考虑优先级和括号。这是栈在表达式求值领域最经典的出场。int evalRPN(const std::vectorstd::string tokens) { std::stackint st; for (const std::string 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(); }最容易写错的地方是操作数顺序。先弹出的是b右操作数再弹出的是a左操作数。做减法和除法的时候a和b交换位置会产生完全不同的结果。我第一次写的时候就在这翻过车遇到10和3相减先弹3后弹10十减三是7没问题但要是顺序搞反了变成三减十直接负数。写这类代码第一步先在心里给栈画个图。4.3 单调栈下一个更大元素的“延迟匹配”思想括号匹配是“立即匹配”单调栈则是“延迟匹配”。它做的事情是遍历到一个元素时先不确定这个元素的答案把它先存在栈里“观察”直到后面出现满足条件的元素再去结算之前存下的那些元素。以经典的“每日温度”为例。给定每天温度数组要求输出气温升高需要等待的天数。std::vectorint dailyTemperatures(const std::vectorint temperatures) { int n temperatures.size(); std::vectorint res(n, 0); std::stackint st; // 存下标栈底到栈顶温度单调递减 for (int i 0; i n; i) { while (!st.empty() temperatures[i] temperatures[st.top()]) { res[st.top()] i - st.top(); st.pop(); } st.push(i); } return res; }这个算法的精妙之处在于维护了一个“温度递减”的栈。栈里存的下标对应的温度是从栈底到栈顶严格递减的。遍历到新温度时只要它比栈顶温度高说明栈顶那个位置找到了第一个更高的温度立刻结算如果新温度更低它自己入栈等待未来某天结算。每个元素最多入栈一次、出栈一次总复杂度O(n)。单调栈的变体非常广。柱状图中最大矩形面积、接雨水等一堆看似不相干的问题底层都是这套延迟匹配的思想。理解了一个场景其他场景基本就是换换比较条件和结算逻辑。5. 算法实战二queue与deque的三个典型场景5.1 层序遍历先固定当前层大小这个细节树的层序遍历是queue最直观的应用。逐层访问节点顺序天然是先进先出。但有一个细节不亲手写一遍很容易掉坑。std::vectorstd::vectorint levelOrder(TreeNode* root) { std::vectorstd::vectorint res; if (!root) return res; std::queueTreeNode* q; q.push(root); while (!q.empty()) { int levelSize q.size(); // 关键先固定当前层节点数 std::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); } res.push_back(level); } return res; }关键点是进入循环后第一件事就是把q.size()存下来。因为处理当前层节点的过程中会把下一层的孩子节点也push进队列q.size()会不断变大。如果不先固定layerSizefor循环会失控把下一层的节点混进当前层的vector。5.2 BFS拓扑排序入度为0的节点队列拓扑排序解决的是“有依赖关系的任务谁先谁后”的问题。Kahn算法用队列实现BFS思路非常清晰不断把入度为0的节点入队一个个出队并在每次出队时把这个节点能到达的邻居入度减一。邻居入度一旦归零意味着它的所有前置依赖都已经处理完可以入队了。std::vectorint topoSort(int n, const std::vectorstd::vectorint edges) { std::vectorint indegree(n, 0); std::vectorstd::vectorint adj(n); for (const auto e : edges) { adj[e[0]].push_back(e[1]); indegree[e[1]]; } std::queueint q; for (int i 0; i n; i) { if (indegree[i] 0) q.push(i); } std::vectorint res; while (!q.empty()) { int u q.front(); q.pop(); res.push_back(u); for (int v : adj[u]) { if (--indegree[v] 0) q.push(v); } } // 出现环时res长度不足n return res.size() n ? res : std::vectorint{}; }这里queue的作用是保存“当前可以直接执行的候选任务”。queue本身不承担任何逻辑判断它像一个传送带入度为0的任务被放在传送带上一个个被消化。如果最终res长度小于n说明图中存在环——有些节点的入度永远不会归零永远等不到被处理的机会。5.3 滑动窗口最大值用deque实现单调队列滑动窗口最大值问题在很多地方都叫“单调队列”。它用的数据结构实际上是deque而不是queue但和queue的FIFO思想同源。先看代码。std::vectorint maxSlidingWindow(const std::vectorint nums, int k) { std::vectorint res; std::dequeint dq; // 存下标队首到队尾单调递减 for (int i 0; i (int)nums.size(); i) { // 1. 删除窗口外的元素窗口左边界离开 if (!dq.empty() dq.front() i - k) dq.pop_front(); // 2. 删除队尾所有比当前元素小的元素 while (!dq.empty() nums[dq.back()] nums[i]) dq.pop_back(); // 3. 当前元素入队 dq.push_back(i); // 4. 窗口形成后队首就是最大值 if (i k - 1) res.push_back(nums[dq.front()]); } return res; }这个算法的思路是维护一个“从队首到队尾递减”的下标队列。队首永远是当前窗口最大值。每次滑动窗口先看看队首下标是否已经被滑出窗口左边界如果是就弹出然后清理队尾所有比新元素小的元素因为它们在新元素存在的整个生命周期里永远不可能成为最大值。剩下的数字从队首到队尾是一个递减序列队首直接取最大值。为什么用deque因为需要两端同时操作队首要弹出过期的元素队尾要弹出较小的元素再压入新元素。这个双端操作的需求恰恰是deque的设计初衷。这里也能看出适配器和算法场景是密不可分的正确的数据结构选型往往直接决定了算法能不能写出O(n)的复杂度。6. 实战中的易错点与选型建议6.1 queue和stack没有clear()清空方式的代价用惯了vector很多人会自然地以为queue会有clear()结果编译直接报错。stack和queue这两个适配器故意不提供clear()接口。清空它们常见做法是// 方式1pop到空 while (!q.empty()) q.pop(); // 方式2直接用临时对象赋值 q std::queueint(); // 方式3stack同理 std::stackint emptyStack; s.swap(emptyStack);方式1是O(n)的需要逐个调用pop。方式2和方式3实际上是O(1)的只是把内部底层容器的所有权整个换掉了。工程代码里推荐直接用方式3swap是成员函数开销极小。在面试或笔试题里如果要求“清空栈/队列”这些细节是能反映功底的。6.2 不可遍历的接口设计为什么不是缺陷stack和queue没有迭代器很多人刚接触的时候抱怨“不方便”。但换个角度想这反而是设计者刻意为之的防御。vector之所以强大是因为它承诺随机访问和遍历能力。但栈的价值恰恰在于“只能碰栈顶”队列的价值在于“只能从头进出”。一旦允许遍历就能绕过数据结构的语义限制直接摸到内部状态。限制接口本质上是保护数据结构操作的正确性。如果在实际开发中你真的需要遍历一个栈里的全部元素合理的做法不是“给栈加迭代器”而是退一步审视设计这里到底需不需要栈也许vector本身才是更合适的容器。6.3 vector当栈使可以queue别硬上list我实际写代码的经验是栈的实现用std::stack很顺手但如果我自己要写一个需要频繁遍历的栈结构会直接用vector配合size成员手动维护栈顶位置。vector的内存连续性带来的缓存优势在大量访问场景下非常明显。stack的top()按常数时间返回栈顶的引用本质上也只是vector.back()的包装。queue的选型就没那么大自由度了。如果数据量小、且不需要随机访问list能勉强当queue底层但每个元素多存一两个指针cache不友好。deque在绝大多数情况下是平衡点。只有在极端低延迟、队列长度极长的场景我才会考虑自己写环形数组来替代——但那个场景我会直接用std::vector维护head/tail两个下标而不是真的去“实现一个queue”。6.4 性能实测中的几个心得最后说几个我实际调试和测试中遇到的教训。deque的operator[]确实比vector慢。差别不大大概几个百分点但在百万级以上的循环里可以稳定复现。如果写的是热路径代码而且元素数量充足vector优先。优先使用emplace而非push。C11之后stack和queue都转发支持emplace。emplace直接在底层容器中构造对象免掉了“临时对象构造 移动拷贝”两步。对string这种非平凡类型收益尤其明显。我实测过emplace比push加移动构造省掉一个临时string的构造和析构在百万次入栈场景下能差出肉眼可见的时间。swap是个被低估的成员函数。stack和queue都带swap成员交换两个栈或两个队列代价极低。实测它只是交换底层容器的内部指针不会搬动任何元素。在需要批量重建数据结构的场景先用临时对象swap一下比逐个pop快几个数量级。STL真正要做的事不是替你保存数据而是在需要的地方用最少的状态变化完成对数据的操作。适配器只是把这个哲学用到了极致而已。