C++数据结构之队列_c++队列

这里详细总结一下C++中队列这个数据结构，涉及队列的基本知识，以及队列的变种还有相应的应用场景等，总体来说算是一个知识的检索，不过遇到自己感兴趣的知识，还是会对其进行尝试。

队列的基础知识

简单来说，队列是一种 「先进先出（First In First Out）」 的线性表，简称为 「FIFO 结构」。

具体来说，参考如下

01.队列基础知识 | 算法通关手册 (itcharge.cn)

队列的基本操作

• 初始化空队列：创建一个空队列，定义队列的大小 size，以及队头元素指针 front，队尾指针 rear。
• 判断队列是否为空：当队列为空时，返回 True。当队列不为空时，返回 False。一般只用于「出队操作」和「获取队头元素操作」中。
• 判断队列是否已满：当队列已满时，返回 True，当队列未满时，返回 False。一般只用于顺序队列中插入元素操作中。
• 插入元素（入队）：相当于在线性表最后一个数据元素后面插入一个新的数据元素。并改变队尾指针 rear 的指向位置。
• 删除元素（出队）：相当于在线性表中删除第一个数据元素。并改变队头指针 front 的指向位置。
• 获取队头元素：相当于获取线性表中第一个数据元素。与插入元素（入队）、删除元素（出队）不同的是，该操作并不改变队头指针 front 的指向位置。
• 获取队尾元素：相当于获取线性表中最后一个数据元素。与插入元素（入队）、删除元素（出队）不同的是，该操作并不改变队尾指针 rear 的指向位置。

队列的基础知识和队列的基础操作，决定了数据结构中队列的与众不同，这些是核心的东西。

循环队列

简单来说：队列作为原本的线性关系的数据结构，而循环队列将其首尾相连，从逻辑上看成一个环，和循环链表类似，但是操作还是队列的操作。

具体来说，参考百度百科：

循环队列_百度百科 (baidu.com)

01.队列基础知识 | 算法通关手册 (itcharge.cn)

上述第一个链接队列的基础知识也有循环队列的实现。

循环队列的出现是为了解决“假溢出”问题，当你使用数组这种结构作为底层实现队列时，才会出现这种问题。

这里盗了一个图（嘿嘿），我们可以看到每次出队和入队，我们只是改变指针的位置。所以每次出队，前面的空间就不会在使用，同样的，每次入队，尾部指针就会向后指，这样久而久之就会出现这样的“假溢出”问题，明明空间是够的，但是最后显示的结果确实栈溢出。

优先队列

简单来说：优先队列进栈的顺序是无关紧要的，但是出栈的顺序则需要按照最高级别的规则进行出队。

具体来说，可以参考如下的知识。

01.优先队列知识 | 算法通关手册 (itcharge.cn)

举例说明:

比如迪杰斯特拉算法，如果采用标号法计算的话，就需要每次从未标号的数据中取出距离标号数据最近的数据。那么未标号的节点通过计算入队的顺序是无所谓，但是出队一定要是那个最短的距离。

优先队列的实现一般有三种，堆、数组、链表。

这里详细讲解一下优先队列的堆实现。让你对优先队列有一个更加深刻的认知。优先队列的底层可以采用数组，链表，但是效率都没有采用堆来的快。

这里采用二叉堆来实现优先队列。首先是堆这个结果，我们可以看到

堆结构中的数据是按照 父节点<左孩子节点<右孩子节点的顺序进行排列。

1. 当插入一个新元素的时候，元素处于堆的末尾。
2. 当新插入的元素破坏了原来数据的平衡，就需要进行调整。
3. 调整速度，根据二叉堆，时间在O(logn)。

所以我们发现优先队列的和堆排序一样，借用堆的结构，每次取出最大或者最小值即可。

双端队列

简单来说：双端队列，就是同时具有栈和队列的性质，可以进行入队，出队，入栈，出栈的操作。不过局限的是，每次只能控制队列的头部和尾部元素的进出。

应用场景

这里找到了一个有意思的应用场景，那就是工作密取

在生产者-消费者模式中，所有消费者都从一个工作队列中取元素，一般使用阻塞队列；这里的阻塞队列先不管。

而工作密取模式中，每个消费者有其单独的工作队列，如果它完成了自己的双端队列，那么它就可以从其他消费者的双端队列的末尾秘密地获取工作。这简直就是资本家的压迫，不会让任何一个线程停下来。

更形象一点来说

例如网页爬虫程序中处理一个页面时，通过会发现更多的页面需要处理，都可以通过工作密取机制来实现高效并行。当一个工作线程找到新的任务单元时，他会将其放到自己队列的末尾。当双端队列为空时，他会在另一个线程的队列末尾查找新的任务，从而确保每个线程都保持忙碌状态。

大致就介绍这几种常用的队列结构，其他队列结构用到了在进行使用。