C++容器适配器用途解析：stack queue priority_queue详解

C++容器适配器是封装底层容器的类模板，提供特定操作接口，主要包括stack、queue和priority_queue。1. stack实现后进先出（LIFO），适用于括号匹配、函数调用栈等场景，默认使用deque，提供push、pop、top等操作；2. queue实现先进先出（FIFO），用于任务调度、BFS等场合，默认使用deque，支持push、pop、front、back等操作；3. priority_queue维护优先级顺序，默认使用vector并维护堆结构，适合堆排序、最短路径算法等，插入删除复杂度为O(log n)，只能访问顶部元素。选择合适底层容器可优化性能，注意线程安全及避免修改适配器源码。

C++容器适配器（Container Adaptors）是一类封装了底层容器的类模板，它们本身不提供完整的容器功能，而是基于已有的容器（如 vector、deque、list 等）实现特定的操作接口。最常见的三个容器适配器是：stack（栈）、queue（队列）和 priority_queue（优先队列）。它们在实际开发中用途广泛，尤其适用于需要特定数据访问顺序的场景。

1. stack：后进先出（LIFO）

std::stack 是一个后进先出的数据结构，适合用于需要“最后压入的元素最先弹出”的情况。例如括号匹配、函数调用栈、表达式求值等场景。

• 默认底层容器是 std::deque，但也可以使用 std::vector 或 std::list
• 常用操作：
  • push()：压入元素
  • pop()：弹出顶部元素
  • top()：查看顶部元素
  • empty() 和 size()

#include <stack>
std::stack<int> s;
s.push(1);
s.push(2);
int top = s.top(); // 得到 2
s.pop();           // 弹出 2

注意：不能直接遍历 stack，只能通过 push/pop/top 操作访问元素。

2. queue：先进先出（FIFO）

std::queue 是一个先进先出的队列结构，常用于任务调度、广度优先搜索（BFS）等需要按顺序处理的场合。

• 默认使用 std::deque 实现
• 支持的操作包括：
  • push()：将元素加入队尾
  • pop()：移除队首元素
  • front() 和 back()：分别获取队首和队尾元素

#include <queue>
std::queue<int> q;
q.push(10);
q.push(20);
int first = q.front(); // 得到 10
q.pop();               // 移除 10

与 stack 类似，queue 也不支持随机访问，只能通过 front/back 来查看两端元素。

3. priority_queue：优先级队列

std::priority_queue 是一种特殊的队列，每次取出的是当前队列中优先级最高的元素（通常是最大值，默认情况下），非常适合用来实现堆排序、Dijkstra 最短路径算法、哈夫曼编码等。

• 默认使用 std::vector 存储元素，内部维护一个堆结构
• 插入和删除的时间复杂度为 O(log n)
• 只能访问顶部元素（即最大/最小值，取决于比较方式）

#include <queue>
std::priority_queue<int> pq;
pq.push(3);
pq.push(1);
pq.push(4);
int max = pq.top(); // 得到 4
pq.pop();           // 移除 4

如果想让 priority_queue 按照最小堆的方式工作，可以这样写：

std::priority_queue<int, std::vector<int>, std::greater<>> min_pq;

注意：priority_queue 不允许遍历，只能逐个 pop 出来。

使用建议与注意事项

• 选择合适的底层容器：虽然默认都使用 deque 或 vector，但在某些特殊场景下，比如频繁插入删除中间元素时，可能要考虑 list。
• 不要尝试修改适配器源码：这些适配器是为了简化使用而设计的，强行扩展功能可能会破坏其行为逻辑。
• 注意线程安全问题：标准库中的容器适配器都不是线程安全的，多线程环境下需自行加锁。

基本上就这些。掌握好 stack、queue 和 priority_queue 的基本用法，再结合具体的算法和应用场景，就能很好地发挥它们的作用了。