企业官网建设流程全解析

stack 和 queue 这两个容器适配器，大概是 STL 里最容易上手、也最容易被人低估的工具。很多初学者一开始以为它们就是数组加了个壳，背完 push、pop 就算完事，等真正刷题或者写项目时，才发现连“为什么默认底层容器是 deque”“能不能遍历”“怎么清空”都答不上来。这篇笔记就按我的实际学习过程来写：先讲清容器适配器到底适配了什么，再逐个拆 stack 和 queue 的接口、场景、底层选型，最后给出一组能直接跑的简易实现和几个高频坑位。适合正在啃 STL 的初学者，也适合想快速复习的人。

1. 容器适配器：理解 stack 和 queue 的第一步

1.1 适配器模式在 STL 里长什么样

先抛出问题：stack 和 queue 严格来说不是“容器”，而是“容器适配器”。这个说法很多人第一次看到会愣住，其实意思很简单：它们自己并不存储数据，而是把某个现成容器（默认是 deque）包装一层，只暴露最符合某种数据结构语义的少数接口。

拿生活场景打比方：底层容器就是仓库，stack 是仓库门口那个“只能从顶部放取”的窗口，queue 是“只能从一端进、另一端出”的收银排队通道。你把底层的 deque 理解成真正的货架，stack/queue 就是贴在货架上的使用规则，规则直接限定了你能怎么操作。

这样做的好处是编译器层面帮你减少错误：栈只能 push、pop、top，队列只能 push、pop、front、back。你想要“从栈中间抠一个元素出来”，编译器直接报错，根本进不了逻辑。

1.2 模板参数结构：三层关系

标准库中，stack/queue 的模板声明如下：

template<class T, class Container = std::deque<T>> class stack; template<class T, class Container = std::deque<T>> class queue;

两个模板参数，第一个 T 是元素类型，第二个 Container 是底层容器类型，默认是std::deque<T>。看到这你就明白了，适配器的本质就是“组合 + 接口裁剪”：内部持有 Container 类型对象，对外的接口调用全部转发给底层容器的对应操作。

具体映射关系很直白：

• stack::push 对应 Container::push_back；
• stack::pop 对应 Container::pop_back；
• stack::top 对应 Container::back；
• queue::push 对应 Container::push_back；
• queue::pop 对应 Container::pop_front；
• queue::front/back 对应 Container::front/back。

这套对应关系记住了，后面手动实现或者换底层容器时心里就有底。

1.3 为什么默认底层容器是 deque

官方默认用 deque，实际是综合考量的结果。deque 本身支持两端高效插入删除，还拥有随机访问能力。对 stack 来说，只需要尾部操作；对 queue 来说，只需要尾部插入加头部删除。deque 两头操作都是均摊 O(1)，内存不像 vector 那样是连续单块，而是分段的，插入删除时不会把所有旧元素整体搬移。

用 vector 也可以做 stack，但 vector 尾部插入有扩容搬移成本；做 queue 更麻烦，pop_front 会空出头部，元素整体前移，O(n) 开销。用 list 虽然两端插入删除是 O(1)，但每个节点有额外指针开销，访问节点时缓存局部性差，频繁分配内存，整体性能反而容易输给 deque。这一块的详细对比后面我会单独展开。

2. stack 实战拆解：后进先出的正确打开方式

2.1 接口虽然少，细节别踩错

stack 的全部公开接口就六个：push、emplace、pop、top、empty、size。日常最常用的写法是这样：

#include <stack> #include <iostream> int main() { std::stack<int> st; st.push(10); st.push(20); st.emplace(30); // 原地构造，减少一次拷贝/移动 std::cout << "top=" << st.top() << "\n"; // 30 st.pop(); // 弹出 30，pop 不返回元素 std::cout << "size=" << st.size() << "\n"; // 2 while (!st.empty()) { std::cout << st.top() << " "; // 20 10 st.pop(); } return 0; }

这里有几个新手必踩的点：

• top 只管查看，不弹出；pop 只管弹出，不给返回值。这是刻意设计的，避免出现“拿到元素拷贝后再弹出，拷贝优化掉导致返回悬空引用”这类复杂问题。
• 入栈用 emplace 比 push 更像“就地构造”。当元素类型不是内置类型时，emplace 通常能少一次临时对象的构造开销。
• empty 判断要放在 top 之前。空栈调用 top 是未定义行为，可能直接崩，也可能返回一个垃圾值，隐患极大。

2.2 括号匹配：最经典的栈算法

我认为初学者第一个该手写的栈算法就是括号匹配。它把栈“最近匹配”的特性体现得最清晰：左括号入栈，遇到右括号时，拿栈顶和它比对。

#include <stack> #include <string> #include <unordered_map> bool isValidParentheses(const std::string& s) { std::stack<char> st; std::unordered_map<char, char> pairs = { {')', '('}, {']', '['}, {'}', '{'} }; for (char c : s) { if (c == '(' || c == '[' || c == '{') { st.push(c); } else { if (st.empty()) return false; // 右括号过多 char top = st.top(); if (pairs[c] != top) return false; // 类型不匹配 st.pop(); } } return st.empty(); // 左括号过多 }

这段代码背后的算法逻辑就一句话：最近出现的左括号先被匹配。这是栈“后进先出”的来源。写完这段，你会体会到 top 和 pop 分离带来的方便——弹出前必须先看栈顶，确认匹配再弹。

2.3 逆波兰表达式求值：栈处理计算顺序

另一个高频算法题是逆波兰表达式（后缀表达式）。数字直接入栈，遇到运算符弹出两个操作数，算完再把结果压回去。需要注意弹出顺序：第一个弹出的应该是右操作数，第二个才是左操作数。

#include <stack> #include <vector> #include <string> int evalRPN(const std::vector<std::string>& tokens) { std::stack<int> st; for (const std::string& t : tokens) { if (t == "+" || t == "-" || t == "*" || t == "/") { int rhs = st.top(); st.pop(); int lhs = st.top(); st.pop(); if (t == "+") st.push(lhs + rhs); else if (t == "-") st.push(lhs - rhs); else if (t == "*") st.push(lhs * rhs); else st.push(lhs / rhs); } else { st.push(std::stoi(t)); } } return st.top(); }

这里我专门用 lhs/rhs 命名，就是提醒自己别写反。减法或除法写反符号，整个结果就错了。实际刷题时这个坑相当常见，尤其是连写两三个运算符时，稍不留神就把操作数顺序颠倒了。

2.4 栈还能用来干什么

除了括号匹配和表达式求值，栈还有一个高频场景是模拟递归。递归函数调用本身就是在系统栈上逐层压栈，自己用栈改写递归时，相当于把递归的“栈帧”显式化。

另一类是撤销（Undo）操作。编辑器、绘图工具里，用户每执行一次操作就 push 到操作栈，执行撤销就 pop 一次，把状态回退到上一帧。这个模型天然对应栈，比写一堆状态变量靠谱得多。

3. queue 实战拆解：先进先出的调度利器

3.1 接口与使用提示

queue 的接口和 stack 相似，但方向不同：front 取队头，back 取队尾，pop 弹出队头，push 在队尾插入。

#include <queue> #include <iostream> int main() { std::queue<int> q; q.push(1); q.push(2); q.push(3); std::cout << q.front() << "\n"; // 1，队头是1 std::cout << q.back() << "\n"; // 3，队尾是3 q.pop(); // 弹出1 std::cout << q.front() << "\n"; // 2 return 0; }

最容易犯的错是把 stack 的 top 习惯带到 queue：一上来就找 q.top()，然后编译报错。queue 没有 top，只有 front/back。front 是队列中第一个要被处理的数据，back 是刚入队还没来得及处理的数据。这两个概念搞混，写异步任务队列时很容易拿到错数据。

3.2 广度优先搜索：queue 的天然舞台

BFS（广度优先搜索）是 queue 最典型的算法场景。因为 BFS 要求逐层扩展，先访问到的节点的邻居，比后访问到的节点的邻居先被处理，这正好就是 FIFO 语义。

#include <queue> #include <vector> void bfs(const std::vector<std::vector<int>>& graph, int start) { std::vector<bool> visited(graph.size(), false); std::queue<int> q; visited[start] = true; q.push(start); while (!q.empty()) { int cur = q.front(); q.pop(); // 处理当前节点 // 把当前节点的所有未访问邻居入队 for (int next : graph[cur]) { if (!visited[next]) { visited[next] = true; q.push(next); } } } }

这里有两个关键点：

• 节点入队的瞬间就标记 visited，而不是弹出时才标记。否则同一个节点可能被多个邻居重复入队，队列里会出现大量重复，算法性能会退化，极端情况下甚至出错。这是 BFS 里最经典的一个坑。
• q.front() 之后立即 pop，取队头和出队是两个动作，必须先拿到 front 保存好，再 pop。顺序写反，就取不到当前节点了。

3.3 生产者消费者与任务队列

实际工程里，queue 常被用来做任务调度：生产者把任务 push 到队列尾部，消费者从队列头部取任务处理。这个模型天然是“先提交的先执行”，而且方便做排队限流。

但要注意，标准库 queue 本身不是线程安全的，多线程环境下直接 push/pop 会数据竞争，必须配合互斥锁。C++ 标准并没有直接提供线程安全的 queue，concurrent queue 一般来自第三方库或自己封装，所以别拿 std::queue 直接往多线程代码里扔。

一个简单的封装思路是：用互斥锁保护 push 和 pop 两个操作，生产者调用 pushTask，消费者调用 popTask，内部再加一个条件变量，让消费者在队列为空时等待。

3.4 queue 不适合做什么

queue 不适合用来做需要“插队”的场景。比如紧急任务要优先处理，队列的 FIFO 语义就不支持。这时候要么结合优先级队列 priority_queue，要么实现带优先级的自定义结构。

另外，queue 不提供随机访问，你没法通过下标查看某个元素，只能从队头一个个出队来看。这在调试时会多一步折腾，通常我会开一个临时队列，把元素从队头逐个挪出来观察。

4. 底层容器选型：为什么默认 deque，什么时候该换

4.1 底层容器对比表

从表里能直接看出 deque 为什么是默认答案：它同时满足 stack 只需要尾端操作、queue 需要头尾两端操作的需求，而且不会像 list 那样牺牲缓存局部性。

有些资料会说“vector 扩容时搬移元素”，这确实存在，但你从哪个方向理解很重要。stack 本身只需要 push_back/pop_back，vector 完全没问题；但 queue 需要 pop_front，vector 就不行了，pop_front 之后所有元素都要前移一位，复杂度 O(n)。所以如果你想给 stack 换 vector，技术上完全允许；想给 queue 换 vector，就要承担 O(n) 弹出代价。

4.2 什么时候换成 vector

stack 换成 vector 的合法写法是：

std::stack<int, std::vector<int>> st;

这样的好处是：如果你能预估元素量，可以在构造前先 reserve 好内存，减少扩容搬移。举例：

std::vector<int> reserved; reserved.reserve(100000); // 一次分配到位 std::stack<int, std::vector<int>> st(std::move(reserved));

这里用 std::move 把预先 reserve 好的 vector 移动进 stack，比直接 push 十万个元素反复扩容省很多分配开销。注意，传入的 vector 会被移动进 stack 内部的容器对象，构造完之后它本身不再负责存储。

如果你担心 vector 的扩容搬运在多线程环境导致指针引用抖动，那换 vector 反而会增加扩容风险。deque 的扩容只分配新块，已存在的元素不搬位置。所以多数场景下普通开发不用换。

4.3 什么时候换成 list

list 的插入删除操作很便宜，但节点缓存局部性差。stack/queue 本来就只操作两端，deque 已经两头都在 O(1)，list 的优势在这里发挥不出来。

唯一值得考虑 list 的是：底层容器元素可能被外部长期持有引用或指针，并且容器还会继续增长。deque 在两端插入时，已存在的元素引用是稳定的（这是标准规定的行为），但为了可移植性和代码审查的省心，有些人倾向于直接用 list，因为节点地址从生到死都不变。工程上很少遇到这种情况，我的判断标准是：如果连“元素引用会不会失效”都要担心，那说明对适配器的使用有点过度了，先重新审视设计更合理。

5. 手写一个简易 stack/queue：把适配器思想落地

5.1 模板化实现 stack

看再多接口说明，不如动手写一个能跑的简易版。理解了适配器就是“套壳”，用模板写出来非常快：

#include <deque> template<typename T, typename Container = std::deque<T>> class MyStack { public: void push(const T& value) { data_.push_back(value); } void pop() { data_.pop_back(); } T& top() { return data_.back(); } const T& top() const { return data_.back(); } bool empty() const { return data_.empty(); } size_t size() const { return data_.size(); } private: Container data_; };

这个实现和标准库的思路完全一致：内部持有一个 Container 对象，接口全部转发给底层容器。模板参数支持自定义底层容器，所以以后你想换成 vector 或 list，只要这些容器提供 back、push_back、pop_back，就能直接套用。

一个细节：pop 通常定义为 void，这是刻意的。如果 pop 返回被弹出元素，必须先拷贝再删除，而 top 返回引用又方便查看栈顶，二者职责分离最清晰。

5.2 模板化实现 queue

queue 的自定义实现也一样，只是转发方向不同：

#include <deque> template<typename T, typename Container = std::deque<T>> class MyQueue { public: void push(const T& value) { data_.push_back(value); } void pop() { data_.pop_front(); } T& front() { return data_.front(); } const T& front() const { return data_.front(); } T& back() { return data_.back(); } const T& back() const { return data_.back(); } bool empty() const { return data_.empty(); } size_t size() const { return data_.size(); } private: Container data_; };

如果把底层容器模板参数换成 vector，这个 MyQueue 在 pop 时就会调用 vector::pop_front，编译直接报错。这其实是个很好的“安全网”：标准库通过适配器接口刻意隐藏了底层容器的自由度，手动实现时你反而能更真切体会到，为什么默认底层容器是 deque 而不是 vector，因为 vector 根本没有 pop_front。

5.3 给简易实现补上 emplace

标准库 stack/queue 还提供 emplace 接口，用来在底层容器中“原地构造”元素。简易版可以顺手加上：

template<typename... Args> void emplace(Args&&... args) { data_.emplace_back(std::forward<Args>(args)...); }

注意这里用了可变参数模板和完美转发，需要对 C++11 的引用折叠有基本认识。如果看不懂，可以先记结论：emplace 比 push 多了“把参数直接传给底层构造函数”的能力，能少构造一个临时对象。

6. 实战中经常踩的坑：问题排查与避坑经验

6.1 高频问题速查表

6.2 清空 stack/queue 的两种做法

stack 和 queue 都没有像 vector 那样的 clear 接口，但清空完全可以通过赋值完成：

std::stack<int> st; st.push(1); st.push(2); st = std::stack<int>(); // 新对象整体赋值过去 std::queue<int> q; q.push(10); q.push(20); q = std::queue<int>();

利用临时对象赋值也是常见写法。还有更“炫技”一点的写法是：

std::stack<int>().swap(st);

前提是 C++11 之后标准库为容器适配器提供了 swap 成员函数。这个写法本质是让一个空临时对象与 st 交换内部底层容器，能把旧元素带来的内存也一并释放干净。实际项目里我更喜欢直接赋值空对象，可读性好，大多数人一眼就能看懂。

6.3 调试小技巧：如何查看栈里的内容

因为 stack/queue 不提供迭代器，直接遍历是做不到的。调试时我一般用两个办法：

• 通过业务逻辑把元素逐个转移到临时栈，再转移回来：

std::stack<int> st; st.push(1); st.push(2); st.push(3); std::stack<int> reversed; while (!st.empty()) { reversed.push(st.top()); st.pop(); } // 现在 reversed 里从栈顶往下的顺序是 3, 2, 1 while (!reversed.empty()) { std::cout << reversed.top() << " "; reversed.pop(); }

这个方法虽然会改变原栈内容，但配合移动语义恢复回去也不算麻烦。调试时要注意别让临时栈残留数据污染后续逻辑。

• 另一个思路是在自定义类里把底层容器作为 protected 成员暴露出来。标准库的实现虽然技术上访问不到，但在很多实现中有 protected 字段，比如std::stack<T, Container>::c。不过这属于未标准化的实现细节，我建议只在自己自定义的容器里这样做，别依赖标准库的私有实现。

6.4 关于拷贝和内存的小心得

stack/queue 的拷贝会把整个底层容器全部拷贝一遍，元素量大时开销相当可观。如果你只是想把状态快照下来，建议显式拷贝到 vector/deque 再处理，还能保留随机访问能力。

用 emplace 代替 push 是一个很有效的优化点。对自定义类型，push 往往经历“构造临时对象 -> 拷贝/移动到底层容器 -> 销毁临时对象”三步，emplace 则直接把构造参数转发到底层容器，少掉一次临时对象往返。实测在容器元素几十万量级时，这个差距还是肉眼可见的。

我个人经验是：每次要在“该用 stack 还是 queue”上犹豫时，先问自己一个问题——最新来的数据，是要最先处理，还是最后处理？最先处理就 queue，最后处理就 stack。这个标准在绝大多数场景下都能把方向定对。栈和队列虽然简单，但背后是“后进先出”和“先进先出”两大思维模式，写一遍简易实现、刷几道经典题、踩过几次空容器访问的坑之后，它们就不再是“背接口”的负担，而会成为手边非常趁手的工具。