文章目录
- 1. 什么是循环队列？
- 2. 结构的选择：数组 or 链表？
- 链表结构分析
- 数组结构分析
- 判空判满
- 入数据出数据
- 取队头队尾元素
- 3. 代码实现（数组结构）
- C语言版本
- C++版本
这篇文章我们来学习一下如何实现循环队列
那力扣上呢有一个对应的题我们可以来看一下：
1. 什么是循环队列？
循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。
要求我们实现的循环队列要有以下几个接口：
2. 结构的选择：数组 or 链表？
那下面要实现循环队列的话，我们采用哪种结构呢，数组还是链表呢？
我们假设循环队列的长度k（当然实现好之后k传几构造出来长度就是几）为4，我们来分析一下。
首先我们来分析一下用链表行不行
链表结构分析
那链表的话我们是不是正好可以用一个循环链表啊，因为我们现在要实现循环队列嘛：
搞一个循环单链表，循环队列长度为4，所以开4个结点。
看起来好像还挺合适的。
那现在结点上来直接就开好了，如何判空或者判满呢？
🆗，那我们可以定义两个指针front和rear，来标识队头和队尾的位置
那front和rear都指向第一个结点（front==rear），就可以表示空。
那插入数据怎么做呢？
🆗，队尾入数据那对应我们这里的链表来说就是尾插嘛，所以，给rear指向的结点赋要插入的值，然后rear往后走指向下一个结点
所以rear就是指向最后一个元素的下一个，空队列的时候指向第一个结点。
那我们继续插入
此时我们发现一个问题，插入满了之后，rear就重新回到了第一个结点，此时front和rear又指向了同一个结点（front==rear）。
那我们发现判空和判满的条件都是（front==rear）
那这样就分辨不开了，怎么办？
那这里解决方式呢不止一种：
比如你可以增加一个size记录有效数据的个数，用size==k来判满。
但是我们这里不采用这种方法，我们还可以这样做：
多开一个结点（开k+1个），就可以解决这个问题
多开一个结点，判空呢还是front==rear，而判满则用rear->next==front
而且，这个多开的结点也可以存储数据，在后续的操作中，这个空余结点可能是任意一个结点。
我们继续往下看
此时满了，不能再入数据了，那如何删除数据呢——队头出数据
那就是链表的头删，当然这里我们不会真的删除结点，怎么做呢？
很简单，我们让front往后走就行了（front=front->next），被“删除”的数据也不用抹掉啥的，因为后续再入数据给会他覆盖掉（我这里只是这样画）
那然后再插入呢？
那我再来pop四次删到空呢？
删到front==rear就是空了。
那走到这里我们发现这个结构好像就跑通了，用循环单链表实现好像挺棒的。
但是此时我们再来看要实现的几个接口：
我们发现构造，获取队头元素，插入，删除，判空判满这些都不难搞。
但是获取队尾元素是不是很麻烦啊。因为我们这里是一个单向循环的链表，找尾是比较麻烦的。
当然也可以解决：
可以再增加一个指针prev，记录rear的前一个，这样只要队列不为空，就可以通过prev直接获取队尾元素。
也可以解决。
链表呢我们看了这么久，刚开始感觉还不错，用循环链表刚好有这个环的感觉，非常合适，但是最后发现还是有一些缺点。
那此时呢，我们不妨来考虑一下另外一种结构——用数组实现怎么样呢？
数组结构分析
我们来分析一下，还是以K=4为例：
首先有了上面的分析经验，我们的数组也多开一个空间
但是数组的话首先看上去就不如上面的链表，因为看着根本不循环。
那如何让它实现循环呢？
那也很简单，走到结尾的时候，我们让它回绕到下标0的位置就行了。
判空判满
那数组实现的话如何判空判满呢？
判空的话很简单
还是可以以front==rear为空（在哪个位置，就等于该位置下标值）
那判满呢？
rear+1==front吗？
如果是上面这种情况呢确实是，但是：
如果是下面这样呢？
rear+1是不是就越界了啊。
那怎么办呢？那就要让它回去，给rear+1模上一个k+1（即数组的长度）
所以统一处理：如果(rear+1)%(k+1)==front，就可以同时处理两种情况的判满。
大家可以代入验证一下。
当然也可以给这种情况（rear==k）单独加一个判断，如果此时是满的，front肯定等于0，去判断front是否等于0
入数据出数据
那我们再来分析一下插入删除即队尾入数据和队头出数据：
首先入数据是不是很简单啊
给rear下标的元素赋值，然后rear++就行了
但是，需要注意：
如果是这种情况，rear==k再++（等于k+1)是不是就越界了。
那这种情况可以加一个判断if(raer==k+1)，让k=0
或者也可以用取模的方式，让它%k+1。当然如果用取模的话就不用判断，因为如果rear
那我们再来看一下队头出数据：
也很简单，正常的pop就直接让front++就行了
需要注意的也是front走到越界的时候
此时如果删了5之后，再++就越界了（front==k+1），得让他回到0
那跟上面一样，可以去模k+1，或者加个判断，把它置成0。
取队头队尾元素
那最后再来分析一下取队头和队尾元素：
先来看取队头元素，非常简单：
只要队列不为空（为空题目要求返回-1），直接返回下标front的元素就行了
那取队尾元素呢？
上面分析链表就是取队尾元素麻烦，但是数组，就很简单了：
下标rear-1的元素不就是队尾元素嘛。
当然，也需要注意一下：
怕的是这种情况，rear为0，那rear-1是-1，越界了。
但是也很好处理，还是两种方法：
可以单独加一个判断，如果rear==0，把它置成k，其余情况就是rear-1
当然可以写成这样rear==0?k:rear-1
另外一种方式就还是取模可以两种方式统一处理：
(rear-1+k+1)%(k+1) ，此时rear-1是-1嘛，越界了，加个k+1，就变成k了；
而对于其它情况也适用，其它情况rear-1肯定小于k+1，所以模一下不受影响。
简化一下即 (rear+k)%(k+1)
那综合分析一下，其实还是数组会简单一点，所以下面我们就用数组来实现。
3. 代码实现（数组结构）
画图理清思路，写代码还是很简单的：
C语言版本
typedef struct { int *arr; int front; int rear; int k; } MyCircularQueue; //front==rear就是空 bool myCircularQueueIsEmpty(MyCircularQueue* obj) { assert(obj); return obj->front==obj->rear; } //(rear+1)%(k+1))==front就是满 bool myCircularQueueIsFull(MyCircularQueue* obj) { assert(obj); return ((obj->rear+1)%(obj->k+1))==obj->front; //或 // if(obj->rear==obj->k) // return obj->front==0; // return (obj->rear+1)==obj->front; } MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* q=(MyCircularQueue*)malloc(sizeof(MyCircularQueue)); //多开一个空间，解决判满的问题 q->arr=(int*)malloc(sizeof(int)*(k+1)); q->front=q->rear=0; //开了k+1个空间，但队列实际容量为k q->k=k; return q; } bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { assert(obj); if(myCircularQueueIsFull(obj)) return false; obj->arr[obj->rear]=value; obj->rear++; //注意rear++越界的处理 // if(obj->rear==obj->k+1) // obj->rear=0; obj->rear%=(obj->k+1); return true; } bool myCircularQueueDeQueue(MyCircularQueue* obj) { assert(obj); if(myCircularQueueIsEmpty(obj)) return false; obj->front++; //注意front++越界的处理 if(obj->front==(obj->k+1)) obj->front=0; //obj->front%=(obj->k+1); return true; } int myCircularQueueFront(MyCircularQueue* obj) { assert(obj); if(myCircularQueueIsEmpty(obj)) return -1; return obj->arr[obj->front]; } int myCircularQueueRear(MyCircularQueue* obj) { assert(obj); if(myCircularQueueIsEmpty(obj)) return -1; //注意rear为0情况的理 int rear=(obj->rear==0?obj->k:obj->rear-1); return obj->arr[rear]; //return obj->arr[(obj->rear+obj->k)%(obj->k+1)]; } void myCircularQueueFree(MyCircularQueue* obj) { assert(obj); free(obj->arr); free(obj); }C++版本
class MyCircularQueue {private: vectorq; int front; int rear; int _k; public: MyCircularQueue(int k) { q.reserve(k+1); front=rear=0; _k=k; } bool enQueue(int value) { if(!isFull()) { q[rear++]=value; rear%=(_k+1); return true; } return false; } bool deQueue() { if(!isEmpty()) { front++; front%=(_k+1); return true; } return false; } int Front() { if(!isEmpty()) return q[front]; return -1; } int Rear() { if(!isEmpty()) { return q[(rear+_k)%(_k+1)]; } return -1; } bool isEmpty() { return front==rear; } bool isFull() { return (rear+1)%(_k+1)==front; } };