假设你在餐厅后厨帮忙。厨师生好了一盘菜，放在一个只有顶部开口、底部封死的架子上。你每放一盘，就只能放在最上面；要拿走一盘，也只能拿最上面的那一盘。先放进去的菜，反而要等上面所有的菜都被端走之后才能拿出来。这种「后来者居上、先来者垫底」的规则，就是栈（stack）的形象写照，它的学名叫后进先出（LIFO，Last In First Out）。
再换个场景。食堂打饭的窗口前，同学们排成一队。第一个人先到，排在队头，先打饭、先离开；后来的人只能排在队尾，最后一个轮到自己。这种「先来先服务、后来候补」的规则，就是队列（queue），它的学名叫先进先出（FIFO，First In First Out）。
你可能已经在数据结构课程里和它们见过面了。今天我们要做的，是站在 C++ 标准模板库（STL，Standard Template Library，标准模板库，C++ 标准库里的那套容器、迭代器、算法、仿函数的总称）的角度重新认识 stack 和 queue——这一次你会发现，它们在 C++ 里甚至称不上「独立的容器」，而有一个专属的头衔：容器适配器（container adapter）。在学习它们之前，先补一个前置知识：什么是容器和模板。如果你还没接触过，这里我一次性讲透。
前置知识：容器、模板、类模板
容器（container）是 STL 里对「能存放一批同类型元素的数据结构」的统称。前面讲过的 vector 是动态数组，list 是带头尾的链表，string 也能视为一种容器。它们共同的特点是：底层自己分配内存、自己管理元素的增删查改，是「货真价实」的数据结构。说它们是「货真价实」，意思是它们真的拥有内存、真的负责把元素放进去、真的处理扩容搬移这些脏活累活。
模板（template）是 C++ 里「一份代码，多种类型」的机制。比如你要写一个能存 int 的栈，再写一个能存自定义点的栈，如果每个类型都抄一份代码，会累死人。模板允许你把类型「抽象」成一个参数，写一份通用代码，使用时再指定具体类型。这里的要点是：写模板时，T 只是一个「占位符」；只有当你在代码里写出 Box<int> 这种实例化（instantiation）的那一刻，编译器才会依据你传入的类型，真正生成一份专属代码。模板本身在编译期就被展开了，所以不会有运行时的派发开销——这是 C++ 模板高效的根本原因。
类模板（class template）就是针对类（class）的模板化。STL 里的容器几乎全是类模板，所以你在声明一个 vector 时要写 vector<int> 或 vector<string>——尖括号里那个 int、string，就是传给模板的「类型参数」。同样的，stack<int> 里的 int 表示这个栈存放整型元素，queue<string> 里的 string 表示这个队列存放字符串元素。
为了把「类模板」的感觉落到实处，先看一段最小的类模板能编译的代码：
#include <iostream>
using namespace std;
// 一个极简的"盒子"类模板：能存任意一种类型的单个值
template <class T>
class Box {
public:
void set(const T& v) { data_ = v; } // 存入一个值
T get() const { return data_; } // 取出当前值（注意这里是按值返回）
private:
T data_; // 底层真的存了一个 T 类型的成员
};
int main()
{
Box<int> intBox; // 用 int 实例化：data_ 是 int
Box<string> strBox; // 用 string 实例化：data_ 是 string
intBox.set(42);
strBox.set("hello template");
cout << intBox.get() << endl; // 输出 42
cout << strBox.get() << endl; // 输出 hello template
return 0;
}看出门道了吗？Box<int> 和 Box<string> 是两个不同的类型，但统统由 template <class T> class Box 这一份定义派生而来。所谓「类型参数」，就是尖括号里那个你可以替换的 T。后面学的 stack<int>、queue<string>，原理一模一样。
从生活中认识栈与队列
在进入 API 之前，先把这两个结构的「脾气」摸清楚，因为它俩的接口设计完全不同，根源就在各自的规则上。
先看栈。栈只允许在栈顶（top）进行操作——压入（push）往栈顶放，弹出（pop）从栈顶取，看栈顶（top）也只能看最上面那一个。除此之外别无他门。你永远没法直接查看栈中间的某个元素，更没法从栈中间插一个进去。这就是术语里的「后进先出」：最后一个进去的，最先出来。
想象一下浏览器的「后退」按钮。你依次访问了 A、B、C 三个页面，浏览器把你访问的历史按顺序压进一个栈：栈底是 A，中间是 B，栈顶是 C。当你点击「后退」，弹出的是最近访问的 C，回到 B；再点一次，回到 A。你要是从 B 直接跳到搜索之后返回，又往栈顶压一个 D——这个行为完全符合后进先出。再想想编辑器的「撤销」（Undo）功能，同样是维护一个操作记录栈，每次撤销弹出的都是最近那一步操作。
栈还有个你可能天天在用却从不察觉的存在：函数调用本身就是一个栈。当你写了 main 调用 funcA，funcA 调用 funcB，运行时的调用栈（call stack）会按 main → funcA → funcB 的顺序一层层压上去；而调用返回时，必然是 funcB → funcA → main 的顺序一层层弹出来——最晚被调用的 funcB 最先结束。这正是后进先出。你写的递归函数为什么无限递归会「栈溢出」（Stack Overflow）报错？因为每次递归调用都往调用栈压一层，压满内存就爆了。理解了这层，你对栈的「最近优先」直觉会牢固得多。
而队列恰好相反。它有两个「口」：一个是队尾（back），新元素从这里进来（入队 push）；一个是队头（front），元素从这里离开（出队 pop）。可以理解为一条单行道：只进不出那叫装口袋，只出不进不叫排队，必须「队尾进、队头出」才叫队列，这就是「先进先出」。
打字打到一半，但打印机一次只能打一份，于是各文档按提交先后在打印队列里排队：先提交的先打印，后来的排后面。微信消息的发送队列、网络里数据包的收发缓冲，底层都是一个又一个队列。操作系统里的线程池任务队列、生产者消费者模型，本质上也是「先来的任务先被处理」的先进先出。一言以蔽之：栈管「最近需要撤销的东西」，队列管「按顺序处理的东西」。
容器适配器：什么是适配器
现在进入本文最关键的概念——适配器（adapter）。
你真的去查 C++ 的标准库文档，会发现描述 stack 和 queue 时反复出现一句话：「容器适配器」（container adapter）。这到底是什么意思？
先解释「适配器」这个词本身。它最早来自软件开发中的设计模式——一套被反复验证、可以复用的代码设计经验。适配器模式的核心思想是：把一个类的接口，转换成一个使用者期望的接口。
打个比方。你家里买了一台某国生产的电器，插头是三孔的、还是两种不同标准，而你墙上的插座只有两孔。直接插，插不进去。怎么办？买一个转接头——这个转接头的一端和电器的三孔插头吻合，另一端和你墙上的两孔插座吻合，于是电器就能用上电了。这个转接头就是「适配器」：它没有自己发电，只是改变了插头的「接口」，让原本不匹配的双方对接起来。
C++ 里的容器适配器，道理一模一样。我们早就有了 vector、list、deque 这些「能装元素的容器」。但这些容器太「万能」了，什么操作都允许：你能从中间插、从中间删、任意下标访问。可栈和队列要的不是这种万能，栈只许「顶部进出」，队列只许「队尾进、队头出」。
于是 STL 的做法是：拿一个现成的底层容器垫底，外面包一层，只暴露受限的接口，把「万能容器」的接口磨成「栈」或「队列」该有的样子。这就是容器适配器的本质——它不是自建数据结构，而是在已有容器之上加约束，从而形成新的语义。
你在代码里体会一下会更清楚。下面用一个 deque 当底料，自己简单裹一个「栈」的感觉：
#include <deque> // 引入双端队列 deque（后面会细讲）
// 一个极简的栈适配器：内部包一个 deque，只暴露栈语义
template <class T>
class MyStack {
public:
void push(const T& x) { c_.push_back(x); } // 压栈：往底层容器尾部塞
void pop() { c_.pop_back(); } // 弹栈：把底层容器尾部删掉
T& top() { return c_.back(); } // 看栈顶：底层容器的尾元素
bool empty() const { return c_.empty(); } // 底层空则栈空
std::size_t size() const { return c_.size(); } // 底层元素个数即栈的大小
private:
std::deque<T> c_; // 底层真正的存储，只有一个 deque
};你看，这个 MyStack 从头到尾没有自己管理内存，全部操作都是「转发」给 c_（那个 deque）去做的。它自己只是对外制定了一套「只许顶部进出」的规矩。这就是适配器最直白的形态。
对称地，给你一个「队列适配器」的自制版。注意队列有两个口，所以接口里有两个取元素的函数——front 和 back：
#include <deque>
// 一个极简的队列适配器：同样只包一个 deque，但暴露的是两个口
template <class T>
class MyQueue {
public:
void push(const T& x) { c_.push_back(x); } // 入队：从尾部进
void pop() { c_.pop_front(); } // 出队：从头部出
T& front() { return c_.front(); } // 看队头：最早进来的那个
T& back() { return c_.back(); } // 看队尾：最晚进来的那个
bool empty() const { return c_.empty(); } // 底层空则队列空
std::size_t size() const { return c_.size(); } // 底层元素个数即队列大小
private:
std::deque<T> c_; // 底层真正的存储
};比较这两个自制适配器，你会瞬间明白一件事：栈的接口比队列少一个取元素函数，因为它只有「一个口」。 MyStack 里只有 top，MyQueue 里却有 front 和 back 两个——这正是后文 std::stack 用 top()、std::queue 用 front()/back() 的根源。
顺带一提，在 C++ 标准库的内部归类里，std::vector、std::list、std::deque 被正式划为「序列式容器」（sequence container），而 std::stack、std::queue、std::priority_queue 被划为「容器适配器」（container adapter），二者是并列的不同范畴。标题里的「容器」两个字，是要打引号的——它们离了底层容器什么都不是。
一句话记住：栈和队列不是「自己的结构」，是「借来的结构加规矩」。这是理解它俩 API 为什么这么少、为什么不带迭代器、为什么很多底层细节不用你操心的钥匙。
栈的实现与常用接口
打开代码，我们来实操 std::stack。使用它要包含头文件 <stack>。它的常用成员函数不多，加起来是六个（构造、判空、求大小、读写栈顶、入栈、出栈），我列成一张表：
| 接口 | 说明 |
|---|---|
stack() | 构造一个空栈 |
empty() | 判断栈是否为空，是返回 true，否则 false |
size() | 返回栈中元素的个数 |
top() | 返回栈顶元素的引用（不看栈顶以外的任何元素） |
push(val) | 把元素 val 压入栈顶 |
pop() | 把栈顶元素弹出（注意：它不返回被弹出的元素） |
你可能会疑惑：push 和 pop 名字前面那个 () 是干吗的？std::stack 是个类模板，push()、pop() 是它的成员函数（可以类比成对象的方法）；尖括号里的 int 是类型参数，表示这个栈放整型元素。所以上面表的写法里 push(val) 表示「调用成员函数 push，参数是 val」——这是文档里常见的简写方式，实际代码里是 stk.push(5); 这样调用。下面看完代码就一目了然。
读取栈的栈顶元素，用的是成员函数 top()，注意它返回的是引用。这是什么意思？意味着通过它不仅可以读取，还可以直接修改栈顶元素的值——比如 stk.top() = 100;，这行代码没有任何报错，它真的把栈顶元素改成了 100。这一点很多新手会忽略，但它恰恰解释了下一个常见疑问。
再补充两个接口细节。第一，top() 其实有两个重载：一个返回 T&（可以改），一个返回 const T&（只读）。当你对一个 const 栈调用 top() 时，编译器会自动选择 const 版本，防止你改它。新手通常意识不到这一幕，但它是 C++ 惯用法「重载决定读写权限」在容器上的典型体现。第二，std::stack 在 C++11 起还提供了 emplace()（原地构造，避免拷贝）和 swap()（交换两个栈，本质是交换底层容器，O(1)）；以及非成员的重载运算符 ==、!=、< 等，用来按元素逐一比较两个栈。这些作为进阶接口认识即可。
这里有个坑：pop 为什么不返回被删除的元素？
这是 stack 和 queue 面试里最高频的「灵魂拷问」。你看，top() 暴露了引用，那 pop() 为什么不直接返回栈顶元素，让你一口气「拿到并删掉」呢？很多人直觉上会觉得 int v = stk.pop(); 更省事。
标准库刻意不这么设计，原因主要有三条，层层递进：
第一，效率 / 拷贝代价。 pop 是要删除元素的，而栈顶元素类型 T 可能是任何类型——T 的拷贝可能代价高昂（比如是个大对象、是个 string）。让 pop 返回一个元素，就必须先把栈顶的那个 T 复制一份交给你，这会白白付出一次拷贝；而很多时候你根本不在乎被删的那个值，只想让它消失。为了大多数情况下用不到的值去付全款，不划算。
第二，可行性 / 可移动性。 有些类型根本没有拷贝构造（比如 unique_ptr，它被设计成只能移动、不能复制）。如果 pop 强制要求「返回一个 T」，那这种类型就根本塞不进栈，等于把 stack<T> 的使用范围砍掉一大截。这是纯实用性考量。
第三，异常安全（exception safety）。 这是最深的一条。设想设计成「先删掉元素、再把它的副本返回给你」：如果拷贝或移动的过程中抛出了异常，元素已经被删掉了、值却没能送达，数据就丢了，栈的强异常保证（要么成功、要么状态完全不变）就被击穿。把「读」和「删」拆成两个独立操作，正好各自保持语义干净：top() 只读、保证不抛异常或至少不破坏结构；pop() 只删、删完不用回头给任何人交差。这两步正交，任何一步都可以被单独妥善地处理。
而且退一万步，你完全有能力自己拼出「拿到并删掉」：先 top() 拿引用，读取值，再单独 pop() 删掉它。top() 已经返回了引用，这两个操作拆开，语义各自清晰，还能把「读」和「删」的成本正交分开——你不删的时候只是读，就完全不用付拷贝的代价。
所以记住这个铁律：pop 只负责删，不负责给你拿回来；想要栈顶的值，先 top() 再说。 补充一句很要紧的勘误：网上有些文章说「C++23 给 stack 加了 pop_top()」，这是不准确的。截至 C++23（也就是目前最新发布的标准），std::stack 和 std::queue 的 pop() 一律返回 void、不返回被删元素；虽然社区一直有人呼吁推进类似「拿到并弹出」的接口（例如标准提案 P3182 提出的 pop_value），但这个特性至今尚未进入任何正式标准，请勿在代码里依赖它。如果你实在想写成一行的便捷样子，可以自己包一个小函数，本质还是 top+pop 两步：
#include <stack>
// 网友自制的「拿到并弹出」助手——本质还是先把 top 的值拷出来再 pop
int popValue(std::stack<int>& st)
{
int v = st.top(); // 先读（这里为了简单按值拷贝，大对象请改成按需 move）
st.pop(); // 再删
return v; // 把拿到的值还给调用者
}看一段完整可编译的栈测试代码：
#include <iostream> // 引入输入输出流头文件，用于 cout/cin
#include <stack> // 引入 stack 容器适配器
using namespace std; // 使用 std 命名空间，简化 std:: 前缀
int main()
{
stack<int> stk; // 构造一个空栈，存放 int 元素
stk.push(1); // 1 入栈，现在栈里是 [1]，栈顶是 1
stk.push(2); // 2 入栈，现在栈里是 [1,2]，栈顶是 2
stk.push(3); // 3 入栈，现在栈里是 [1,2,3]，栈顶是 3
cout << "size = " << stk.size() << endl; // 输出元素个数：3
cout << "top = " << stk.top() << endl; // 只看不删：输出栈顶 3
stk.top() = 100; // top 返回引用，可以直接修改栈顶，把它改成 100
while (!stk.empty()) // 只要栈不空就循环
{
cout << stk.top() << " "; // 输出栈顶（最后压入的）先生成
stk.pop(); // 弹出栈顶，一个元素只看一次、删一次
}
cout << endl; // 换行，让输出更整洁
cout << "empty? " << stk.empty() << endl; // 弹空了，输出 1（表示 true）
return 0; // main 返回 0，程序正常结束
}运行这段代码，输出会是：
size = 3
top = 3
100 2 1
empty? 1
注意看最后一行输出：100 2 1 ——你现在对这个栈依次 pop，先出来的是最后压入的 100（我们改过的那个栈顶），然后是 2，最后是当初最先压入的 1。后进先出在这一刻体现得清清楚楚。
栈的经典入门：用「最小栈」体会栈的应用
栈最经典的一类面试题，叫最小栈（MinStack）。要求设计一个栈，除了常规的 push、pop、top，还要能在 O(1)（常数时间，即无论元素多少，花费时间基本不变）内取到当前栈里的最小值。思路是经典的双栈：一个 _elem 正常存元素，另一个 _min 同步记录「每个时刻的最小值」。压栈时，如果新元素比 _min 栈顶还小或相等，就顺手压进 _min；弹栈时，如果要弹的元素恰好是当前最小值，_min 也一起弹出去。
#include <stack> // 引入 stack
class MinStack {
public:
void push(int x) {
_elem.push(x); // 正常元素照常入栈
if (_min.empty() || x <= _min.top()) // 若最小栈为空或不大于当前最小值
_min.push(x); // 把这个新最小值也压入最小栈
}
void pop() {
if (_elem.top() == _min.top()) // 若被弹出的恰好是当前最小值
_min.pop(); // 最小栈的栈顶也要同步弹出
_elem.pop(); // 无论是否同步，元素栈都弹出
}
int top() { return _elem.top(); } // 栈顶元素，直接看元素栈
int getMin() { return _min.top(); } // 当前最小值，一眼取最小栈栈顶
private:
std::stack<int> _elem; // 保存所有元素的栈
std::stack<int> _min; // 保存历史最小值的栈
};这里有一个新手总写错、却非常关键的细节：压栈时的判断条件用的是 <=（小于等于），不是 <。 为什么？因为最小值很可能重复出现。假设连续压入两个 5：如果只压更小的（<），第二个 5 不会进 _min；那么当你弹走一个 5（它是当前最小值）时，_min 的栈顶还是那个 5，紧接着如果你把剩下的唯一一个 5 也弹走，_min 的栈顶却仍然记录着 5，可真实栈里已经一个 5 都不剩了——最小值就「阴魂不散」，错了。用 <= 的话，每个重复的最小值都会在 _min 里留一份，弹走一个就销掉一份，一一对应，绝不会错。
再看 pop() 的顺序：先比较 _min.top() == _elem.top()，再去弹 _elem。这一步的顺序不能反——要是先把 _elem.top() 弹了，就再也取不到「被弹出的那个值」去和 _min 比较了。
为什么 getMin 能 O(1)？因为 _min 的栈顶始终记录着当前栈的全局最小值：每次 push 时，若来了更小的就更新它；每次 pop 时，若把最小值弹出去了就回退到「弹之前的那个最小值」。这个技巧在很多需要「随时快速回答极值」的场景里都能派上用场。
队列的实现与常用接口
认识了栈，队列就顺理成章了。std::queue 使用要包含头文件 <queue>。它的常用接口是七项，但注意取端口的名字变了——栈用 top()，队列却用 front()（队头）和 back()（队尾）。原因很直白：栈只有一个「口」（顶部），队列有两个「口」（进在队尾、出在队头），所以分别要用两个函数来访问。
| 接口 | 说明 |
|---|---|
queue() | 构造一个空队列 |
empty() | 判断队列是否为空，是返回 true，否则 false |
size() | 返回队列中元素的个数 |
front() | 返回队头元素的引用（队里「最早进来的那个」） |
back() | 返回队尾元素的引用（队里「最晚进来的那个」） |
push(val) | 在队尾把 val 入队，新元素排到最后面 |
pop() | 将队头元素出队（同样不返回被弹出的元素） |
队列的 front()、back() 和栈的 top() 一样，返回的都是引用，都可以直接拿来修改对应元素。而 pop() 同样不返回被删的元素——原因和栈一模一样：避免拷贝大对象、保持「读」「删」分离。类比一下 top、front、back 的差别：栈只有一个口叫 top，队列进出的口不一样、所以有 front（出口）和 back（进口）两个名字。
这里把三个取元素的函数再掰开揉碎一次，帮你在命名上死记下规律：
- 栈只有栈顶一个出入口，所以只需要一个
top()，它既当入口又当出口。 - 队列有两个口：进的方向叫队尾 tail/back，出的方向叫队头 head/front，所以
push走back()那边、pop走front()那边、要看两个端点就得front()和back()各一次。
一句话：取元素的函数数量 = 需要关注的「口」的数量。 栈一个口→top，队列两个口→front 和 back。
和 std::stack 一样，std::queue 在 C++11 起也多了 emplace()、swap()，以及 ==、< 等比较运算符（按元素的先后顺序逐一比较）。这些都是顺手的便利，并非必须。
看完整代码验证一遍先进先出:
#include <iostream> // 引入输入输出流，用于 cout
#include <queue> // 引入 queue 容器适配器
using namespace std; // 使用 std 命名空间
int main()
{
queue<int> qu; // 构造一个空队列，存放 int 元素
qu.push(10); // 10 入队，排队：队头是10，队尾也是10
qu.push(20); // 20 入队，排队：队头是10，队尾是20
qu.push(30); // 30 入队，排队：队头是10，队尾是30
cout << "size = " << qu.size() << endl; // 元素个数：3
cout << "front= " << qu.front() << endl; // 队头（最早来的）：10
cout << "back = " << qu.back() << endl; // 队尾（最晚来的）：30
while (!qu.empty()) // 只要队列不空就循环
{
cout << qu.front() << " "; // 先输出队头
qu.pop(); // 队头出去，队伍整体前移一位
}
cout << endl; // 换行整洁输出
cout << "empty? " << qu.empty() << endl; // 全部出队，输出 1
return 0; // 程序正常结束
}输出：
size = 3
front= 10
back = 30
10 20 30
看到了吗？输出顺序 10 20 30 和入队顺序完全一致——先进先出。和栈的 100 2 1 形成鲜明反差：同样的三个元素，栈是倒着出来，队列是正着出来。这两个顺序的区别，是每种数据结构取舍的第一课。
底层容器：为什么是 deque
前面反复提到 stack 和 queue 是「包装」出来的容器适配器，那它们底层到底包的是谁？答案是——默认情况下，两者都包 std::deque。你可能还没听说过 deque，先记住：deque（读作 deck，是 double-ended queue 的缩写）= 双端队列，一种能在头部和尾部都高效插入删除的容器。关于它我们下一节专门展开，现在先解释「为什么选它」。
有人会问：栈明明只需要「尾部插入、尾部删除」，用 vector 不就行了吗？队列需要「尾部插入、头部删除」，这不就是 list 的拿手好戏吗？这么说没错——理论上，能用其他容器当底层。事实上标准库确实允许你换（下一节就演示）。
但为什么默认选了 deque？你得先捋清楚 stack 和 queue 的「需求画像」：它们不需要遍历（所以这两个容器压根没有迭代器，想从中间访问元素、遍历所有元素都没门），只需要在固定的一端（栈）或两端（队列）做操作。这个前提至关重要。
在这个前提下，对比三种候选：
- vector：尾部插入删除是 O(1)（速度快），但头插头删要搬移所有元素（把后面的元素整体往后挪），队列要用到头删，vector 吃不住。另外 vector 扩容时要把旧元素整体搬到新内存（虽然指数式扩容，但搬移本质还是搬），元素多时开销不小。
- list：两端插入删除都是 O(1)，很灵活。但链表每个节点都要额外存指针（前驱指针、后继指针），空间利用率低——为了放一个 int，得额外多花几十上百字节，内存开销远高于 vector 和 deque。而且链表节点是离散分配的，对 CPU 缓存很不友好，访问要到处跳，效率有隐性成本。
- deque：头尾插入删除都是 O(1)，扩容时不用搬移大量元素（它是分段连续存储，新增一段即可，下一节细讲），空间利用率又比 list 高。
所以对「只需两端操作、无需遍历」的 stack 和 queue 来说，deque 是两头都占优的均衡解：既具备 list 那样的头尾高效插入删除，又具备 vector 那样的连续内存高空间利用率，还避开了「扩容大搬移」和「节点指针开销」这两个短板。一句话：deque 对 stack/queue 的使用场景来说，是「既要又要还要」的最优默认值。
再用一个「引用是否失效」的视角补一刀，解释 deque 为什么比 vector 适合当 stack 的底层。vector 扩容时会把旧内存里的元素整体搬到新地址，导致已持有的指向元素的引用/指针全部失效——如果你 stack<int,vector<int>> 里先 int& r = st.top(); 拿到了栈顶引用，下一次 push 触发扩容，r 就悬空了（指向被释放的对象），再用就是未定义行为。而 deque 往两端插入、删除时，不会重定位已存在的元素，之前拿到的指向元素的引用依然有效（只有迭代器可能失效）。这个「到元素引用稳定」的特性，让 deque 当底层要比 vector 安全得多，也是默认选它的又一重专业理由。
这也是标准库文档里明确写的：stack 和 queue 默认以 deque 为底层容器，因为「栈和队列不需要遍历，只需在固定一端或两端操作」——deque 完美贴合这个特性。
如何改变底层容器（用 vector/list 作底层）
也许你就是对 deque 有顾虑，或者想用 stack 却希望底层是 vector，以便观察它的真实行为。没问题，std::stack 和 std::queue 都是类模板，第二个模板参数就是底层容器类型，而且带默认值 deque<T>。这一点正好呼应了开头讲的「类模板可以传多个类型参数」——stack/queue 的模板签名大致是 template<class T, class Container = deque<T>>，第一参数是元素类型，第二参数是底层容器，还给了默认值。
声明时要写成：
stack<int> s1; // 默认：底层是 deque<int>
stack<int, vector<int>> s2; // 显式指定：底层是 vector<int>
stack<int, list<int>> s3; // 显式指定：底层是 list<int>
queue<int> q1; // 默认：底层是 deque<int>
queue<int, list<int>> q2; // 显式指定：底层是 list<int>注意两个细节。第一，尖括号里 >> 在 C++11 之后的版本里可以连写（早期标准会把它误解析成右移运算符，需要写成 > > 空格隔开；如果你用的是老编译器，就加个空格，新编译器都支持连写）。第二，不是所有容器都能当底层，底层容器必须提供 stack 或 queue 需要的那几个操作：
- 栈的底层容器必须支持：
push_back（尾部入）、pop_back（尾部出）、back（看栈顶）、empty、size。所以vector、list、deque都满足。 - 队列的底层容器必须支持：
push_back（队尾入）、pop_front（队头出）、front（看队头）、back（看队尾）、empty、size。所以list、deque满足，但vector不满足——因为 vector 没有pop_front（头删要搬移，标准库干脆不提供）。所以你想用 vector 当 queue 的底层，是编译不过的，清清楚楚报错告诉你 vector 缺了pop_front。
这条规则的深层逻辑是这样的：适配器只是「约束」，不是「实现」。 它自己不产生任何新能力，一切皆来自底层容器。底层容器能干什么，适配器就敢让别人干什么；底层容器做不到的，适配器也只能摊手。所以「stack 能不能用 list 当底层」不是 stack 说了算，而是 list 有没有 push_back/pop_back/back——有就用得成。
下面这段代码，用 vector 当栈的底层并验证栈行为跟默认完全一致：
#include <iostream> // 引入 cout
#include <stack> // 引入 stack
#include <vector> // 引入 vector，用于当栈的底层容器
using namespace std; // 简化 std 前缀
int main()
{
stack<int, vector<int>> st; // 栈的底层显式指定为 vector
st.push(7); // 入栈 7
st.push(9); // 入栈 9
cout << st.top() << endl; // 栈顶：9
st.pop(); // 弹出 9
cout << st.top() << endl; // 栈顶又回到 7
return 0;
}之所以支持换底层，是因为适配器本来就是「把约束加到任意合适的容器上」——你想让栈底层用 vector、让队列底层用 list，只要那个容器能满足所需操作，就完全合法。这也正是「适配器」这个词的宽容之处。
栈与队列的经典应用
光会调 API 不够，这两个结构真正的价值在「用它们解决实际问题」。下面我们沿着课件题库的脉络，把最经典的几个场景逐个过一遍，每个都配可编译代码。
应用一：括号匹配
写代码时，编译器要检查 ( 与 )、[ 与 ]、{ 与 } 是否成对、嵌套正确。这个检查就是栈的经典应用：遇到左括号就压栈，遇到右括号就看栈顶是不是与之匹配的左括号——没匹配上或者栈是空的，就说明括号不合法；扫描完整个字符串后栈必须是空的，否则说明有左括号没闭合。
#include <iostream> // 引入 cout
#include <string> // 引入 string
#include <stack> // 引入 stack
using namespace std; // 简化 std
bool isValid(const string& s)
{
stack<char> st; // 用栈记录还没匹配的左括号
for (char c : s) // 逐个字符扫描（范围 for，C++11 起支持）
{
if (c == '(' || c == '[' || c == '{') // 遇到任意左括号
{
st.push(c); // 压栈，记下待匹配的左括号
}
else // 否则这是个右括号
{
if (st.empty()) // 栈空说明没有左括号可匹配
return false; // 直接判不合法，比如首字符就是 ')'
char open = st.top(); // 取出栈顶那个最近未匹配的左括号
st.pop(); // 它即将被匹配，从栈里移除
bool ok = (open == '(' && c == ')')
|| (open == '[' && c == ']')
|| (open == '{' && c == '}'); // 检查是否配成一对
if (!ok) // 配对不上，比如 '(' 遇到 ']'
return false; // 括号不合法
}
}
return st.empty(); // 全部扫描完，栈空才算全部闭合
}
int main()
{
cout << isValid("([]{})") << endl; // 嵌套合法，输出 1
cout << isValid("([)]") << endl; // 交叉不匹配，输出 0
cout << isValid("(()") << endl; // 左括号多，输出 0
cout << isValid(")(") << endl; // 右括号打头，输出 0
return 0;
}为什么栈合适？因为「检查括号」的本质是最近匹配：一个右括号，只可能和最近那个还没被匹配的左括号配对。而「最近未匹配」恰好就是栈顶。这种「只关心最近、需要一个一个回溯」的场景，栈是天然的答案。这段代码里还用到了范围 for（for (char c : s)）——一个 C++11 引入的语法，能让「遍历容器里的每个元素」写得更简洁，遇到不认识可以先记下：它等于「把 s 的元素逐个取出来放进 c」。
最后总结一下这个算法的四种「不合法」情形，你就知道这个 return st.empty() 为什么必不可少：
- 右括号打头：如
)，遇到时栈空 → 直接return false。 - 交叉错配：如
([)]，]遇到栈顶是(→ok为假 →return false。 - 左括号多：如
(()，扫描完栈里还残留(→ 靠末尾return st.empty()拦住。 - 成对但空栈收尾：如
(),最终栈空 → 合法。
应用二：栈的弹出压入序列
这是课件里仅次于最小栈的经典题：给定一个入栈序列 pushV 和一个出栈序列 popV，问 popV 有没有可能是某个栈（全程遵守「压入 pushV 的全部元素」这一约束下）真实的弹出顺序。解题的黄金思路是——用一个真实的栈把入栈出栈过程完整模拟一遍：一边按 pushV 的顺序往栈里压，一边看栈顶是不是此刻 popV 想要的元素，是就弹、不是就继续压；压到序列尽头还凑不出，就说明非法。
#include <iostream> // 引入 cout
#include <vector> // 引入 vector
#include <stack> // 引入 stack
using namespace std; // 简化 std
// 判断 popV 是否可能是 pushV 的一个合法出栈序列
bool isPopOrder(const vector<int>& pushV, const vector<int>& popV)
{
if (pushV.size() != popV.size()) // 个数不一样，谈不上序列合法
return false;
stack<int> s; // 用一个真实栈模拟入栈出栈全过程
int in = 0; // 指向 pushV 中下一个该入栈的位置
for (int x : popV) // 依次处理出栈序列里想要的每个元素
{
// 只要栈顶还不是 x、且还能压，就一直往里压
while (s.empty() || s.top() != x)
{
if (in < (int)pushV.size()) // 入栈序列还没耗尽
s.push(pushV[in++]); // 压入一个元素，下标后移
else
return false; // 全压完还凑不出 x，非法
}
s.pop(); // 栈顶正好是 x，说明该出栈了
}
return true; // 每个出栈元素都顺利模拟完，合法
}
int main()
{
vector<int> pushV = {1, 2, 3, 4, 5};
cout << isPopOrder(pushV, {4, 5, 3, 2, 1}) << endl; // 合法，输出 1
cout << isPopOrder(pushV, {4, 3, 5, 1, 2}) << endl; // 非法，输出 0
cout << isPopOrder(pushV, {1, 2, 3, 4, 5}) << endl; // 合法，输出 1
return 0;
}光看结论可能不踏实，手动推演第二条 {4,3,5,1,2} 为什么非法：想要 4 → 先压 1、2、3、4，再弹 4；想要 3 → 栈顶正是 3，弹 3；想要 5 → 压入 5，弹 5；想要 1 → 此刻栈顶是 2，而 pushV 已经全部压完（in 越界），再也凑不出 1 → 返回 false。合法与否，模拟一遍就知道，这就是「用栈验证栈」的巧妙之处。
应用三：逆波兰表达式求值
逆波兰表达式（Reverse Polish Notation）也叫后缀表达式，把运算符写在两个操作数之后，比如 ["2","1","+","3","*"] 等价于常见的 (2 + 1) * 3。用它求值的经典办法还是栈：遇到数字就压栈，遇到运算符就弹出栈顶的两个操作数（先弹出来的是右操作数），算出结果再压回去，扫描完栈顶就是最终答案。
#include <iostream> // 引入 cout
#include <string> // 引入 string
#include <vector> // 引入 vector
#include <stack> // 引入 stack
#include <cstdlib> // 引入 atoi（把字符串转成整数）
using namespace std; // 简化 std
int evalRPN(const vector<string>& tokens)
{
stack<int> st; // 用栈暂存中间的操作数
for (const string& s : tokens) // 依次处理每一个元素
{
if (s == "+" || s == "-" || s == "*" || s == "/") // 遇到运算符
{
int right = st.top(); st.pop(); // 先弹出的是右操作数
int left = st.top(); st.pop(); // 再弹出的是左操作数
switch (s[0]) // 按运算符分派
{
case '+': st.push(left + right); break; // 加
case '-': st.push(left - right); break; // 减
case '*': st.push(left * right); break; // 乘
case '/': st.push(left / right); break; // 除（前提是除数不为0）
}
}
else // 否则它是个数字字符串
{
st.push(atoi(s.c_str())); // 转成整数后压栈
}
}
return st.top(); // 栈顶就是表达式的结果
}
int main()
{
vector<string> expr = {"2", "1", "+", "3", "*"}; // 即 (2+1)*3
cout << evalRPN(expr) << endl; // 输出 9
return 0;
}这里有个和前面 top()/pop() 呼应的细节：我们先 right = st.top(); st.pop();，再取 left。因为先弹出的是后压入的，所以 right 必须先行弹出，否则一个利用栈式 pop 顺序的小坑（弹出顺序和压入顺序相反）就会算错方向，比如 left - right 写反成 right - left 结果就错了。这个「先弹的是右操作数、后弹的是左操作数」的顺序，是逆波兰求值里最容易踩的坑，务必和「pop 顺序与 push 相反」这条栈天性绑定起来记。
（小提示：atoi 来自 C 语言 <cstdlib>，处理负数也正确——比如 "-5" 会被转成整型 -5。如果追求 C++ 更地道的写法，可以用 <string> 里的 stoi，但要注意 stoi 遇到非数字会抛异常，做题时用 atoi 更省心。）
应用四：用两个栈实现队列
这是课件里安排的课后 OJ，但它是「容器适配器 + 栈天性」最漂亮的实战，值得单独拎出来讲。要求：只用 stack 内部的 push/pop/top（不碰 deque、vector、list 底层），拼出一个有 push、pop、front、empty 的队列。妙处在于「负负得正」：把元素在两个栈之间倒腾一次，顺序就翻转过来了——入队先进「入栈」，出队时把「入栈」整体倒进「出栈」，队头就变成了「出栈」的栈顶。
#include <iostream> // 引入 cout
#include <stack> // 引入 stack
using namespace std; // 简化 std
// 用两个栈实现一个先进先出的队列
class MyQueue {
public:
void push(int x) { in_.push(x); } // 入队：先都收进"入栈"
int pop() { // 出队：返回队头并把它删除
moveInToOut(); // 出栈空时，把入栈整体倒过去
int ret = out_.top(); // out_ 的栈顶就是队头
out_.pop(); // 删除队头（注意：自己这里 top+pop 两步）
return ret;
}
int front() { // 看队头（不删除）
moveInToOut();
return out_.top();
}
bool empty() const { return in_.empty() && out_.empty(); }
private:
// 把 in_ 的全部元素按栈顶顺序倒入 out_，这一倒顺序就反转了
void moveInToOut() {
if (out_.empty()) { // 只在出栈空时才搬运，保证均摊 O(1)
while (!in_.empty()) {
out_.push(in_.top()); // 取 in_ 的栈顶压进 out_
in_.pop(); // 再从 in_ 删掉（top+pop 两步）
}
}
}
stack<int> in_; // 「收件箱」栈：新元素统一进这里
stack<int> out_; // 「发件箱」栈：从这里吐出的就是队头
};
int main()
{
MyQueue q;
q.push(1); // 入队 1
q.push(2); // 入队 2
cout << q.front() << endl; // 队头是 1
q.pop(); // 出队 1
q.push(3); // 入队 3
cout << q.front() << endl; // 队头是 2
q.pop(); // 出队 2
cout << q.front() << endl; // 队头是 3
return 0;
}运行输出是 1\n2\n3，入队顺序和出队顺序完全一致，先进先出成立。这段代码还顺带复习了今天的课题——你看 pop() 里头，我们自己写 MyQueue 的 pop 也是老老实实 top() 先读、pop() 再删，因为这是 std::stack 唯一留给我们的路。均摊复杂度的关键在 moveInToOut() 里的 if (out_.empty())：每个元素最多被搬运一次（从 in_ 倒进 out_）、被弹出一次，所以虽然某一次 pop 可能是 O(n)，但摊到每个元素上仍是 O(1)。
应用五：用队列实现栈
再对称地来一道「反着来」的 OJ：只用 std::queue 拼出一个栈。思路也对称：按先进先出的队列，「栈顶」就是「队列里最后一个元素」。所以要让 pop/top 拿到栈顶，得把队里除最后一个元素以外全部倒进辅助队列，让最后一个"浮"到队头；取完再换回来，让主队列恢复原状。
#include <iostream> // 引入 cout
#include <queue> // 引入 queue
using namespace std; // 简化 std
// 用两个队列实现一个后进先出的栈
class MyStack2 {
public:
void push(int x) { q1_.push(x); } // 入栈：一律进主队列队尾
int pop() { // 出栈：返回栈顶并删除
moveTopToFront(); // 把主队列唯一的尾元素挪到队头
int ret = q1_.front(); // 那么队头就是"栈顶"
q1_.pop(); // 删掉它
swap(q1_, q2_); // 换回来，让主队列重新接管
return ret;
}
int top() { // 看栈顶（不删除）
moveTopToFront(); // 同样把尾元素挪到队头
int ret = q1_.front();
q2_.push(q1_.front()); // 注意这里不删，而是也转发到 q2_
q1_.pop();
swap(q1_, q2_); // 再换回来
return ret;
}
bool empty() const { return q1_.empty(); }
private:
// 把主队列 q1_ 中除最后一个外的所有元素转发到 q2_，使尾元素到队头
void moveTopToFront() {
while (q1_.size() > 1) {
q2_.push(q1_.front()); // 队头转到辅助队列
q1_.pop();
}
}
queue<int> q1_; // 主队列，实际存放栈内元素
queue<int> q2_; // 辅助队列，用来把尾元素"顶"到队头
};
int main()
{
MyStack2 st;
st.push(10); // 入栈 10
st.push(20); // 入栈 20
cout << st.top() << endl; // 栈顶是 20
st.pop(); // 弹出 20
cout << st.top() << endl; // 栈顶回到 10
return 0;
}运行输出是 20\n10，后进先出成立。注意 top() 和 pop() 的唯一差别：pop 把队头删掉，top 把它留着转发到 q2_。这两道「互相模拟」的题放在一起，能让你彻底看清 stack 和 queue 的「血统」——它们其实是一对「顺序相反的双胞胎」，靠底层容器换来换去就能互相伪装。这也是容器适配器概念最好的练兵场。
应用六：二叉树的层序遍历（BFS）
队列的经典应用是广度优先搜索（BFS，Breadth-First Search），最典型的例子是二叉树的层序遍历：按层从上到下、每层从左到右依次访问节点。做法是用队列：先把根节点入队，然后循环——出队一个节点并访问它，再把它的左右孩子依次入队。队列的先进入先出特性，保证了同一层节点先进先出、层与层之间自然衔接。
这里先用一个「队列能装节点指针」的最小示例感受队列的用途（假设已有一个二叉树的裸指针结构，只演示队列操作）：
#include <iostream> // 引入 cout
#include <queue> // 引入 queue
using namespace std; // 简化 std
struct TreeNode { // 二叉树的一个节点（简化版）
int val; // 节点存的值
TreeNode* left; // 左孩子指针
TreeNode* right; // 右孩子指针
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} // 构造：值为x，左右为空
};
// 层序遍历：按层输出每个节点的值，用空格分隔
void levelOrder(TreeNode* root)
{
if (root == nullptr) // 空树无需遍历
return; // 直接返回
queue<TreeNode*> q; // 队列里存的是节点的指针
q.push(root); // 根节点先入队
while (!q.empty()) // 队列非空就一直取
{
TreeNode* node = q.front(); // 取出队头节点
q.pop(); // 队头出队，队伍前移
cout << node->val << " "; // 访问（打印）当前节点
if (node->left) // 若有左孩子
q.push(node->left); // 左孩子入队，排在下次轮到它
if (node->right) // 若有右孩子
q.push(node->right); // 右孩子入队
}
cout << endl; // 遍历完换行
}你之前的 TreeNode 默认构造可能接受参数（像这里的 TreeNode(int x)），那么工厂建树时用 new 造节点即可。这里重点不是建树细节，而是看清这个「取出＋入队孩子」的自然节奏——它就是 BFS 的骨架。骨架为什么是队列而不是栈？因为 BFS 要求「先进入（先访问到）的层先被处理完」，兄弟节点也要按发现顺序依次处理，先进先出正好对上。如果你改用栈（DFS，深度优先搜索），就会一头扎到最深的叶子再折返，那叫先序遍历、求树的高度，语义完全不同。
如果想更进一步——区分出「每一层」分别处理（比如按层求和、输出每层平均值），只需在每轮循环开头记下 q.size()，这一轮的节点数就是当前层的节点数，循环处理完它们再进下一层：
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
// 按层统计：把每一层的节点值分别放到一个 vector 里
vector<vector<int>> levelValues(TreeNode* root)
{
vector<vector<int>> result;
if (root == nullptr) return result;
queue<TreeNode*> q;
q.push(root);
while (!q.empty())
{
int levelSize = (int)q.size(); // 关键：此刻队列里的节点数 = 当前层节点数
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);
}
result.push_back(level); // 收集完当前层，再进入下一轮
}
return result;
}这段代码用 levelSize 把「当前层」和「下一层」从宽度上切开，是层序遍历最常见的进阶写法，建议背下来。
应用七：单调栈与单调队列（拓展开个眼界）
stack 和 queue 各有自己的进阶变体，考过算法题的同学一定不陌生。
单调栈（monotonic stack）是这样的栈：压入元素时，维护栈内元素严格递增或递减。它能在 O(n) 时间内解决「找某元素右边第一个比它大/小的元素」这类问题——典型如求解「每日温度」、柱状图中最大矩形。核心妙处：当新元素比栈顶大（小）时，就开始弹栈，被弹出元素的下一个更大/更小元素往往就是当前这个新元素。它利用的正是栈的「最近待结算」特性。
单调队列（monotonic queue）类似，维护队内元素单调，能在滑动窗口问题里 O(n) 求窗口最大/最小值（典型「滑动窗口最大值」）。因为窗口里的最值只和范围有关，把「过期出窗口」的元素从队头踢掉，把「更优的新元素」从队尾挤掉，队头就是答案。它把队列的两端能力（队头出、队尾进）都用到了极致。
这两个是面试里 stack/queue 应用的天花板。这一节只为开眼界，具体实现细节以后再单独开篇——现在你只要知道：它们不是新结构，都是在你今天学的 stack/queue 上加了「单调」的约束。
deque 双端队列简介
是时候把那个神秘的 deque 介绍清楚了。
deque（double-ended queue，双端队列），是一种「双开口的连续空间」结构——它允许在头部和尾部都进行插入和删除操作，且时间复杂度均为 O(1)。它站在 vector 和 list 的折中位置上：和 vector 比，deque 头插效率高，不需要搬移元素；和 list 比，deque 空间利用率高，不用每个节点存额外指针。
但关键的一点是：deque 并不是真正连续的空间，它是由一段段连续的小空间拼接而成的，底层很像一个「动态的二维数组」——一维是一张「缓冲区地址表」（不同实现叫法不同，GCC 的 libstdc++ 里叫 map、MSVC 里是类似的指针数组），每个表项指向一段连续的小内存（缓冲块）。要往头部插入新元素时，如果头部缓冲块满了，就在缓冲表里再申请一个新块接在前面；尾部同理。这就是它头尾插入都是 O(1)、扩容又不用大搬移的秘密——它只需要在缓冲表里新增一个指针，而不是像 vector 那样把全部元素搬到一块新内存。
这里把「缓冲区」的大小也澄清一下，以免你以为有个固定值：标准并没有规定缓冲块多大，这是各实现自行决定的。 例如 GCC 的 libstdc++ 常按「每块 512 字节」来切，于是 deque<int> 每块能装 512 / 4 = 128 个 int；MSVC 的默认缓冲大小则是按元素个数固定（通常是 16 个）来取。总之，具体尺寸以你用的标准库实现为准，写代码时不要假设它等于某个数。你只需要掌握它的宏观形态——「一段段连续，靠缓冲表串起来」。
为了维持「看起来整体连续、还能随机访问」的假象，deque 的迭代器设计得非常复杂：迭代器里除了当前元素的指针，还得记录所在缓冲块的头尾、缓冲表的位置。每次自增自减，都要判断是否越过了当前缓冲块的边界，决定要不要跳到下一个块。这个「频繁检查边界」的动作，正是 deque 的软肋所在。
deque 的缺陷：不适合遍历
你也许会问，deque 这么好，为什么平时用得少？因为它有个致命的缺陷——不适合遍历。遍历时，迭代器每前进一步都要检测是否到达了某段小空间的边界，这个判断累积起来，让遍历效率明显低于 vector。而在真实的「序列式」场景里，遍历几乎是主流操作（打印全部、查找某个、汇总统计……），于是实际工程里，需要线性结构的场合，大多数人还是优先选 vector 或 list。
而且 deque 还有第二重软肋：它的随机访问（下标）虽然也是 O(1)，但常数比 vector 大——d[i] 得先做一次「定位到哪个缓冲块」的换算，才能拿到真正的地址，不像 vector 一个偏移就完事。所以「又要随机访问又要高效」的活，永远找 vector，不找 deque。
那 deque 是不是就废了？不是。它目前最「出名」的一个应用恰恰就是——STL 拿它当 stack 和 queue 的底层容器。因为 stack 和 queue 压根不遍历（前面说过它们连迭代器都没有），只做固定端的插入删除，deque「头尾高效」的好处被最大化，「不适合遍历」的缺陷被完美规避。这就是「把对的东西放在对的场景」的绝佳示范。栈要的「尾部插删 + 引用稳定」、队列要的「头尾插删」，deque 在两端的 O(1) 都接得住，且不重定位已有元素，正中命门。
最后给你一句话串起整节：deque 用「分段连续 + 复杂迭代器」换来了头尾双端 O(1) 插入删除和接近 vector 的空间利用率，代价是不擅遍历；而 stack 和 queue 恰好不需要遍历，所以 deque 成了它们最合适的默认拍档。
这一篇我们走完了 stack 和 queue 的完整旅程：从生活里的后进先出、先进先出，到它们作为容器适配器（包一层既有容器、只暴露受限接口）的本质；把栈的 top/push/pop 和队列的 front/back/push/pop 过了一遍，也解释了那个高频陷阱——为什么 pop 不返回被删的元素（top/front/back 已返回引用，pop 只管删，且返回会带来拷贝代价、移动限制与异常安全的麻烦）；弄清了为什么默认底层是 deque，也学了用 vector/list 显式指定底层容器；再到一组实战应用（括号匹配、栈的弹出压入序列、逆波兰表达式、两个栈模拟队列、两个队列模拟栈、层序遍历 BFS）和 deque 双端队列的原理与缺陷。
现在试着回答自己四个问题：
- 为什么说栈是适配器而不是独立容器？
- 为什么
stack<int, list<int>>合法而queue<int, vector<int>>会编译失败？ - 为什么层序遍历要用队列而不用栈？
- 为什么
top()/front()返回引用意味着能改写元素，而pop()却永远只能「删」不能「拿」？
如果这几个你都答得上来，今天这篇就算真正吃透了。下一节，我们还会碰到 stack/queue 的第三位兄弟——优先队列 priority_queue，它同样是容器适配器，但底层藏着一棵隐形的「堆」，到时候再细聊。
priority_queue：第三位容器适配器
上面反复预告的"第三位兄弟"现在就落地了。std::priority_queue（优先队列）同样是容器适配器：它默认以 vector 为底层容器，再在这块 vector 之上用堆算法把元素组织成堆，从而提供一个"永远能 O(1) 取出当前最大（或最小）元素，插入与删除堆顶都是 O(log n)"的接口。换句话说，priority_queue 就是"披着容器外衣的堆"——以后凡是要用堆的地方，先想到它。
它有三个模板参数：priority_queue<T, Container = vector<T>, Compare = less<T>>。
- 第三个参数
Compare是"比较方式"，默认less<T>表示大堆（堆顶最大）； - 想要小堆，就把第三个参数换成
greater<T>（<functional>里）。
#include <iostream>
#include <vector>
#include <queue>
#include <functional> // std::greater
using namespace std;
int main()
{
vector<int> v{ 3, 2, 7, 6, 0, 4, 1, 9, 8, 5 };
// 默认大堆：堆顶是最大值
priority_queue<int> big(v.begin(), v.end());
cout << big.top() << endl; // 9
// 小堆：堆顶是最小值
priority_queue<int, vector<int>, greater<int>> small(v.begin(), v.end());
cout << small.top() << endl; // 0
// 常用接口跟 stack 几乎一样：push / pop（删堆顶）/ top（读堆顶）/ empty / size
big.push(100); // 插入，O(log n)
big.pop(); // 删除堆顶，O(log n)
cout << big.top() << endl; // 现在最大的是 9（100 已被 pop）
return 0;
}往 priority_queue 里放自定义类型（比如 Date）时，默认大堆需要这个类型提供 operator<；要建小堆（配合 greater<Date>）则提供 operator>。这和 std::sort 要求元素可比较是同一个道理。
它的经典 OJ 应用：数组中第 K 大的元素
"找第 K 大的元素"最朴素的想法是排序后取下标，但用 priority_queue 可以做到只建一次堆、再连续弹出堆顶 k-1 次，剩下的堆顶就是第 k 大：
#include <vector>
#include <queue>
using namespace std;
int findKthLargest(vector<int>& nums, int k)
{
priority_queue<int> p(nums.begin(), nums.end()); // 用 [begin,end) 区间构造：一次建堆 O(N)
for (int i = 0; i < k - 1; ++i)
p.pop(); // 连续丢掉最大的 k-1 个
return p.top(); // 剩下的最大的那个，就是第 k 大
}底层原理一句话
priority_queue 内部其实就是对标准库堆算法 make_heap / push_heap / pop_heap 的封装：push 时把新元素放到堆尾并向上调整（上滤）；pop 时把堆顶与最后一个元素交换、删除末尾元素并向下调整（下滤）。因为堆永远是"完全二叉树"，它天然适合用 vector 这种连续结构来存——下标 i 的左右孩子就是 2i+1、2i+2。理解了这几个调整动作，priority_queue 就没有任何秘密了。
参考答案与详解（上面的四个问题）
1. 为什么说栈（以及队列、优先队列）是"适配器"而不是独立的容器？
因为 stack 自己并不持有数据，也不负责内存管理——它只是"包"在某个既有顺序容器（默认 deque）外面，把底层容器的丰富接口裁剪成 push/pop/top/size/empty 这一组受限接口，从而保证"栈只能先进后出"。适配器模式的核心就是这个"把 A 类的接口改造成用户想要的 B 类接口"：它不新增存储能力，只做了一层语义包装。
2. 为什么 stack<int, list<int>> 合法，而 queue<int, vector<int>> 会编译失败？
这取决于底层容器必须支持哪些操作：
stack只需要push_back（入栈）和pop_back（出栈），vector、list、deque全都支持，所以用list甚至vector作底层都没问题；queue的pop()需要pop_front（队头删除）来配合push_back（队尾插入）。deque、list有pop_front，而vector没有pop_front（它只能在尾部删）。于是当queue真的去调用_c.pop_front()时，编译器发现vector没有这个成员函数，就报编译错误了。
一句话：适配器要求底层容器"喂"给它所必需的接口，vector 缺 pop_front，喂不了队列。
3. 为什么层序遍历（BFS）要用队列而不用栈？
层序遍历要求"先把同一层的都处理完，再处理下一层"，也就是先被压入的先被访问。这正好对应队列的先进先出（FIFO）：把根压入，出队一个节点并把它的左右孩子从尾巴压入，队列自然保证"同一层从左到右、一层一层往外扩展"。而栈是后进先出（LIFO），它会一路往一个方向钻到底再回来，形成的是"纵深"的深度优先（DFS），而不是一层一层的广度优先（BFS）。所以"要一层层平推"用队列，"要一条路钻到底"用栈。
4. 为什么 top()/front() 返回引用能改写元素，而 pop() 永远只能"删"不能"拿"？
top()/front()返回的是"对栈顶/队头元素的引用"（T&），所以你既可以在上面读，也可以直接改（比如s.top() = 5;），因为对象仍活着、拿引用即拿到它本人。pop()的返回类型被设计成void，它只负责删除栈顶/队头，不返回被删的值。若要让pop既删除又返回，就得先拷贝一份再删除——这会带来不必要的拷贝开销，也牵涉移动语义与异常安全的麻烦（拷贝可能抛异常，删都删了却没法保证返回值安全交给调用者）。所以标准库的约定是"读与删分开"：要读就先top()/front()拿引用（或先备份一份值），要删再pop()。这样既安全又高效。
还没有评论 — 第一条由你来留。