【队列】如何设计循环队列？-力扣622【超详细的解题思路和注释】

说在前面

其实数据结构-队列是一种特殊的线性表，设计循环队列其实也是队列方面的一道特别经典的题目，如果用

纯C

实现，它极好地考察了我们C语言的功底。
如果对数据结构-队列还没有很好了解的同志们，可以看看博主的数据结构专栏和有关栈和队列的总结博客哦！传送门在这里给到大家了。

• 数据结构
• 【栈和队列】纯C实现栈和队列以及其基本操作-宝藏级别数据结构教程【保姆级别详细教学】

此篇，博主带着大家用纯C实现这个循环队列，顺便巩固扎实我们的C语言基础

题目：622.design-circular-queue

导航小助手

博主给大家的话

那么这里博主先安利一下一些干货满满的专栏啦！

数据结构专栏：数据结构 这里包含了博主很多的数据结构学习上的总结，每一篇都是超级用心编写的，有兴趣的伙伴们都支持一下吧！
算法专栏：算法 这里可以说是博主的刷题历程，里面总结了一些经典的力扣上的题目，和算法实现的总结，对考试和竞赛都是很有帮助的！
力扣刷题专栏：Leetcode 想要冲击ACM、蓝桥杯或者大学生程序设计竞赛的伙伴，这里面都是博主的刷题记录，希望对你们有帮助！
C的深度解剖专栏：C语言的深度解剖 想要深度学习C语言里面所蕴含的各种智慧，各种功能的底层实现的初学者们，相信这个专栏对你们会有帮助的！

题目描述和要实现的接口

要实现的接口：

题目和思路的分析详解-链式或数组？

图片来自比特就业课

分析：
其实看到循环，我们其实很容易可以想到环形链表，将单链表首尾相连。因为是静态的，我们如果队列是

k

个储存空间，现在我们开

k

个节点，依次链接起来。我们定义

head

和

tail

指针，一开始

head==tail

，如果插入一个数据我们的

tail=tail->next;

如果删除数据，我们

head=head->next;

即可，这个我们是必须要想到的。
但是在这种情况下，我们发现一个问题，当队列为空的时候，

head ==tail

,当队列满的时候，也是

head ==tail

，这样就出问题了。因此，开

k

个节点是不够的！我们要开

k+1

个！ 此时，当tail的下一个是

next

的时候，表示队列已满。
当然，除了这种解决方案，我们多加一个

size

表示队列的大小，当

size==k

的时候满也是可以的。

• 这种思路是完全可以做出这道题的，但是我们考虑一下，去tail上的数据的时候，我们还需要一个prev记录前一个节点，因为我们插入一个数据是在tail位置上插入的，插入之后tail=tail->next;

但是如果我们使用数组来实现这个环形队列，我们就没有这个问题，因为数组可以做到数据的随机访问。

**思路是一样的，只是我们的

head

和

tail

不再是指针，是下标了。**

• 用数组实现要注意的点：注意边界的控制，如果指针出去了，越界了，绕一下绕回0的位置，或者用取模的方式都可以解决！

关于实现过程中边界控制等一些细节，博主将在代码的注释中给大家解释清晰！

实现完整代码

typedefstruct{int* a;//数组int k;//队列的大小int head;//头下标int tail;//尾下标} MyCircularQueue;//isFull()和isEmpty()这两个函数放到前面来，因为后面要用，或者写一个前置声明也是可以的。boolmyCircularQueueIsFull(MyCircularQueue* obj){//注意tail在数组最后，head在最前的特殊情况int next = obj->tail +1;//如果next超范围了，回去if(next == obj->k +1){
        next =0;}return next == obj->head;}boolmyCircularQueueIsEmpty(MyCircularQueue* obj){return obj->head == obj->tail;//如果head==tail一定就是空的}

MyCircularQueue*myCircularQueueCreate(int k){
    MyCircularQueue* obj =(MyCircularQueue*)malloc(sizeof(MyCircularQueue));//先搞一个节点出来//这里的malloc是将环形队列创建出来
    obj->a =(int*)malloc(sizeof(int)*(k +1));//多开一个空间//这里的malloc是将环形队列里面的数组创建出来
    obj->head = obj->tail =0;//这里head tail是下标
    obj->k = k;return obj;}boolmyCircularQueueEnQueue(MyCircularQueue* obj,int value){if(myCircularQueueIsFull(obj))returnfalse;//满了，不能插入
    obj->a[obj->tail]= value;//在tail的位置放val
    obj->tail++;//但是要控制边界if(obj->tail == obj->k +1){
        obj->tail =0;//把下标绕回来}returntrue;}boolmyCircularQueueDeQueue(MyCircularQueue* obj){//空了，不能删除if(myCircularQueueIsEmpty(obj))returnfalse;++obj->head;if(obj->head == obj->k +1){
        obj->head =0;}returntrue;}intmyCircularQueueFront(MyCircularQueue* obj){//按照题目要求，如果空了，返回-1if(myCircularQueueIsEmpty(obj))return-1;return obj->a[obj->head];}intmyCircularQueueRear(MyCircularQueue* obj){//空了，返回-1if(myCircularQueueIsEmpty(obj))return-1;int prev = obj->tail -1;if(obj->tail ==0){
        prev = obj->k;}return obj->a[prev];}voidmyCircularQueueFree(MyCircularQueue* obj){//先free数组//再free循环队列//否则会造成内存泄漏！free(obj->a);free(obj);}

离开之前

看到这里，如果伙伴们觉得有帮助的话，不要忘记一键三连哦！