C++ 常用的数据结构（适配器容量：栈、队列、优先队列）

文章目录

• • • 适配器容器的共性
    • 栈（`stack`）
    • • 特点
      • 常用操作
      • 示例代码
      • 自定义底层容器
    • 队列（`queue`）
    • • 特点
      • 常用操作
      • 示例代码
    • 优先队列（`priority_queue`）
    • • 特点
      • 常用操作
      • 示例代码
      • 自定义比较函数
    • 适配器容器的应用场景
    • 选择底层容器的建议
    • 注意事项

在 C++ 中，适配器容器（Adapter Containers） 是一种特殊的容器，它们不直接提供存储功能，而是通过封装其他基础容器（如 vector、deque、list）来提供特定的接口和行为。C++ 标准库提供了三种适配器容器：栈（stack）、队列（queue） 和 优先队列（priority_queue）。

适配器容器的共性

1. 封装基础容器：适配器通过组合一个基础容器来实现功能，默认使用 deque，但可指定其他容器（如 vector、list）。
2. 限制访问接口：适配器隐藏了基础容器的大部分接口，仅暴露特定的操作（如栈的 push/pop），确保数据遵循特定的访问规则。
3. 模板参数：适配器的模板参数格式为：

   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 #include 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 #include 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 #include 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 算法
- 数据流中位数问题

选择底层容器的建议

1. stack：

   • 默认 deque：平衡的内存使用和性能。
   • 使用 vector：若需连续内存（如频繁随机访问栈中元素）。
   • 使用 list：若需频繁插入/删除中间元素。

2. queue：

   • 默认 deque：支持高效的双端操作。
   • 使用 list：若需频繁插入/删除中间元素。

3. priority_queue：

   • 默认 vector：堆操作需要随机访问，vector 性能最优。

注意事项

1. 空容器操作风险：调用 top()、front()、back() 或 pop() 前必须确保容器非空，否则会导致未定义行为。
2. 性能差异：不同底层容器的选择可能影响性能（如 vector 扩容导致的拷贝开销）。
3. 优先队列的比较函数：比较函数决定了元素的优先级顺序（a < b 为大顶堆，a > b 为小顶堆）。