深入理解 C++ STL：stack 和 queue 的底层原理与实现

系列文章：继string、vector、list之后，这篇聊stack和queue。 这两个容器在 STL 里有点特殊——它们不是"真正的容器"，而是容器适配器（Container Adapter）。 理解这个设计思想，比死记接口重要得多。

一、stack 是什么

1.1 概念与结构

栈（stack）是一种**后进先出（LIFO, Last In First Out）**的数据结构。

你可以把它想象成一摞盘子：放盘子只能放在最上面，拿盘子也只能从最上面拿。任何时候你都只能操作**栈顶（top）**这一个位置。

这个限制看起来很强，但正因为有这个限制，stack 在括号匹配、递归模拟、表达式求值、DFS等场景里极其好用。

1.2 接口一览

注意pop()不返回被弹出的值，这是 STL 的一贯设计：让操作和访问分开，避免在异常场景下同时承担两个职责。如果你想拿到栈顶的值再弹出，要先top()再pop()。

#include <stack> #include <iostream> using namespace std; int main() { stack<int> st; // 压栈 st.push(1); st.push(2); st.push(3); // 遍历：只能通过 top() + pop() 逐个取出 while (!st.empty()) { cout << st.top() << " "; // 先访问 st.pop(); // 再弹出 } // 输出：3 2 1（后进先出） return 0; }

二、stack 的底层：容器适配器

2.1 stack 不是"亲自实现"的容器

打开 STL 源码（libstdc++），你会发现 stack 的定义非常短：

template <class T, class Container = deque<T>> class stack { public: typedef typename Container::value_type value_type; typedef typename Container::size_type size_type; typedef Container container_type; protected: Container c; // 底层容器 public: bool empty() { return c.empty(); } size_type size() { return c.size(); } value_type& top() { return c.back(); } void push(const T& val) { c.push_back(val); } void pop() { c.pop_back(); } };

stack 自己不存储数据，它把所有操作转发给底层的容器c。这就是"适配器"的含义：用一个已有的容器，套上受限制的接口，暴露特定的行为。

2.2 默认底层是 deque，也可以换成 vector 或 list

// 默认：底层用 deque stack<int> st1; // 显式指定底层用 vector stack<int, vector<int>> st2; // 底层用 list 也可以（但性能差一些） stack<int, list<int>> st3;

为什么默认是deque而不是vector？

deque两端的 push/pop 都是 O(1)，而且没有vector那种整体扩容的开销。虽然vector在 push_back/pop_back 上也是均摊 O(1)，但deque的内存分配策略更稳定，不会出现大块搬移。实际使用中两者性能差异不大，大多数情况下用vector底层的 stack 会更缓存友好。

底层容器的要求：必须支持back()、push_back()、pop_back()、empty()、size()。满足这些的容器都能作为 stack 的底层。

2.3 手写一个 stack（基于 vector）

理解了上面的原理，手写一个就很简单：

namespace Jianyi { template <class T, class Container = std::vector<T>> class stack { public: void push(const T& val) { _con.push_back(val); } void pop() { // 不检查 empty，和 STL 保持一致：由调用者保证 _con.pop_back(); } T& top() { return _con.back(); } const T& top() const { return _con.back(); } bool empty() const { return _con.empty(); } size_t size() const { return _con.size(); } private: Container _con; }; }

几乎所有逻辑都是对_con的转发调用。这个设计的好处：stack 自己不需要管内存，底层容器全权负责。换底层容器只需要改模板参数，stack 的代码一行都不用改。

三、经典问题：最小栈

这是 LeetCode 155 题，也是 stack 最经典的面试题之一。

要求：设计一个栈，在 O(1) 时间内支持push、pop、top、以及getMin（返回栈中最小值）。

3.1 为什么这道题有难度

难点在于pop操作。如果只用一个变量_min记录当前最小值，那么当最小元素被弹出时，你不知道下一个最小值是什么——除非重新扫描整个栈，但那是 O(n)。

3.2 辅助栈方案

用两个栈：_elem存所有数据，_min存当前的最小值序列。

核心规则：

• push(x)时：x一定进_elem；如果_min为空，或者x <= _min.top()，则x也进_min。
• pop()时：先弹_elem；如果被弹出的值等于_min.top()，_min也弹一个。
• getMin()时：直接返回_min.top()。

为什么 push 用<=而不是<？

因为可能有重复的最小值。比如压入[3, 1, 1]，_min里应该是[3, 1, 1]，这样 pop 掉一个1之后，_min还剩[3, 1]，最小值仍然是1。如果用<，第二个1不会进_min，pop 掉第一个1时_min也跟着弹，getMin()就会返回错误的3。

class MinStack { public: void push(int x) { _elem.push(x); // 空栈，或者 x 小于等于当前最小值，才压入 _min if (_min.empty() || x <= _min.top()) _min.push(x); } void pop() { // 如果弹出的是当前最小值，_min 也要同步弹出 if (_elem.top() == _min.top()) _min.pop(); _elem.pop(); } int top() { return _elem.top(); } int getMin() { return _min.top(); } private: stack<int> _elem; // 数据栈 stack<int> _min; // 最小值栈 };

走一遍示例：

操作序列：push(5), push(3), push(7), push(3), pop(), pop()

操作 _elem _min getMin() push(5) [5] [5] 5 push(3) [5,3] [5,3] 3 push(7) [5,3,7] [5,3] 3 （7 > 3，不进 _min） push(3) [5,3,7,3] [5,3,3] 3 （3 <= 3，进 _min） pop() [5,3,7] [5,3] 3 （弹出的 3 == _min.top()，同步弹） pop() [5,3] [5,3] 3 （弹出的 7 != _min.top()，_min 不动）

空间上，_min最坏情况和_elem一样大（每个元素都递减时），平均情况远小于_elem。

四、queue 是什么

4.1 概念与结构

队列（queue）是**先进先出（FIFO, First In First Out）**的数据结构。

生活中最直觉的比喻就是排队：先来的人先出去，后来的只能在队尾等。

4.2 接口一览

#include <queue> #include <iostream> using namespace std; int main() { queue<int> q; q.push(1); q.push(2); q.push(3); while (!q.empty()) { cout << q.front() << " "; q.pop(); } // 输出：1 2 3（先进先出） return 0; }

4.3 queue 的底层实现

queue 同样是容器适配器，默认底层是deque：

template <class T, class Container = deque<T>> class queue { protected: Container c; public: bool empty() { return c.empty(); } size_t size() { return c.size(); } T& front() { return c.front(); } T& back() { return c.back(); } void push(const T& val) { c.push_back(val); } // 队尾入 void pop() { c.pop_front(); } // 队头出 };

queue 需要两端都能高效操作：队尾 push_back，队头 pop_front。vector的 pop_front 是 O(n)（要整体移动），所以queue 不能用 vector 做底层，必须用deque或list。

手写 queue：

namespace Jianyi { template <class T, class Container = std::deque<T>> class queue { public: void push(const T& val) { _con.push_back(val); } void pop() { _con.pop_front(); } T& front() { return _con.front(); } const T& front() const { return _con.front(); } T& back() { return _con.back(); } bool empty() const { return _con.empty(); } size_t size() const { return _con.size(); } private: Container _con; }; }

五、经典问题：用两个栈实现队列

LeetCode 232，也是面试里的高频题，考的是对 stack 和 queue 本质差异的理解。

5.1 思路

stack 是 LIFO，queue 是 FIFO，方向相反。两个 LIFO 叠在一起可以变成 FIFO。

设两个栈：_pushSt（专门入队）和_popSt（专门出队）。

规则：

• push(x)：直接压入_pushSt。
• pop()/front()：如果_popSt为空，将_pushSt所有元素倒入_popSt；然后对_popSt操作。

为什么这样正确？

假设入队顺序是 1, 2, 3：_pushSt从底到顶是 [1, 2, 3]，top 是 3。

把_pushSt全部倒入_popSt：[3, 2, 1]，top 是 1。

现在对_popSt做 pop()，弹出的是 1——正是最早入队的，符合 FIFO。

class MyQueue { public: void push(int x) { _pushSt.push(x); } int pop() { // _popSt 为空时才搬运，不是每次 pop 都搬 if (_popSt.empty()) _move(); int val = _popSt.top(); _popSt.pop(); return val; } int peek() // 返回队头，不弹出 { if (_popSt.empty()) _move(); return _popSt.top(); } bool empty() { // 两个栈都空，队列才真的空 return _pushSt.empty() && _popSt.empty(); } private: void _move() { // 把 _pushSt 全部倒入 _popSt while (!_pushSt.empty()) { _popSt.push(_pushSt.top()); _pushSt.pop(); } } stack<int> _pushSt; stack<int> _popSt; };

时间复杂度分析：

push是严格 O(1)。pop均摊 O(1)——每个元素最多被搬运一次（从_pushSt到_popSt），一旦搬过去之后所有 pop 都是 O(1)，直到_popSt耗尽才触发下一次搬运。

关键点：不要每次 pop 都触发搬运，只在_popSt为空时才搬。这是均摊 O(1) 的前提。

六、deque：被遗忘的底层主力

stack 和 queue 默认都用deque，它值得单独说一说。

6.1 deque 的结构

deque（double-ended queue，双端队列）和vector的最大区别在于内存布局：

• vector：一块连续内存，扩容时整体搬移。
• deque：分段连续，有一个"中控数组"（map），每个槽指向一个固定大小的内存块（buffer）。

这种结构让 deque 两端的 push/pop 都是 O(1)，且不需要搬移已有数据。代价是随机访问比 vector 慢（需要两次间接寻址），也更难做到缓存友好。

6.2 deque 的短板

正因为这个结构，deque 有几个明显弱点：

• 随机访问效率低于 vector（有额外的地址计算）。
• 中间插入/删除效率低（和 vector 一样要移动数据）。
• 不适合大量随机访问的场景。

所以 STL 没有把 deque 单独推荐为"通用容器"，它主要的价值就是作为 stack 和 queue 的底层，以及priority_queue不需要它但 queue 需要它。

七、priority_queue：加了优先级的队列

7.1 是什么

priority_queue（优先队列）每次弹出的不是最先入队的元素，而是优先级最高的元素。默认情况下是最大堆，即top()返回当前最大值。

#include <queue> #include <iostream> using namespace std; int main() { // 默认最大堆 priority_queue<int> pq; pq.push(3); pq.push(1); pq.push(4); pq.push(1); pq.push(5); while (!pq.empty()) { cout << pq.top() << " "; pq.pop(); } // 输出：5 4 3 1 1 return 0; }

7.2 接口

7.3 最小堆写法

// 方法1：仿函数 priority_queue<int, vector<int>, greater<int>> minHeap; // 方法2：插入时取负值（hack，不推荐） priority_queue<int> hackyMinHeap; hackyMinHeap.push(-val); // 存的时候取负 int top = -hackyMinHeap.top(); // 取的时候再取负

7.4 自定义类型的比较

struct Task { int priority; string name; }; // 仿函数：按 priority 降序（数字大的先出） struct CmpTask { bool operator()(const Task& a, const Task& b) { return a.priority < b.priority; // 注意：和 sort 的 cmp 语义一致 } }; priority_queue<Task, vector<Task>, CmpTask> pq;

底层实现：priority_queue的底层是堆（heap），默认用vector存数据，通过push_heap/pop_heap维护堆序。它和 stack/queue 一样是容器适配器，但底层容器是 vector 而不是 deque。

八、对比与选型总结

选底层容器的原则：

• 如果操作频繁在两端进行 →deque
• 如果只在尾部操作 →vector（更缓存友好）
• 如果需要任意位置插入/删除 →list（但随机访问差）

九、常见坑和注意事项

1. pop() 之前一定要判空

stack、queue、priority_queue的pop()和top()在容器为空时行为是未定义的（UB），不会抛异常，而是直接崩溃或产生随机结果。

// 错误写法 st.pop(); // 不确认 empty // 正确写法 if (!st.empty()) st.pop();

2. 用两个栈实现队列，empty() 要同时判断两个栈

// 错误 return _pushSt.empty(); // 可能 _popSt 里还有数据 // 正确 return _pushSt.empty() && _popSt.empty();

3. priority_queue 的比较器方向和 sort 的比较器一致，但效果相反

sort里cmp(a, b)返回 true 表示 a 排在 b 前面。priority_queue里cmp(a, b)返回 true 表示 a 的优先级低于b（a 比 b 晚出队）。

这是因为 priority_queue 默认是最大堆，堆的内部排序和"谁先出"的方向是反的。记忆方法：想要谁先出，就让比较器在比较它时返回 false。

4. stack 没有迭代器，无法用范围 for

stack<int> st; for (auto x : st) // 编译错误！stack 没有 begin()/end() cout << x; // 只能通过 top() + pop() 遍历（会破坏原栈） while (!st.empty()) { cout << st.top(); st.pop(); }

十、延伸思考

Q1：为什么 STL 要设计"容器适配器"这个概念，而不是直接写 stack 和 queue 的完整实现？

因为 stack 和 queue 的逻辑非常简单，核心是"接口限制"而不是"数据结构创新"。如果自己实现，需要重新处理内存管理、扩容、迭代器等一堆事情，而这些已经被 vector/deque/list 解决了。适配器模式让代码复用做到极致，同时给用户提供了换底层容器的灵活性。这是 STL 设计哲学的一个缩影：算法与容器分离，通用性优先。

Q2：deque 两端都是 O(1)，为什么不直接用 deque，而要有 stack 和 queue？

deque的接口太丰富了：随机访问、中间插入、两端操作全支持。直接用 deque 的话，调用者可能不小心（或者故意）做了不符合"栈/队列"语义的操作（比如从队头 pop 一个 stack）。stack和queue通过限制接口，让代码的意图更清晰，也让编译器帮你检查不合法的操作。这是类型系统即文档的思想。

Q3：如果要实现"双端栈"（两个栈共享一块数组，从两端往中间增长），该怎么做？

这是一个内存利用率更高的设计，常见于嵌入式或内存受限场景：

template <class T, size_t N> class DoubleStack { public: void pushLeft(const T& val) { if (_left + 1 == _right) throw overflow_error("full"); _data[_left++] = val; } void pushRight(const T& val) { if (_left + 1 == _right) throw overflow_error("full"); _data[--_right] = val; } // ... pop/top 类似 private: T _data[N]; size_t _left = 0; // 左栈栈顶（从左往右增长） size_t _right = N; // 右栈栈顶（从右往左增长） };

两个栈共用同一块内存，只有当它们加起来的元素数超过 N 时才会溢出，单独用其中一个栈时可以用满整块空间。

小结

• stack和queue不是独立实现的数据结构，而是对底层容器的接口适配。
• 默认底层是deque；stack也可以用vector，但queue不能（因为需要 pop_front）。
• 最小栈的核心是辅助栈同步维护最小值，push 用<=而不是<。
• 两个栈实现队列的核心是懒搬运：只有_popSt为空时才把_pushSt的数据倒过来。
• priority_queue是堆，push/pop 是 O(log n)，自定义比较器时注意方向。
• 三者都没有迭代器，体现了"限制接口 = 明确语义"的设计哲学。