个人主页: 起名字真南的CSDN博客
个人专栏:
【数据结构初阶】 ? 基础数据结构【C语言】 ? C语言编程技巧【C++】 ? 进阶C++【OJ题解】 ? 题解精讲
目录
前言? 1. 优先级队列、容器适配器和 `deque` 概述✨1.1 什么是优先级队列？✨ 1.2 容器适配器与 `deque` ? 2. `deque` 的特点与基本操作✨2.1 特点✨2.2 基本操作 ? 3. 容器适配器的类型与实现原理? 4. `priority_queue` 的基本使用? 5. 实际应用场景：任务调度与路径搜索✨5.1 优先级队列在任务调度中的应用✨ 5.2 `deque` 在滑动窗口问题中的应用 ? 6. 总结与常见问题解答✨ 6.1 常见问题 总结
前言
在 C++ 标准库中，优先级队列（priority_queue）是一种容器适配器，特别适合处理需要频繁访问最大值或最小值的数据集。同时，双端队列 deque 也是一种灵活的标准容器，支持高效的头尾插入、删除操作，被广泛用于实现队列、栈等数据结构。本文将深入讲解优先级队列、deque 及其在容器适配器中的应用。
? 1. 优先级队列、容器适配器和 deque 概述
✨1.1 什么是优先级队列？
优先级队列是一种基于优先级的特殊队列。默认情况下，C++ 的 priority_queue 是最大堆，出队时总是返回最大元素。实现优先级队列的底层容器通常是 vector 或 deque，其中 deque 是标准库提供的双端队列容器，支持高效的头尾插入和删除。
✨ 1.2 容器适配器与 deque
C++ 容器适配器包括 stack、queue 和 priority_queue，它们对底层容器进行封装，提供栈、队列等结构的特定接口。deque 是 queue 和 stack 默认使用的底层容器，提供两端的灵活操作。
? 2. deque 的特点与基本操作
deque（双端队列）是 C++ 中的一种序列容器，支持在两端快速插入和删除。deque 的实现类似一个分段的动态数组，因此具备更灵活的内存管理方式，可以在前后两端动态扩展。
✨2.1 特点
双端插入与删除：支持在头尾两端快速插入和删除，效率接近O(1)。动态扩展：不像 vector 只能从尾部扩展，deque 可以在头部或尾部自由扩展。支持随机访问：与 vector 类似，可以通过索引访问任意位置的元素，但相比 vector 速度稍慢。 ✨2.2 基本操作
#include <iostream>#include <deque>void deque_example() { std::deque<int> dq; // 在尾部插入 dq.push_back(10); dq.push_back(20); // 在头部插入 dq.push_front(5); // 访问元素 std::cout << "Front: " << dq.front() << std::endl; // 5 std::cout << "Back: " << dq.back() << std::endl; // 20 // 删除头尾元素 dq.pop_front(); dq.pop_back(); // 遍历 std::cout << "Elements: "; for (int elem : dq) { std::cout << elem << " "; } std::cout << std::endl;}int main() { deque_example(); return 0;}输出：
Front: 5Back: 20Elements: 10 代码解析：
push_back 和 push_front：分别在尾部和头部插入元素。pop_back 和 pop_front：分别从尾部和头部删除元素。front 和 back：访问头部和尾部的元素。 ? 3. 容器适配器的类型与实现原理
C++ 容器适配器使用底层容器来构建特定的数据结构，例如栈、队列和优先级队列。以下是容器适配器的类型及默认底层容器：
stack：默认使用 deque 实现的后进先出（LIFO）数据结构，也支持 vector。queue：使用 deque 实现的先进先出（FIFO）数据结构，提供 push、pop、front 和 back 操作。priority_queue：通常使用 vector 或 deque 实现，提供最高优先级元素的访问和出队操作。 使用 deque 作为底层容器时，可以灵活利用其双端插入和删除的特性。
? 4. priority_queue 的基本使用
priority_queue 默认是最大堆，每次 pop 操作返回当前的最大值。其底层容器通常使用 vector，但 deque 也可以用作其底层容器。
如果我们想让他最小堆可以在传入参数的时候传入 greater
#include <iostream>#include <queue>#include <vector>#include <functional> // std::greaterint main(){std::priority_queue<int> pq_max;pq_max.push(10);pq_max.push(20);pq_max.push(30);pq_max.push(40);while (!pq_max.empty()){cout << pq_max.top() << " ";pq_max.pop();}cout << endl;std::priority_queue<int,vector<int>,greater<int>> pq_min;pq_min.push(10);pq_min.push(20);pq_min.push(30);pq_min.push(40);while (!pq_min.empty()){cout << pq_min.top() << " ";pq_min.pop();}cout << endl;return 0;}输出：
40 30 20 1010 20 30 40? 5. 实际应用场景：任务调度与路径搜索
✨5.1 优先级队列在任务调度中的应用
在任务调度中，priority_queue 可以用来根据任务优先级调度任务。例如，操作系统内核中的进程管理通常需要根据优先级选择任务执行。可以使用 priority_queue 来存储任务，每次从队列中取出最高优先级的任务执行。
✨ 5.2 deque 在滑动窗口问题中的应用
deque 因其双端特性，被广泛用于解决滑动窗口问题。例如，在一个数组中找到滑动窗口的最大值，可以通过 deque 快速实现。每当窗口向前滑动时，使用 deque 的 push_back 和 pop_front 可以高效地更新窗口中的最大值。
? 6. 总结与常见问题解答
通过本文的介绍，我们全面了解了 priority_queue 和 deque 的实现与应用场景。以下是一些常见问题解答：
✨ 6.1 常见问题
deque 与 vector 的区别是什么？
deque 支持在两端高效插入和删除，而 vector 仅支持尾部的快速插入与删除。 为什么 priority_queue 默认使用 vector？
priority_queue 主要关注堆操作的效率，而 vector 是一个连续内存容器，适合在堆排序中实现高效的随机访问。 deque 可以用在 priority_queue 中吗？
priority_queue 支持以 deque 为底层容器，但因为 priority_queue 中通常不需要双端操作，因此更常使用 vector。 总结
本文介绍了 C++ 中的 priority_queue 和 deque 容器，分别适合实现优先级调度和双端队列操作。priority_queue 和 deque 在实际应用中扮演着重要角色，为各种算法和数据处理提供了高效、简洁的解决方案。希望本篇内容能帮助您更好地理解 C++ 容器的灵活性，并在项目中合理使用这些数据结构。
参考链接：C/C++ Reference