-
冰冰学习笔记：循环队列的实现
欢迎各位大佬光临本文章！！！
还请各位大佬提出宝贵的意见，如发现文章错误请联系冰冰，冰冰一定会虚心接受，及时改正。
本系列文章为冰冰学习编程的学习笔记，如果对您也有帮助，还请各位大佬、帅哥、美女点点支持，您的每一分关心都是我坚持的动力。
我的gitee：冰冰棒 (bingbingsupercool) - Gitee.
https://gitee.com/bingbingsurercool
系列文章推荐
目录
前言
本文是《栈与队列》练习题的延续，前文讲到几道经典练习题，但是并未对循环队列进行讲解。博主原本想偷懒不写了，结果这两天重新看到这道题的时候有些生疏，看来还是没有对该题目熟稔于心，本想看看博客笔记进行知识点回顾，结果发现自己并未进行讲解记录。因此决定将此题记录下来，以备不时之需。
1.设计循环队列
题目链接：622. 设计循环队列 - 力扣（LeetCode）
题目描述：设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列与循环链表类似，均是首尾相连的数据存储结构，它具备队列的所有性质，并且存储空间一旦开辟完毕，就会对其进行循环使用。通过题目给出的函数接口我们可以看到，循环队列在调用构造器函数时，会把队列实际长度k传递过来，并构建出一个能存储k个数据的循环队列。剩余的即为队列的常规操作函数，注意有些函数需返回布尔值。本文将用两种方式来进行循环队列的搭建，链表形式和数组形式。
1.1使用链表构建的原理和注意事项
对于循环队列的实现，我们首先想到的就是利用链表的形式进行搭建，毕竟我们只需要将最后一个结点中的next指针连接到头指针即可构成循环状态。由于队列只能从队尾进行数据存储，从队头进行数据弹出，因此我们可以设计一个tail指针用来记录队尾，head指针用来记录队头。每次存储数据直接在tail指针指向的位置进行插入，随后tail指针向后移动。当tail指针与head指针相遇时，说明循环队列已满，数据无法存储。
但是这里出现了个问题，当数据进行删除时，head指针将向后移动，那么如何判断队列为空呢？head遇到tail?如果这样，判空与判满存在歧义，均为两者相遇。当然我们可以将长度k设为参考值，并设计全局变量size。队列未存储数据时，size为0，增加数据则size++，减少数据则size--。当size与k相同时，队列已满，size为0则队列为空。还有一种方式就是多开辟一个结点来构建循环队列，长度为k则开辟k+1个结点，当tail的next指向head时则表示队列已满，当head和tail相遇则表示队列为空。
就算如此，链表形式的循环队列在取队尾数据时也并不好操作，因为tail指针并非指向最后一个数据，而是指向最后一个数据的下一个位置。解决此种方式我们当然可以让tail指向最后一个数据存储的位置，然后在存放数据的时候，将新数据放在tail的next指向的位置，然后tail再移动到下一个位置。判断数列是否满的条件就应该改为tail->next->next是否等于head，但是该种方式在进行数据删除和判空条件时又会出现各种问题，因此我们直接在队列结构中增加tailprev指针用来标记tail的前一个结点位置，返回队尾数据直接返回tailprev->data即可。
因此最终链表实现循环队列的结构如下所示：
- //链表实现方式
- typedef int QueueDataType;
- //结点
- typedef struct QueueNode
- {
- QueueDataType data;
- struct QueueNode* next;
- }QNode;
- //环形队列
- typedef struct Queue
- {
- QNode* head;
- QNode* tail;
- QNode* tailprev;
- }MyCircularQueue;
1.2使用数组构建的原理和注意事项
如前文所讲，既然链表实现方式如此复杂繁琐，那么用数组实现可以吗？答案是肯定的，使用数组实现将会避免上诉出现的问题，但也有一些值得注意的点。使用数组构建时也需要向链表结构那样，多开辟一个空间避免判空和判满出现歧义。数组实现的队列结构中，head指向的为队列开头的下标，tail指向的是队列末尾的下标。当head和tail相同时，则表明队列为空，如果tail+1=head则表明队列为满。此时返回队头队尾数据就可以利用数组物理空间存储的连续性来进行下标的加减操作访问数据，不在那么繁琐。
但是，循环队列逻辑上是一个闭环，物理空间上可不是，我们就需要考虑边界问题。假设队列长度为4，实际需要开辟5个空间，当tail指向下标为4的地方时，存储数据后，tail++移动到下标为5的位置，数组发生越界，逻辑上此时队列应该放满数据，tail和head相遇了，但是实际上并没有。我们应该在此时处理这种边界问题，让tail回到数组起始位置，数据删除，判空，判满时也有此种边界问题，应格外注意。
对于边界问题的解决就需要有数据来记录队列长度k，对超过边界的数据进行取模操作或者进行条件判断，因此数组形式的队列结构中应包含如下元素：队头下标head，队尾下标tail，队列长度k，队列数组指针pq。
- 环形队列
- typedef struct Queue
- {
- int* pq;
- int k;
- int head;
- int tail;
- }MyCircularQueue;
2.链表形式的循环队列
2.1循环队列构建函数
题目在进行队列构建时会将队列实际长度k进行传递，我们只需要使用循环将创建的每个结点进行连接即可。我们首先将队列obj开辟出来，并将其参数head，tail，tailprev置为空指针；然后创建next结点记录head的值，方便在循环中连接结点。
进入循环后，由于开辟的结点数为k+1，所以循环控制条件为k+1，每连接一个结点k减少1。在进行结点连接时我们要分为两种情况，一种为第一个结点的连接，此时head，指向NULL，因此需要将新节点作为队列头指针head，并同时更新tail和tailprev的指向；第二种就是将结点依次连接在head后面的过程。连接完毕后，将obj返回。
函数代码：
- MyCircularQueue* myCircularQueueCreate(int k)
- {
- MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
- if ( obj == NULL )
- {
- perror("malloc:");
- exit(-1);
- }
- obj->head = obj->tail =obj->tailprev= NULL;
- QNode* next = obj->head;
- while ( k + 1 )
- {
- QNode* newnode = (QNode*)malloc(sizeof(QNode));
- if ( obj->head == NULL )
- {
- obj->head = obj->tail = obj->tailprev = newnode;
- next = obj->head;
- }
- else
- {
- next->next = newnode;
- next = newnode;
- next->next = obj->head;
- }
- k--;
- }
- return obj;
- }
2.2数据插入函数
数据插入之前我们要进行队列判满操作，当队列数据存储已满的时候，需要返回false，成功插入数据后返回true。对于第一次数据插入，head，tail，tailprev均指向第一个结点，因此我们只需要将数据存放到tail指向的data之中即可，然后更新tailprev为当前存放数据的结点即tail的位置，然后将tail更新至tail->next，下次数据插入时直接在tail处进行数据插入，不用遍历寻找队尾。
函数代码：
- bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
- {
- assert(obj);
- if ( myCircularQueueIsFull(obj) )
- {
- return false;
- }
- obj->tail->data = value;
- obj->tailprev = obj->tail;
- obj->tail = obj->tail->next;
- return true;
- }
2.3数据删除函数
循环队列的数据删除并不需要结点的释放，因为结点需要循环使用，实际上里面的数据也不需要删除，在下一次进行数据存储的时候直接将其覆盖即可。但是删除数据之前我们还是需要对其进行队列的判空处理，只有队列非空才能对其进行删除。队列的性质表明数据的删除只能在队头进行，因此想让其无法访问到，只需将队头指针head向后移动即可，此时就对数据进行了删除操作。 成功删除返回true，否则返回false。
函数代码：
- bool myCircularQueueDeQueue(MyCircularQueue* obj)
- {
- assert(obj);
- if ( myCircularQueueIsEmpty(obj) )
- {
- return false;
- }
- obj->head = obj->head->next;
- return true;
- }
2.4队头队尾数据返回函数
在创建队列结构时，我们使用tailprev对其队尾数据结点进行了记录，因此返回队尾数据只需要返回tailprev指向的data即可；队头数据的返回更加简单，直接返回head指向的data。但是在数据返回之前都需要对队列进行判空处理。
函数代码：
- int myCircularQueueFront(MyCircularQueue* obj)
- {
- assert(obj);
- if ( myCircularQueueIsEmpty(obj) )
- {
- return -1;
- }
- return obj->head->data;
- }
- //
- int myCircularQueueRear(MyCircularQueue* obj)
- {
- assert(obj);
- if ( myCircularQueueIsEmpty(obj) )
- {
- return -1;
- }
- return obj->tailprev->data;
- }
2.5队列的判满和判空函数
循环队列的判满和判空在前文已经提到，空队列的条件就是head指针与tail指针相遇，满队列的条件是tail->next与head相遇。
2.6队列销毁函数 销毁之前我们需要知道一共向内存申请开辟了多少空间，在创建队列函数中，我们一共申请了两次空间，第一次是申请空间来创建队列结构，包含head，tail，tailprev，另一次是循环内部连接结点时创建的新节点的空间，一共是k+1个结点，所以我们需要释放两次。
首先利用循环将结点释放，然后将obj指向的三个指针置为NULL，最后将obj释放。
函数代码：
- void myCircularQueueFree(MyCircularQueue* obj)
- {
- QNode* cur = obj->head->next;
- while ( cur != obj->head )
- {
- QNode* next = cur->next;
- free(cur);
- cur = next;
- }
- free(obj->head);
- obj->head = obj->tail = obj->tailprev = NULL;
- free(obj);
- }
3.数组形式的循环队列
3.1循环队列构建函数
与链表实现方式一样，使用数组实现的时候也需要将队列长度k进行传递，但是我们不需要利用循环进行结点的创建和连接，我们只需要直接开辟k+1个数据空间即可。在数组空间开辟之前，还需要对队列obj进行空间的开辟，前文已经将obj的结构进行了分析，里面包含4个参数。空间开辟后，将obj指向的pq指向新开辟的数组空间，并将head，tail置为数组开头位置的下标0，obj指向的k设为队列长度k。
函数代码：
- MyCircularQueue* myCircularQueueCreate(int k)
- {
- MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
- if ( obj == NULL )
- {
- perror("malloc:");
- exit(-1);
- }
- obj->pq = (int*)malloc((k + 1) * sizeof(int));
- obj->k = k;
- obj->head = obj->tail = 0;
- return obj;
- }
3.2数据插入函数
对于数组进行队列的数据的插入，我们要先进行判满操作，然后执行数据插入。在插入时我们只需要知道数组下标就可以进行数据插入。在队列结构中，head为队列开头位置的下标，tail为队列结尾数据的下一个位置的下标，因此我们只需要将新数据放在obj->tail下标的位置，然后让下标后移即可。但是我们要注意边界问题，当tail自增后如果达到数据边界，应该让其回到队列开头位置，因此需要对tail进行取余操作，但并非对k取余而是对数组实际长度k+1进行取余。
函数代码：
- bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
- {
- assert(obj);
- if ( myCircularQueueIsFull(obj) )
- {
- return false;
- }
- obj->pq[obj->tail] = value;
- obj->tail++;
- obj->tail %= (obj->k + 1);
- return true;
- }
3.3数据删除函数
数据删除也要考虑边界问题，只不过数据删除时移动的是head，head向后移动，当到达边界时，head也要进行取余操作。这里也可以进行条件语句判断是否到达边界，下面进行取余的操作均可用这种判断代替。数据的删除要确保队列非空，因此免不了判空操作。
函数代码：
- bool myCircularQueueDeQueue(MyCircularQueue* obj)
- {
- assert(obj);
- if ( myCircularQueueIsEmpty(obj) )
- {
- return false;
- }
- obj->head++;
- //if(obj->head==obj->k)
- //{
- // obj->head=0;
- //}
- obj->head %= (obj->k + 1);
- return true;
- }
3.4队头队尾数据返回函数
队头数据的返回比较简单，在队列不为空的情况下，直接取出head下标对应的数据即可，但是对于队尾数据我们依然要考虑边界问题。当tail位于head后面，可以直接返回tail-1位置的数据，但是当tail在head前面时返回的不一定是tail-1位置的数据了。
因此tail-1要加上实际数组长度k+1，然后对其实际长度k+1取余得到的就是正确的位置。
函数代码：
- int myCircularQueueFront(MyCircularQueue* obj)
- {
- assert(obj);
- if ( myCircularQueueIsEmpty(obj) )
- {
- return -1;
- }
- return obj->pq[obj->head];
- }
- int myCircularQueueRear(MyCircularQueue* obj)
- {
- assert(obj);
- if ( myCircularQueueIsEmpty(obj) )
- {
- return -1;
- }
- return obj->pq[(obj->tail + obj->k) % (obj->k+1)];
- }
3.5队列的判满和判空函数
队列的判空采用的head与tail相遇，判满采用的是tail+1与head相等，因此tail+1之后也需要对其取余。
函数代码：
- bool myCircularQueueIsEmpty(MyCircularQueue* obj)
- {
- assert(obj);
- return obj->head == obj->tail;
- }
- bool myCircularQueueIsFull(MyCircularQueue* obj)
- {
- assert(obj);
- int next = (obj->tail + 1) % (obj->k + 1);
- return next == obj->head;
- }
3.6队列销毁函数
销毁函数也和链表类似，先销毁掉pq指向的数组空间，在销毁掉obj指向的空间。
函数代码：
- void myCircularQueueFree(MyCircularQueue* obj)
- {
- assert(obj);
- free(obj->pq);
- free(obj);
- }
总结
循环队列也是一种重要的存储结构，其具备空间利用率高的特点，博主建议采用数组形式进行队列的构建，此种方式相比于链表结构相对简单易理解，并且实现起来容易，仅需要考虑一个边界问题即可。最后附上循环队列实现的代码仓库地址：循环队列
https://gitee.com/bingbingsurercool/data-structure-warehouse/commit/a1d212e8da815a48f2ad3a15ae6ccd5072518ff4 -
相关阅读:
MQTT的认识（1）
防火墙日志记录和监控在网络安全中的重要性
Scala 入门指南：从零开始的大数据开发
WPF XAML中使用依赖属性
如何用PHP获取各大电商平台的数据
关于css溢出
PostgreSQL下载和安装教程
java与es8实战之四：SpringBoot应用中操作es8(无安全检查)
Leetcode79单词搜索
小程序容器技术，加速车联网安全生态运转
- 原文地址：https://blog.csdn.net/bingbing_bang/article/details/125423972