当前位置：首页 > news >正文

【C++】——优先级队列和容器适配器

news 2024/11/14 9:27:46

文章目录

优先级队列
容器适配器

优先级队列

优先级队列是一种特殊的队列，他的元素出队列顺序并不按照先进先出原则，而是根据元素的优先级来。优先级高的先出，优先级低的后出。(类似于堆)
优先级队列常用成员函数：

empty()：检查队列是否为空。
size()：返回队列中的元素数量。
top()：返回队列顶部（优先级最高）的元素，但不从队列中删除它。
push()：将一个元素添加到队列中，并重新调整队列以保持排序。
pop()：删除队列顶部（优先级最高）的元素。
swap()：与另一个优先级队列交换内容

用例：

#define   _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main()
{priority_queue<int> pq;//priority_queue<int, std::vector<int>, std::less<int>> pq;pq.push(2);pq.push(1);pq.push(6);pq.push(4);pq.push(9);while (!pq.empty()){cout << pq.top() << " ";pq.pop();}cout << endl;priority_queue<int, std::vector<int>, std::greater<int>> pq1;pq1.push(2);pq1.push(1);pq1.push(6);pq1.push(4);pq1.push(9);while (!pq1.empty()){cout << pq1.top() << " ";pq1.pop();}cout << endl;return 0;
}

在这里插入图片描述

容器适配器

C++中三种常见的容器适配器有stack、queue、priority_queue

stack是一种后进先出的特殊线性数据结构，因此只要具有push_back()和pop_back()操作的线性结构，都可以作为stack的底层容器，比如vector和list都可以
queue是先进先出的特殊线性数据结构，只要具有 push_back和pop_front操作的线性结构，都可以作为queue的底层容器比如：list

在这里插入图片描述

deque容器是什么，stack和queue为什么在底层设计时用deque来实现？

在这里插入图片描述
deque是一个在两端都能进行快速插入和删除操作的数据结构。看起来像是vector和list的合体，按道理来说1 + 1 > 1，
那为什么还用学习vector和list，直接学deque多方便

deque的缺点

内存占用较大：
如下图所示，deque需要维护多个缓冲区（或称为段），这些缓冲区之间通过指针或引用相互连接。这种非连续存储的方式虽然提高了在两端操作的效率，但也导致了额外的内存开销，因为需要存储这些指针或引用。因此，deque的内存占用通常会比vector大。
中间插入或删除操作效率较低：
尽管deque在两端进行插入或删除操作的时间复杂度为O(1)，但在中间位置进行这些操作时，效率并不高。因为需要找到正确的段并可能移动段内的元素，或者在某些情况下甚至需要合并或拆分段，这可能导致时间复杂度增加到O(n)。相比之下，list在中间位置进行插入或删除操作时更加高效。
遍历麻烦(致命缺陷)：
在遍历时，deque的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下，但是一般用到这种线性结构存储的都会需要遍历，所以deque在平时就用不到

deque底层构造
在这里插入图片描述