【C++】深入理解 C++ 优先级队列、容器适配器与 deque：实现与应用解析

时间：2024-11-17 19:58:42

个人主页: 起名字真南的****博客

个人专栏:

  • 【数据结构初阶】 ???? 基础数据结构
  • 【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: 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::greater

int 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 10
10 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 常见问题

  1. deque 与 vector 的区别是什么？

    • deque 支持在两端高效插入和删除，而 vector 仅支持尾部的快速插入与删除。

  2. 为什么 priority_queue 默认使用 vector？

    • priority_queue 主要关注堆操作的效率，而 vector 是一个连续内存容器，适合在堆排序中实现高效的随机访问。

  3. deque 可以用在 priority_queue 中吗？

    • 可以，priority_queue 支持以 deque 为底层容器，但因为 priority_queue 中通常不需要双端操作，因此更常使用 vector。

总结

本文介绍了 C++ 中的 priority_queue 和 deque 容器，分别适合实现优先级调度和双端队列操作。priority_queue 和 deque 在实际应用中扮演着重要角色，为各种算法和数据处理提供了高效、简洁的解决方案。希望本篇内容能帮助您更好地理解 C++ 容器的灵活性，并在项目中合理使用这些数据结构。
参考链接：C/C++ Reference

相关文章