提到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，把三种容器摆在一起比较就一目了然了。

vector支持尾部O(1)插入，但头部插入是O(n)，所以它可以做栈的底层，没法做队列的底层——队列需要pop_front，vector的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::deque<T>> 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::deque<T>> 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::stack<int, std::vector >，牺牲push_front的能力换来更紧凑的内存布局；想专门定制某种特殊内存池容器也完全可以，只要新容器满足接口要求。

这样设计带来的灵活度，来源于适配器本身“不拥有数据”的本质。底层容器是提供给适配器的服务方，双方只有接口约定，没有血缘关系。这也是为什么标准库里stack/queue的声明长这样：

template<class T, class Container = std::deque<T>> class stack; template<class T, class Container = std::deque<T>> 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系列。C++11之后标准库容器支持emplace()，在底层容器内直接构造元素，省掉一次移动拷贝。

把这几项一并加上，代码行数会多不少。不过理解核心语义的话，最基本的版本已经足够。写模拟实现的意义不在于和标准库逐字节对齐，而在于通过亲手转发接口，彻底体会到“适配器”三个字究竟在说什么。

4. 算法实战一：stack的三个典型场景，从最近匹配到延迟匹配

4.1 括号匹配：栈为何天然适合“最近匹配”

栈最直观的算法价值，是处理“最近关联”问题。给定一个只包含括号的字符串，判断括号是否合法闭合，是再经典不过的入门题。

bool isBalanced(const std::string& s) { std::stack<char> 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::vector<std::string>& tokens) { std::stack<int> 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::vector<int> dailyTemperatures(const std::vector<int>& temperatures) { int n = temperatures.size(); std::vector<int> res(n, 0); std::stack<int> 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::vector<std::vector<int>> levelOrder(TreeNode* root) { std::vector<std::vector<int>> res; if (!root) return res; 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* 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()会不断变大。如果不先固定layerSize，for循环会失控，把下一层的节点混进当前层的vector。

5.2 BFS拓扑排序：入度为0的节点队列

拓扑排序解决的是“有依赖关系的任务谁先谁后”的问题。Kahn算法用队列实现BFS，思路非常清晰：不断把入度为0的节点入队，一个个出队，并在每次出队时把这个节点能到达的邻居入度减一。邻居入度一旦归零，意味着它的所有前置依赖都已经处理完，可以入队了。

std::vector<int> topoSort(int n, const std::vector<std::vector<int>>& edges) { std::vector<int> indegree(n, 0); std::vector<std::vector<int>> adj(n); for (const auto& e : edges) { adj[e[0]].push_back(e[1]); indegree[e[1]]++; } std::queue<int> q; for (int i = 0; i < n; ++i) { if (indegree[i] == 0) q.push(i); } std::vector<int> 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::vector<int>{}; }

这里queue的作用是保存“当前可以直接执行的候选任务”。queue本身不承担任何逻辑判断，它像一个传送带，入度为0的任务被放在传送带上，一个个被消化。如果最终res长度小于n，说明图中存在环——有些节点的入度永远不会归零，永远等不到被处理的机会。

5.3 滑动窗口最大值：用deque实现单调队列

滑动窗口最大值问题，在很多地方都叫“单调队列”。它用的数据结构实际上是deque，而不是queue，但和queue的FIFO思想同源。先看代码。

std::vector<int> maxSlidingWindow(const std::vector<int>& nums, int k) { std::vector<int> res; std::deque<int> 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()接口。清空它们，常见做法是：

// 方式1：pop到空 while (!q.empty()) q.pop(); // 方式2：直接用临时对象赋值 q = std::queue<int>(); // 方式3（stack同理） std::stack<int> emptyStack; s.swap(emptyStack);

方式1是O(n)的，需要逐个调用pop。方式2和方式3实际上是O(1)的，只是把内部底层容器的所有权整个换掉了。工程代码里推荐直接用方式3，swap是成员函数，开销极小。在面试或笔试题里，如果要求“清空栈/队列”，这些细节是能反映功底的。

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。C++11之后，stack和queue都转发支持emplace。emplace直接在底层容器中构造对象，免掉了“临时对象构造 + 移动拷贝”两步。对string这种非平凡类型收益尤其明显。我实测过emplace比push加移动构造省掉一个临时string的构造和析构，在百万次入栈场景下能差出肉眼可见的时间。

swap是个被低估的成员函数。stack和queue都带swap成员，交换两个栈或两个队列，代价极低。实测它只是交换底层容器的内部指针，不会搬动任何元素。在需要批量重建数据结构的场景，先用临时对象swap一下，比逐个pop快几个数量级。

STL真正要做的事不是替你保存数据，而是在需要的地方，用最少的状态变化完成对数据的操作。适配器只是把这个哲学用到了极致而已。