---

前言

循坏队列，本质是队列数据结构。普通队列，入数据时可能会增容，出数据会浪费空间。

因此设计一款循环队列，能够利用队列前的空间。

本文针对循坏队列的优势，循坏队列的思路以及实现进行深入剖析。

一、CircularQueue

循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

二、特点

优点：

        提前根据需求，开辟相应的空间，不需要后续增容；

        充分地使用数组中的存储空间，克服”假溢出”现象；

缺点：

        固定容量，使用时必须把握是否满容；

三、设计思路

循环队列就是首尾相连的线性结构。

 设计头指针（front）和尾指针（rear）

每次插入数据rear往前走一步，删除数据front往前走一步。如果能合理掌控，那么front和rear能在循坏队列的每一个位置持续走动。、

针对循坏队列，应设计如下接口：

1）判空与判满

判空：
front==rear时，标记为空。

判满：

因为front==rear表示空，那么判满就不能用front==rear.

        设计：

             1.增加一个size变量，每次存数据size就++。用size来判断是否满

             2.rear+1=front

             每次存入一个元素rear就往前走一步，rear在最后一个元素的下个位置。当     rear+1==front时，判断满。因此在设计队列的容量时，多开辟一个空间。

下图表示一个容量大小为7的循环队列满时的情况

2）链表还是数组实现？

链式结构，首尾可以轻松链接.

但是在创建循环队列时，链接多个结点，过于麻烦。

出尾部数据麻烦：

        改进思路：1.添加rearprev指针  2.遍历一遍队列  3.双向循坏链表

不难发现，链表实现还是比较麻烦的。本文将介绍数组实现循环队列。

四、实现

typedef struct {int front;int rear;int*a;int k; 
} MyCircularQueue;

1).IsEmpty()

rear==front

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {if(obj->rear==obj->front)return true;return false;
}

2).IsFull()

分俩种情况，

1.rear+1不会溢出

 rear+1==front 判满

2.rear+1溢出

 此时为空，但是rear+1!=front 

则需要对rear+1取模

(rear+1)%(k+1)==front

为什么模上k+1而不是k :因为开辟空间是k+1,相当于长度是k+1。例如上述k为5，rear此时为5  

（5+1）%（5+1）=0  刚好为front的下标 判断成立。

bool myCircularQueueIsFull(MyCircularQueue* obj) {if((obj->rear+1)%(obj->k+1)==(obj->front))return true;return false;
}

3)CircularQueueCreate创建

循环队列的创建

先创建obj队列指针，再对数组开辟空间，注意空间大小是K+1

MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));obj->a=(int*)malloc(sizeof(int)*(k+1));  //多开一个空间obj->front=obj->rear=0;obj->k=k;return obj;
}

4）CircularQueueEnQueue插入

要插入先检查是否为满

插入的位置为rear,每次插入后rear往后走一步，但是rear会存在溢出，所以每次插入都对rear取模

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj))return false;obj->a[obj->rear]=value;obj->rear++;obj->rear%=(obj->k+1);return true;
}

5）CircularQueueDeQueue删除

要检查是否为空

每次删除，front往前走一步就可

front会存在溢出，同4）需对front取模

bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return false;obj->front++;obj->front%=(obj->k+1);return true;
}

6）出队尾和队头

特别注意的是，当rear位于第一个位置时，如下

rear-1为非法值，需要将rear移到最后一个位置上

这里提供一个巧妙的方法：
将rear+k+1,相当于容量变成二倍，rear往后移动一个容量的长度

rear+k+1-1（rear+k）就实现将rear移到最后一位上

如果rear不在第一个位置，那么需要对rear+k取模

 

int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;return obj->a[obj->front];
}int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;return obj->a[(obj->rear+obj->k)%(obj->k+1)];
}

五、总结

循环队列因为其可重复利用空间而受到推崇，在判满和出队尾数据时需要注意rear的不同

本文详细讲解每个细节，希望对大家有所帮助！

编程学习没有捷径，要多写多练，感谢阅读。