【初阶数据结构】——循环队列
这篇文章我们来学习一下如何实现循环队列 那力扣上呢有一个对应的题我们可以来看一下：
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<k+1，%k+1之后值是不会变的。
那我们再来看一下队头出数据：
也很简单，正常的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:
vector<int> q;
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;
}
};