长沙公司制作网站费用多少,app与移动网站开发考试资料,台州高端网站设计,长沙招聘网58同城个人主页: 起名字真南的CSDN博客
个人专栏:
【数据结构初阶】 #x1f4d8; 基础数据结构【C语言】 #x1f4bb; C语言编程技巧【C】 #x1f680; 进阶C【OJ题解】 #x1f4dd; 题解精讲 目录 前言#x1f4cc; 1. 优先级队列、容器适配器和 deque 概述✨1.1 什么是优…
个人主页: 起名字真南的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 dequevoid deque_example() {std::dequeint dq;// 在尾部插入dq.push_back(10);dq.push_back(20);// 在头部插入dq.push_front(5);// 访问元素std::cout Front: dq.front() std::endl; // 5std::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: 5
Back: 20
Elements: 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_queueint 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_queueint,vectorint,greaterint 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 10
10 20 30 405. 实际应用场景任务调度与路径搜索
✨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
