今天在刷学校OJ题目的时候做到了这道关于循环队列的题目，说实话这个题刚开始真的没有任何思路，实在是想不出来很好的解决办法，但是当我想起一道在LeetCode上做的一道循环队列的题目时突然对循环队列这个东西有了一点思考，但是即使是做过LeetCode的这道题也还是没能想起这个题重点思路，所以决定好好把循环队列的解题方法和关键思路重新巩固梳理一下。
题目：
学校的OJ题目已经把难度降低了很多，但是题目描述还是有一些模糊，但是这里的输入判断方式需要注意一下，入队和出队都只需要判断第一个字符就可，这题的思路不做过多的介绍，因为大致都是仿照LeetCode上面的这题，基本思路一模一样，后面会对LeetCode的题目进行思路分析。
代码：
#include<iostream>
using namespace std;
typedef struct SList
{
int* data;
int n;//空间个数，注意实际放的元素个数是n-1个
int front;
int rear;
}SL;
SL* SListCreate(int n)
{
SL* p = (SL*)malloc(sizeof(SL));
p->n = n;
p->data = (int*)malloc(sizeof(int)*n);
p->front = 0;
p->rear = 0;
return p;
}
bool IsQueueFull(SL* ps)//判断队列是否为满
{
if ((ps->rear + 1) % ps->n == ps->front)//队列为满的判断条件
return true;
else
return false;
}
bool IsQueueEmpty(SL* ps)//判断队列是否为空
{
if (ps->rear == ps->front)
return true;
else
return false;
}
void SListOperation(SL* ps)
{
char a[5] = { 0 };//用第一个字符判断是入队操作还是出队操作
cin >> a;
if (a[0] == 'i')
{
//说明要入队
int val;
cin >> val;
if (!IsQueueFull(ps))//入队前先判满
{
ps->data[ps->rear] = val;
ps->rear++;
ps->rear = (ps->rear) % (ps->n);//防止越界
}
}
else if(a[0] == 'o')
{
//说明要出队
if (!IsQueueEmpty(ps))//入队前先判空
{
ps->front++;
ps->front = (ps->front) % (ps->n);//防止越界
}
}
}
void SListPrint(SL* ps)//剩下队列元素的打印
{
while (ps->front != ps->rear)
{
printf("%d ", ps->data[ps->front]);
ps->front++;
ps->front = (ps->front) % (ps->n);
}
}
int main()
{
int n = 0;
cin >> n;
SL* ret = SListCreate(n);
int k = 0;
cin >> k;
while (k)
{
SListOperation(ret);
k--;
}
SListPrint(ret);
return 0;
}622. 设计循环队列 - 力扣（LeetCode） (leetcode-cn.com)
https://leetcode-cn.com/problems/design-circular-queue/
用数组的方式实现循环队列：
先来看一看用数组实现循环队列的代码，下面的代码注释比较少，如果代码不好理解，下面的图解思路一定可以解开你的疑惑！
typedef struct
{
int* a;
int k;//队列长度为k
int front;//头的下标
int rear;//尾的下标
} MyCircularQueue;
bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{
if(obj->front==obj->rear)
return true;
else
return false;
}
bool myCircularQueueIsFull(MyCircularQueue* obj)
{
if((obj->rear+1)%(obj->k+1)==obj->front)
return true;
else
return false;
}
MyCircularQueue* myCircularQueueCreate(int k)
{
MyCircularQueue* q=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));//先给结构体开空间
q->a=(int*)malloc(sizeof(int)*(k+1));//开k+1个数组空间
q->front=q->rear=0;//给front和rear赋初值0
q->k=k;
return q;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{
if(myCircularQueueIsFull(obj))
{
return false;
}
else
{
obj->a[obj->rear]=value;
obj->rear++;
obj->rear=obj->rear%(obj->k+1);//防止tail越界
return true;
}
}
bool myCircularQueueDeQueue(MyCircularQueue* obj)
{
if(myCircularQueueIsEmpty(obj))
return false;
else
{
obj->front++;
obj->front=obj->front%(obj->k+1);
return true;
}
}
int myCircularQueueFront(MyCircularQueue* obj)
{
//这一步非常容易忽略，但是题干中也有明确地提示到
if(myCircularQueueIsEmpty(obj))
return -1;
else
{
return obj->a[obj->front];
}
}
int myCircularQueueRear(MyCircularQueue* obj)
{
if(myCircularQueueIsEmpty(obj))
return -1;
else
{
//return obj->a[obj->rear-1];//第一直觉的写法，思考这里有什么问题
int i=(obj->rear+obj->k)%(obj->k+1);
return obj->a[i];
}
}
void myCircularQueueFree(MyCircularQueue* obj)
{
free(obj->a);//应当先将a这块开辟的空间free掉，也很容易忽略
free(obj);//再free掉这个结构体空间
}思路：当我们刚开始拿到这个题的时候，如果对循环队列没有概念的情况下，第一反应大家都一定会去想，需要存放k个数据，我们应该怎么去开辟内存空间呢？我在思考这个题目的时候，也真的是没能想到去开辟k+1个空间的办法，那么知道这个开辟办法过后，我们应当去思考这样设计的目的是什么？为什么设计k个空间行不通呢？
·第一步，也就是我们需要首先正确并且合理地去创建一个结构体，保证在建立这个结构体里面包含的一些内容在每个函数接口都各有各的作用，并且不可或缺，十分重要！下面就来看一看我的这个设计思路：
typedef struct
{
int* a;
int k;//队列长度为k
int front;//头的下标
int rear;//尾的下标
} MyCircularQueue;因为是创建一个数组实现的循环队列，那么首先，我们需要创建一个front位置的下标，用于记录出队列的那个下标，需要用上一个rear位置的下标，用于记录每一次入队列的位置坐标，最后呢这个队列长度k呢，因为题目中只有myCircularQueueCreate这个接口提供了k的值，但是我们后面还需要使用这个k值，那么我们将k存入这个结构体中，以后每一次使用直接从结构体去取即可。
·第二步
结构体建立好了我们就需要思考队列的创建问题了。
MyCircularQueue* myCircularQueueCreate(int k)
{
MyCircularQueue* q=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));//先给结构体开空间
q->a=(int*)malloc(sizeof(int)*(k+1));//开k+1个数组空间
q->front=q->rear=0;//给front和rear赋初值0
q->k=k;
return q;
}上面这段代码中，先给结构体开辟空间，front和rear赋初值都给0，然后k赋值给结构体中的k。以上三个步骤不容易出错。但是这个数组却开辟了k+1个空间？这是为何呢？接下来画图说明一下：
上面的思路证明了如果我们开辟k个空间来存放k个数据设计循环队列明显是行不通的，那么我们就要换个思路。大家可以联系以下生活实际，比如说，队列在什么时候起到关键作用，他的意义是什么。两个关键词：判断队列是否为空！判断队列是否为满? ? ? ? ? ? ? ? ? ?
为了可以实现判空和判满，我们需要设计一个新的开辟空间的思路，下面通过一封图来理解一下：
通过上图可以看出需要判空和判满我们则需要开辟k+1个空间来实现循环队列，那么我们再来举一个具体的实例看看：
?通过上面的实例就可以完成对判空判满两个接口函数的实现：
bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{
if(obj->front==obj->rear)
return true;
else
return false;
}
bool myCircularQueueIsFull(MyCircularQueue* obj)
{
if((obj->rear+1)%(obj->k+1)==obj->front)
return true;
else
return false;
}·第三步：实现完判空和判满接下来我们就需要来写一写入队和出队的接口了。
依旧通过具体的例子来看看：
?
通过上面图解的分析，我们就可以完成入队和出队接口函数的代码：
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{
if(myCircularQueueIsFull(obj))
{
return false;
}
else
{
obj->a[obj->rear]=value;
obj->rear++;
obj->rear=obj->rear%(obj->k+1);//防止tail越界
return true;
}
}
bool myCircularQueueDeQueue(MyCircularQueue* obj)
{
if(myCircularQueueIsEmpty(obj))
return false;
else
{
obj->front++;
obj->front=obj->front%(obj->k+1);
return true;
}
}·第四步：完成了入队出队操作后，我们接下来看看如何去找到队首的元素和队尾的元素，注意这里有一个这题非常容易出错的点！
?接下来就可以完成我们队首元素和队尾两个元素的接口函数代码：
int myCircularQueueFront(MyCircularQueue* obj)
{
//这一步非常容易忽略，但是题干中也有明确地提示到
if(myCircularQueueIsEmpty(obj))
return -1;
else
{
return obj->a[obj->front];
}
}
int myCircularQueueRear(MyCircularQueue* obj)
{
if(myCircularQueueIsEmpty(obj))
return -1;
else
{
//return obj->a[obj->rear-1];//第一直觉的写法，思考这里有什么问题
int i=(obj->rear+obj->k)%(obj->k+1);
return obj->a[i];
}
}·第五步：最后还需要写一个释放空间的代码：
这里也需要注意一下！
释放空间的时候，应当首先去释放开辟的数组空间，再去释放结构体！
这里的先后顺序不能搞反了！
因为一旦先释放掉结构体后，就没法去找到开辟的数组了，所以要记得先释放malloc开辟的数组，然后再释放结构体！
void myCircularQueueFree(MyCircularQueue* obj) { free(obj->a);//应当先将a这块开辟的空间free掉，也很容易忽略 free(obj);//再free掉这个结构体空间 }
用链表的方式实现循环队列：
首先还是先来看看代码：
typedef struct SList
{
int data;
struct SList* next;
}SL;
typedef struct
{
int k;
SL* front;
SL* rear;
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k)
{
MyCircularQueue* q=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
SL* cur=(SL*)malloc(sizeof(SL));
q->k=k;
q->front=cur;
q->rear=cur;
while(k)
{
SL* newnode=(SL*)malloc(sizeof(SL));//开辟一个新节点
cur->next=newnode;
cur=newnode;
cur->next=q->front;
k--;
}//在入队出队之前首先要把空间所有的节点都开辟好，只是不存放有效数据而已
return q;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{
if(obj->front==obj->rear)
return true;
else
return false;
}
bool myCircularQueueIsFull(MyCircularQueue* obj)
{
if(obj->rear->next==obj->front)
return true;
else
return false;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{
if(myCircularQueueIsFull(obj))
return false;
else
{
obj->rear->data=value;
obj->rear=obj->rear->next;
return true;
}
}
bool myCircularQueueDeQueue(MyCircularQueue* obj)
{
if(myCircularQueueIsEmpty(obj))
return false;
else
{
obj->front=obj->front->next;
return true;
}
}
int myCircularQueueFront(MyCircularQueue* obj)
{
if(myCircularQueueIsEmpty(obj))
return -1;
else
return obj->front->data;
}
int myCircularQueueRear(MyCircularQueue* obj)
{
if(myCircularQueueIsEmpty(obj))
return -1;
else
{
SL* prev=obj->front;
while(prev->next!=obj->rear)
{
prev=prev->next;
}
return prev->data;
}
}
void myCircularQueueFree(MyCircularQueue* obj)
{
while(obj->front!=obj->rear)
{
SL* cur=obj->front->next;
free(obj->front);
obj->front=cur;
}
free(obj->front);
free(obj);
}
?
上面分别用数组的方式和链表的方式实现了循环队列的问题，个人认为用链表的方式实现逻辑上更为简单一些，不过在结构体的创建上和空间的开辟方面相对复杂一些。数组的方式在逻辑分析上稍微会多绕一些弯，不过结构体建立空间开辟还算比较简单。两种方法在时空上各有千秋。
最后看完循环队列的两道OJ题后，就在想为什么会有大佬弄出循环队列这个东西，比较好奇其中的原理和设计者的设计目的，所以去查阅了一下相关的大神博客关于循环队列的文章。
循环队列是队列的一种顺序存储结构。循环队列的引入，目的是为了克服假溢出时大量移动数据元素 。?
循环队列的优点是相对于直线队列来讲的，直线队列在元素出队后，头指针向后移动，导致删除元素后的空间无法在利用，即使元素个数小于空间大小，依然无法再进行插入，即所谓的“假上溢”。 当变成循环队列之后，删除元素后的空间仍然可以利用，最大限度的利用空间。
1、循环队列的优点：
可以有效的利用资源。用数组实现队列时，如果不移动，随着数据的不断读写，会出现假满队列的情况。即尾数组已满但头数组还是空的；循环队列也是一种数组，只是它在逻辑上把数组的头和尾相连，形成循环队列，当数组尾满的时候，要判断数组头是否为空，不为空继续存放数据。
2、循环队列的缺点：
循环队列中，由于入队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针，造成队空和队满时头尾指针均相等。因此，无法通过条件front==rear来判别队列是"空"是"满"。
3、拓展知识：
为充分利用向量空间，克服"假溢出"现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列。
