文章目录
在 C++ 中， 适配器容器（Adapter Containers） 是一种特殊的容器，它们不直接提供存储功能，而是通过封装其他基础容器（如
vector、 deque、 list）来提供特定的接口和行为。C++ 标准库提供了三种适配器容器： 栈（stack）、 队列（queue） 和 优先队列（priority_queue）。
适配器容器的共性
- 封装基础容器：适配器通过组合一个基础容器来实现功能，默认使用
deque，但可指定其他容器（如vector、list）。 - 限制访问接口：适配器隐藏了基础容器的大部分接口，仅暴露特定的操作（如栈的
push/pop），确保数据遵循特定的访问规则。 - 模板参数：适配器的模板参数格式为：
template < class T, // 元素类型 class Container = deque<T> // 基础容器类型（默认 deque） > class Adapter;
栈（stack）
特点
- 后进先出（LIFO）：最后入栈的元素最先出栈。
- 默认底层容器：
deque（支持高效的尾部插入/删除）。
常用操作
| 操作 | 功能 | 时间复杂度 |
|---|---|---|
push(x) |
将元素 x 压入栈顶 |
O(1) |
pop() |
移除栈顶元素（不返回值） | O(1) |
top() |
返回栈顶元素的引用 | O(1) |
empty() |
判断栈是否为空 | O(1) |
size() |
返回栈中元素的数量 | O(1) |
示例代码
#include <stack>
#include <iostream>
int main() {
std::stack<int> s; // 默认使用 deque
s.push(10);
s.push(20);
std::cout << s.top() << std::endl; // 输出: 20
s.pop();
std::cout << s.top() << std::endl; // 输出: 10
return 0;
}
自定义底层容器
// 使用 vector 作为底层容器
std::stack<int, std::vector<int>> s;
// 使用 list 作为底层容器
std::stack<int, std::list<int>> s;
队列（queue）
特点
- 先进先出（FIFO）：最先入队的元素最先出队。
- 默认底层容器：
deque（支持高效的头部和尾部操作）。
常用操作
| 操作 | 功能 | 时间复杂度 |
|---|---|---|
push(x) |
将元素 x 加入队尾 |
O(1) |
pop() |
移除队首元素（不返回值） | O(1) |
front() |
返回队首元素的引用 | O(1) |
back() |
返回队尾元素的引用 | O(1) |
empty() |
判断队列是否为空 | O(1) |
size() |
返回队列中元素的数量 | O(1) |
示例代码
#include <queue>
#include <iostream>
int main() {
std::queue<int> q;
q.push(10);
q.push(20);
std::cout << q.front() << std::endl; // 输出: 10
q.pop();
std::cout << q.front() << std::endl; // 输出: 20
return 0;
}
优先队列（priority_queue）
特点
- 元素按优先级出队：默认最大元素优先出队（大顶堆），也可配置为小顶堆。
- 底层实现：基于堆（Heap），默认使用
vector存储数据。
常用操作
| 操作 | 功能 | 时间复杂度 |
|---|---|---|
push(x) |
插入元素 x 并调整堆 |
O(log n) |
pop() |
移除堆顶元素（最大/最小值） | O(log n) |
top() |
返回堆顶元素的引用 | O(1) |
empty() |
判断队列是否为空 | O(1) |
size() |
返回队列中元素的数量 | O(1) |
示例代码
#include <queue>
#include <iostream>
int main() {
// 大顶堆（默认）
std::priority_queue<int> max_heap;
max_heap.push(30);
max_heap.push(10);
max_heap.push(20);
std::cout << max_heap.top() << std::endl; // 输出: 30
// 小顶堆
std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;
min_heap.push(30);
min_heap.push(10);
min_heap.push(20);
std::cout << min_heap.top() << std::endl; // 输出: 10
return 0;
}
自定义比较函数
// 自定义结构体的优先队列
struct Node {
int val;
Node(int v) : val(v) {}
};
// 按 val 从大到小排序（小顶堆）
struct Compare {
bool operator()(const Node& a, const Node& b) const {
return a.val > b.val;
}
};
std::priority_queue<Node, std::vector<Node>, Compare> pq;
适配器容器的应用场景
| 适配器 | 典型应用场景 |
|---|---|
stack |
- 递归模拟（如 DFS） - 表达式求值（中缀转后缀） - 括号匹配问题 |
queue |
- BFS（广度优先搜索） - 任务调度（如生产者-消费者模型） |
priority_queue |
- 贪心算法（如霍夫曼编码） - Dijkstra 算法 - 数据流中位数问题 |
选择底层容器的建议
stack：- 默认
deque：平衡的内存使用和性能。 - 使用
vector：若需连续内存（如频繁随机访问栈中元素）。 - 使用
list：若需频繁插入/删除中间元素。
- 默认
queue：- 默认
deque：支持高效的双端操作。 - 使用
list：若需频繁插入/删除中间元素。
- 默认
priority_queue：- 默认
vector：堆操作需要随机访问，vector性能最优。
- 默认
注意事项
- 空容器操作风险：调用
top()、front()、back()或pop()前必须确保容器非空，否则会导致未定义行为。 - 性能差异：不同底层容器的选择可能影响性能（如
vector扩容导致的拷贝开销）。 - 优先队列的比较函数：比较函数决定了元素的优先级顺序（
a < b为大顶堆，a > b为小顶堆）。