更新时间： 2026-08-27

前面几篇把 vector、string、list、deque、map 这些"存储型"容器过了一遍，它们负责把数据摆好、存好。这一篇换一批角色——stack、queue、priority_queue。它们自己几乎不存东西，而是站在别的容器肩膀上，只露出一个很窄的接口。

在 C++ 里，这类东西有个专门的名字：容器适配器（container adapter）。字面意思就是"把一个容器适配成另一个样子"。本文要回答的问题是：适配器到底适配了什么？三个适配器各管什么场景？以及——stack 明明自己也能用 vector 模拟，为什么要用适配器？

一、什么是容器适配器

先看一个最简单的例子。要用 stack：

#include <stack>
#include <iostream>

int main() {
    std::stack<int> s;
    s.push(1);
    s.push(2);
    s.push(3);
    while (!s.empty()) {
        std::cout << s.top() << " ";   // 3 2 1
        s.pop();
    }
}

push 放进去，top 看顶，pop 弹掉，empty 判断空。接口就这几个，没有下标访问、没有迭代器、没有 size 之外的任何"透视"能力——你永远只能碰到栈顶那一个元素。

@startmindmap
* 容器适配器
** stack
*** 后进先出 LIFO
*** 接口：push / top / pop / empty / size
*** 默认底层：deque
** queue
*** 先进先出 FIFO
*** 接口：push / front / back / pop / empty / size
*** 默认底层：deque
** priority_queue
*** 优先级高者先出
*** 接口：push / top / pop / empty / size
*** 默认底层：vector + 堆
@endmindmap

三者接口都极简，所以名字里带"适配器"而不是"容器"：它们内部各自持有一个底层容器，把底层容器能干的活裁剪成一套固定的窄接口。注意表格里的默认底层：

适配器	默认底层	可换底层	特性
std::stack	deque	vector / list	后进先出
std::queue	deque	list	先进先出
std::priority_queue	vector	deque	堆结构，最大元素在顶

为什么 stack 默认选 deque 而不是 vector？因为 deque 头部也能高效操作，而且它扩容时不像 vector 那样整块搬移；对 stack 这种"只从一端进出"的用法，deque 各方面都够用且无坑。queue 同理，需要头部弹出，deque 头尾操作都是 O(1)。priority_queue 需要随机访问（堆的 sift 操作要不停访问中间元素），所以底层必须是 vector 或 deque，不能是 list。

二、stack：后进先出

2.1 接口细节

#include <stack>

std::stack<int> s;
s.push(1);        // 入栈
int x = s.top();  // 读栈顶（不弹）
s.pop();          // 弹栈顶（不返回值）
s.empty();        // 是否为空
s.size();         // 元素个数

有个历史坑要提醒：pop() 不返回被弹出的元素。早期 C++ 设计里，让 pop 返回元素就得先拷贝、再删，拷贝可能抛异常，删了之后返回的值和栈状态就不一致了；所以标准库选择"读顶用 top()，弹顶用 pop()"，两步走。有些同学初学写成 int x = s.pop();，编译器直接报错，这就是设计使然，不是笔误。

top() 返回引用，所以也能写 s.top() = 42; 直接改栈顶。但注意：空栈上调用 top() 或 pop() 是未定义行为（UB），程序可能直接崩。写循环前先判 !s.empty()，这个习惯要养成。

2.2 底层是可换的

想指定底层容器，写第二个模板参数：

#include <stack>
#include <vector>

std::stack<int, std::vector<int>> sv;  // 用 vector 当底层

适配器本身不负责内存管理，它的全部工作就是把底层容器的接口"翻译"成 push/pop/top。所以 stack 不是一种新的数据结构，而是既有容器的一张窄面孔。这也是它被称为适配器的原因——不新增能力，只收敛接口。

@startuml
left to right direction
skinparam nodeFontSize 13
skinparam backgroundColor #FFFFFF

rectangle "std::stack<int>" as stack #E8F1FF {
  rectangle "对外接口" as api #DCE9FF {
    (push)
    (top)
    (pop)
    (empty)
    (size)
  }
  rectangle "底层容器 deque" as inner #FFF3D6 {
    node "deque<int>" as dq #FFF3D6
  }
}
api --> dq : "只调用底层的能力"
note bottom of inner
  适配器不新增存储，
  只是把底层容器包一层壳
end note
@enduml

图上壳里装的其实是完整的 deque，只是壳只开了几个洞。你碰不到中间元素，这既是限制，也是保护——栈语义被强制保证，谁也改不了。

2.3 C 对照：数组模拟栈

C 里没有栈类型，最常见的做法是数组 + 栈顶指针：

int stack[1024];
int top = -1;

void push(int x) { stack[++top] = x; }
int pop(void) { return stack[top--]; }

操作	C（数组模拟）	C++（std::stack）
入栈	stack[++top] = x;	s.push(x);
读顶	stack[top]	s.top()
出栈	top--;	s.pop();
判空	top == -1	s.empty()
容量	编译期固定 1024	自动增长，无需关心

C 版本省事但有两个代价：容量写死（爆栈上溢），且"栈顶"是裸指针，谁都能越界写。C++ 版本把这些都包进类里了。不过理解 C 的数组模拟依然有价值——它帮你看清 stack 的本质就是"一个指针 + 一块连续内存"，std::stack 只是把这个模式固化成了类型。

三、queue：先进先出

queue 接口长这样：

#include <queue>

std::queue<int> q;
q.push(1);        // 队尾入队
q.push(2);
int f = q.front(); // 队头（最先进入的）
int b = q.back();  // 队尾（最后进入的）
q.pop();          // 队头出队

queue 对应 C 里环形缓冲区（ring buffer）的活。环形缓冲的原理是：数组 + head/tail 两个下标，元素出队时 head 往前走，到尾了绕回开头，把数组当成一个环来用，避免每出队一个元素就把后面全部往前搬。这块内容在内存/存储相关的并发队列里经常出现——比如生产者消费者模型，用的就是队列语义。

@startuml
left to right direction
skinparam nodeFontSize 13
skinparam backgroundColor #FFFFFF

rectangle "std::queue<int>" as queue #E8F1FF {
  rectangle "对外接口" as qapi #DCE9FF {
    (push)
    (front)
    (back)
    (pop)
  }
  rectangle "底层容器 deque" as qinner #FFF3D6 {
    node "deque<int>" as qdq #FFF3D6
  }
}
qapi --> qdq
@enduml

queue 和 stack 长得像，差别只在语义：一个先进先出，一个后进先出。判断该用哪个，别背定义，看业务——新来的任务是不是要排在别人后面？ 是，用 queue；新来的任务要插到最前，用 stack。

queue 的典型场景

• 任务队列 / 消息队列：push 是投递，pop 是消费
• BFS 广度优先搜索：网格迷宫、图的最短路（无权）都靠队列
• 打印机任务、键盘输入缓冲这类"先到先服务"

C 里手写环形缓冲区，要点是下标取模 (tail + 1) % N 和"空/满"两个状态的区分（常用做法是牺牲一个槽位，或者维护 size 计数）。这套逻辑容易写错，std::queue 帮你把错误消灭在接口层。

四、priority_queue：优先级队列

priority_queue 是三个里最特别的——它内部维护一个二叉堆，top() 永远返回"当前最大"（默认按 < 比较）的元素：

#include <queue>
#include <iostream>

std::priority_queue<int> pq;
pq.push(3);
pq.push(1);
pq.push(4);
pq.push(1);
pq.push(5);

while (!pq.empty()) {
    std::cout << pq.top() << " ";  // 5 4 3 1 1
    pq.pop();
}

输出按从大到小。top() 是 O(1)，push/pop 都是 O(log n)——这是堆的特性，插入和删除都在树高（log n）内完成。对比一下：

操作	vector（找最大）	priority_queue
插入	O(1) 尾插	O(log n) 上浮
取最大	需遍历 O(n)	O(1)
弹最大	需先找到 O(n)	O(log n) 下沉

所以"随时要取当前最大/最小"的场景，priority_queue 是标准答案：堆排序、Dijkstra 最短路、Top-K 问题、事件驱动模拟（时间最早者优先），都是它的主场。

4.1 自定义比较器

默认是"大顶堆"。要小顶堆，或者按自己的规则排序，传第三个模板参数：

#include <queue>
#include <vector>

// 小顶堆：用 std::greater 反转比较方向
std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq;

// 自定义类型：按某个字段比较
struct Task {
    int priority;
    int id;
};

struct TaskCmp {
    bool operator()(const Task& a, const Task& b) const {
        return a.priority < b.priority;  // 优先级大的先出
    }
};

std::priority_queue<Task, std::vector<Task>, TaskCmp> tasks;

注意 TaskCmp 是个结构体而不是函数，这是和 sort 不同的地方——比较器是类型，在编译期就确定了。lambda 也行（C++20 才允许直接用 lambda 类型，之前要先 decltype 包一层），后续 lambda 那篇会展开。这里先记住套路：比较器是个结构体，重载 operator()，返回"a 应该排在 b 后面"为 true。

4.2 C 对照：手写堆 vs 直接用

C 里要实现同样的效果，得手写一个二叉堆：数组存堆、push 时 sift_up、pop 时把堆顶换到尾部再 sift_down。三四十行代码，且边界条件（父子下标 (i-1)/2、2*i+1/2*i+2）极易写错。

环节	C 手写堆	C++ std::priority_queue
建堆	手动 heapify	构造时传入容器即可
插入	sift_up 上浮	push()
取最大	arr[0]	top()
删除最大	交换 + sift_down	pop()
比较规则	手写比较函数	模板参数指定

堆这个数据结构本身值得理解（它是"部分有序"的典型代表），但在日常业务里，直接用 priority_queue 更划算——理解堆的原理和用它，不冲突。

五、适配器 vs 直接用底层容器

你可能想：stack 我直接用 deque 不也行吗？deque 也能 push_back/pop_back。确实行，但有个区别：接口收窄 = 语义保证。

直接用 deque 当栈，队友不小心写了 dq[2] 访问中间元素，编译器不会拦；用 std::stack，根本没有下标操作，想犯错都犯不了。这其实就是封装的价值：把"允许的操作"锁死在类型层面，错误的用法在编译期就被拒绝了。

这条思路和前面 17 篇（访问控制）、23 篇（友元）讲的是同一件事——通过类型和接口来约束行为，而不是靠"大家自觉"。

六、与本站主线衔接

这三个适配器在工程里出现频率极高：

• 递归与深度优先搜索天然对应 stack（系统调用栈就是这么工作的，见 21 篇 this 指针关于栈帧的讨论，以及 crash/ 里栈回溯的章节）
• BFS 层序遍历、生产者消费者队列对应 queue
• 调度器、事件驱动、Top-K 对应 priority_queue（Linux 的调度器、定时器堆都是堆结构，见 concepts/process/ 调度相关文档）

想深入看底层实现，重点理解 deque 的分块结构（35 篇讲过）和二叉堆的下沉/上浮（可对照 concepts/ 里堆排序相关章节）。

七、一句话总结

stack、queue、priority_queue 是容器适配器——不自己存数据，站在 deque/vector 肩膀上收窄接口，分别用后进先出、先进先出、优先级最大这三种出队规则，把"取哪个"的决策交给类型本身去保证。

---

上一篇：39-sort / find 等算法库 ｜ 下一篇：41-pair 与 tuple