队列 queue | 彩潭有鲤的札记

type

status

date

slug

summary

队列

队列（queue）是一种具有「先进入队列的元素一定先出队列」性质的表。只允许在一端进行插入数据操作，在另一端进行删除数据。由于该性质，队列通常也被称为先进先出（first in first out）表，简称 FIFO 表。

入队列：进行插入操作的一端称为队尾

出队列：进行删除操作的一端称为队头

入队出队形式：一种入队顺序，只有一种出队顺序。

队列的存储结构

「顺序存储的队列」：利用一组地址连续的存储单元依次存放队列中从队头到队尾的元素，同时使用指针 phead 指向队头元素在队列中的位置，使用指针 ptail 指示队尾元素在队列中的位置。

数组模拟队列

「链式存储的队列」：利用单链表的方式来实现队列。队列中元素按照插入顺序依次插入到链表的第一个节点之后，并使用队头指针 phead 指向链表头节点位置，也就是队头元素，ptail 指向链表尾部位置，也就是队尾元素。

C++ STL中的队列

cplusplus.com

https://cplusplus.com/reference/queue/queue/

适配器模式是一种设计模式，用于将一个类的接口转换成客户所期望的另一种接口。stack和queue虽然可以存放元素，但在STL中并没有将其划分在容器的行列，而是将其称为容器适配器，因为stack和queue只是对其它容器的接口进行了包装。stack和queue默认使用的是deque

函数声明	接口说明
`queue()`	构造空的队列
`empty()`	检测队列是否尾空，是返回 ture，否则返回 false
`size()`	返回队列中有效元素的个数
`front()`	返回队头元素的引用
`back()`	返回队尾元素的引用
`push()`	在对尾将元素 val 入队列
`pop()`	将队头元素出队列

优先队列

优先队列（Priority Queue）：一种特殊的队列。在优先队列中，元素被赋予优先级，当访问队列元素时，具有最高优先级的元素最先删除。

优先队列与普通队列最大的不同点在于出队顺序：

普通队列的出队顺序跟入队顺序相关，符合先进先出的规则

优先队列的出队顺序跟入队顺序无关，优先队列是按照元素的优先级来决定出队顺序的。优先级高的元素优先出队，优先级低的元素后出队。优先队列符合最高级先出的规则

优先队列的应用场景非常多，比如：

数据压缩：赫夫曼编码算法

最短路径算法：Dijkstra 算法

最小生成树算法：Prim 算法

任务调度器：根据优先级执行系统任务

事件驱动仿真：顾客排队算法

排序问题：查找第 k 个最小元素

优先队列的实现方式

优先队列的实现方式有很多种，除了使用「数组（顺序存储）实现」与「链表（链式存储）实现」之外，最常用的是使用「二叉堆结构实现」优先队列：

数组（顺序存储）实现优先队列：入队操作直接插入到数组队尾，时间复杂度为。出队操作需要遍历整个数组，找到优先级最高的元素，返回并删除该元素，时间复杂度为

链表（链式存储）实现优先队列：链表中的元素按照优先级排序，入队操作需要为待插入元素创建节点，并在链表中找到合适的插入位置，时间复杂度为。出队操作直接返回链表队头元素，并删除队头元素，时间复杂度为。

二叉堆结构实现优先队列：构建一个二叉堆结构，二叉堆按照优先级进行排序。入队操作就是将元素插入到二叉堆中合适位置，时间复杂度为。出队操作则返回二叉堆中优先级最大节点并删除，时间复杂度也是。

下面是三种结构实现的优先队列入队操作和出队操作的时间复杂度总结。

ㅤ	入队操作时间复杂度	出队操作（取优先级最高的元素）时间复杂度
堆
数组
链表

可以看出，使用「二叉堆」这种数据结构来实现优先队列是比较高效的。

二叉堆实现的优先队列

时间复杂度： 空间复杂度：

C++ STL中的优先队列

cplusplus.com

https://cplusplus.com/reference/queue/priority_queue/

函数声明	接口说明
`priority_queue()`	构造空的队列
`empty()`	检测队列是否尾空，是返回 ture，否则返回 false
`size()`	返回队列中有效元素的个数
`top()`	返回队top元素的引用
`emplace()`	构造和插入元素
`push()`	在对尾将元素 val 入队列
`pop()`	将队头元素出队列
`front()`	返回容器中第一个元素的引用
`push_back()`	在容器尾部插入元素
`pop_back()`	删除容器尾部元素

queue题目

前 K 个高频元素

题目：给一个整数数组nums和一个整数 k ，请你返回其中出现频率前k高的元素。你可以按任意顺序 返回答案。

示例：

数据流的中位数

题目：中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。arr = [2,3,4]的中位数是 3 ，arr = [2,3]的中位数是(2 + 3) / 2 = 2.5

实现MedianFinder类:

MedianFinder() 初始化 MedianFinder 对象。

void addNum(int num) 将数据流中的整数 num 添加到数据结构中

double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 105 以内的答案将被接受。

用两个优先队列和分别记录大于中位数的数和小于等于中位数的数。当累计添加的数的数量为奇数时，中的数的数量比多一个，此时中位数为的队头。当累计添加的数的数量为偶数时，两个优先队列中的数的数量相同，此时中位数为它们的队头的平均值。