环形队列（环形队列不会产生什么溢出）



队列我们其实并不陌生。在生活中的排队本身也是一种队列。在旧时代（泛指非信息时代）的抽号机防插队也是用了这个。

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾，进行删除操作的一端称为队头。

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，队列在数组第一位弹出数据，可能伴随移位的操作，效率会比较低。即使不用移位，也会造成空间浪费。

5.2.1 链表实现

我们采用一个链表和两个指针的方式来模拟队列。术语 (指针)指向(指针)指的是作为指针变量，存放有（指针）的地址。

基本信息

链式结构：表示队列

队列的结构

之所以这么定义，是因为不是所有场合都用得到头、尾指针。这样分开，一个结构体代表整体，另一个结构体用于操作队列，使得队列的使用更方便。

功能

初始化(Init)

代表一个队列的指针置空。

队列长度（下文简称队长）置0。

队列销毁(Destroy)

可参考链表操作的伪代码：

链表头结点标记队头即可。

销毁链表之后进行一次初始化(Init)操作即可。

入队(push)

申请一个结点。

若队列处于刚初始化的状态，则新申请的结点即是队首也是队尾。

若队列中有结点，将队尾的指针域指向新申请的结点即可。

队长加1。

出队(pop)

出队即单链表的头删。分两种情况：

1. 一个结点
   释放头结点，后进行队列初始化(Init)操作。
2. 多个结点
   先标记头结点后的第二个结点。
   释放头结点。将第二个结点更新为新的头结点。

不要忘记队长减一。

获取队首元素(Front)

一般是返回队首的数据域里的数据，因为头结点虽然能随时访问，但以后使用c++的话，可能需要限制对数据的访问。

同时不要忘记先判断队列是否为空。

获取队尾元素(Back)

同获取队首元素(Front)一样，只是指针变成了尾结点。

获取队列长度(Size)

若定义中有定义变量来存储，返回这个变量即可。

若没有，则需要通过遍历链表来获得长度。

遍历链表同样遵循伪代码：

判断队列是否为空(Empty)

若定义中有定义变量来存储，判断这个变量是否为0即可。

若没有，则需要判断头、尾结点指针是否为空。

参考程序

Queue.h

Queue.c

5.2.2 数组实现循环队列

我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。环形队列可以使用数组实现，也可以使用循环链表实现。

我们依旧从队列的功能角度对循环队列进行分析。分析的是数组实现的循环队列。

可通过这个OJ题来检测自己设计的循环队列：622. 设计循环队列 - 力扣（LeetCode）

基本信息

我们定义用变量代表队首，变量代表队尾。

数组代表队列本体。

变量表示数组的大小。

功能

初始化(Init)

，都赋予相同的值（数组表示循环队列的话推荐0）。

数组开多少单位决定队列能容纳多少数据，可根据情况选择。

入队(push)

若为准备入队的新数据，这里规定即为入队。每次成功入队后，进行一次防止溢出。

出队(pop)

这里规定即可完成出队操作。

每次成功出队后，进行一次防止溢出。

至于数据是否清空，取决于个人喜好。

判断队列是否为空(Empty)

若当时队列为空，可能会出现这种情况：

所以为了避免这种情况出现，我们可以做如下处理：

(1) 留1个空间控制。此时当时队满。

(2) 增加记录队长的变量size。当时队空，当时队满。

这里选择留1个空间控制。此时当时队列为空。

判断队列是否为满(Full)

因为是从用数组建立环形队列的角度来看，而数组即使要扩容也需要判断容量，所以需要判断队列是否为满就有必要。

将这个环用方块拼在一起的图形来代替。

到这里可以看出，循环列表避免不了的前一个数据是的情况，所以单向循环链表实现的循环队列获取队尾并不方便。若一定要用链表实现，解决思路：

1. 从一开始就用双向链表。
2. 增加一个队首前指针标记尾元素。
3. 遍历获取数据（效率最差的一种方式）。

这个队列我们可以认为满队时存在个数据，开了个空间。

满队的标志：。

例如这里。

数组的下标是从0开始，所以也即。

所以可以通过表达式来判断队列是否满员。

获取队尾元素(Back)

我们将两个一样的队列拼在一起。

虽然的内容即为队尾，但当时不符合数组的下标访问方式的要求，所以我们对qb进行一定的处理。

所以队尾为。

队列销毁(Destroy)

释放申请的空间。其他变量全部置0。

但销毁后的循环队列要先初始化(Init)后才能再次使用。

获取队首元素(Front)

队首即为。在每次入队(push)时都会做一次取模处理，所以这里可以不做处理。

获取队列长度(Size)

考虑到可能比小，我们需要做预处理。

例如这个队列，将两个队列拼在一起。

所以可以很容易的看出队列长度为。

参考程序

版权声明：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！

转载请注明出处，原文链接：https://www.xkablog.com/bcyy/71949.html