循环队列（C语言版）

循环队列(C语言版）

1.简单介绍循环队列
2.使用何种结构来实现
3.基本结构
4.初始化
5.判空判满
6.向循环队列插入一个元素
7.从循环队列中删除一个元素
8.获取队头队尾元素
9.释放空间
10.完整代码

🌟🌟hello，各位读者大大们你们好呀🌟🌟
🚀🚀系列专栏：【C++的学习】
📝📝本篇内容：简单介绍循环队列；使用何种结构来实现；基本结构；初始化；判空判满；向循环队列插入一个元素；从循环队列中删除一个元素；获取队头队尾元素；释放空间；完整代码
⬆⬆⬆⬆上一篇：C++priority_queue模拟实现
💖💖作者简介：轩情吖，请多多指教(> •̀֊•́ ) ̖́-

1.简单介绍循环队列

循环队列本质上是也是一个队列，也是“先进先出”的特性，只不过循环队列有空间限制，而不是可以无限添加元素，同时从逻辑上看，它是一个首尾相连的一个环形。
在leetcode上有一道题，也是实现循环队列的，可以看一下☞设计循环队列

2.使用何种结构来实现

对于实现循环队列，有两种选择，一种是使用顺序表，一种是使用链表，但是哪种更好呢？

我们先来看一下leetcode上要求写的函数，需要实现判空判满还有获取队尾数据等，首先谈谈判空判满，见下图：
可以发现，当循环队列满或者空时，front和rear都指向同一个结点，这样我们就难以区分，因此需要增加一个节点，因为它是循环的，这个节点在front，rear的调整的过程中也会存储上数据，但是下图中是不存储数据的，因为整个链表中必须有一个空的节点来保证能够区分空和满

但是链表能否完成获取队尾的数据，我们的链表是单循环链表，无法找到前置节点，所以说对于链表实现循环队列会比较麻烦，不过也可以使用双向循环链表来实现。
我们这边还是主要考虑使用顺序表来实现，front和rear都是下标，顺序表简单来讲只需要通过rear-1即可获取到我们的队尾元素。
顺序表的判满和判空和链表一样，需要多开一个空间，其实也可以增加一个size来判断满和空

3.基本结构

typedef struct {int* arr;//指向开辟的空间int k;//有效空间个数int front;//队头int rear;//队尾} MyCircularQueue;

我们直接在leetcode上完成循环队列的实现
按照我们之间画的图以及理解的，我们先需要声明一个结构体来预想一个循环队列

4.初始化

MyCircularQueue* myCircularQueueCreate(int k) 
{MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));//先在堆上创建一个结构体变量obj->arr=(int*)malloc(sizeof(int)*(k+1));//顺序表的开辟；k+1是为了能多一个空间来区别空和满obj->k=k;obj->front=obj->rear=0;//队头和队尾一开始都指向顺序表的头，此时为空return obj;
}

5.判空判满

bool myCircularQueueIsEmpty(MyCircularQueue* obj) 
{if(obj->front==obj->rear)//只要队头队尾指向同一个位置，那么循环队列就为空{return true;}return false;
}bool myCircularQueueIsFull(MyCircularQueue* obj) 
{//rear的下一个位置是front那么就为满，k+1是因为k是有效空间个数，但是空间是多一个的if((obj->rear+1)%(obj->k+1)==obj->front){return true;}return false;
}

对于叛空没什么问题，但是大家可能对判满有一个疑问，为什么需要%？

如果不进行%的话，rear+1就直接超出了我们的循环队列，rear+1是6，k+1是6，进行%，正好和front相等。并且在rear+1在小于6的情况下（不超过循环队列时），并不会受%的影响

6.向循环队列插入一个元素

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value){if(myCircularQueueIsFull(obj)){//满了就不能放元素了return false;}obj->arr[obj->rear++]=value;//直接在rear位置放入元素，同时位置向后+1obj->rear%=(obj->k+1);//保证不会越界，如果超过的最后一个位置，就需要回到第一个位置return true;
}

rear始终指向有效元素的下一个位置，每次直接插入即可，不过插入完后要对rear进行++

在不停地插入和删除中，rear和front都会发生改变，因此对于rear我们也要对它进行调整，保证它不会越界，一旦指向越界，回到开头。

7.从循环队列中删除一个元素

bool myCircularQueueDeQueue(MyCircularQueue* obj)
{if(myCircularQueueIsEmpty(obj)){//循环队列为空就无法删除return false;}obj->front++;//直接队头位置+1即可obj->front%=(obj->k+1);//保证不会越界return true;
}

和前面插入元素一样，要保证front不能越界

8.获取队头队尾元素

int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){//保证不为空return -1;}else{return obj->arr[obj->front];}
}int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){//保证不为空return -1;}else{return obj->arr[(obj->rear+obj->k)%(obj->k+1)];//这里还需要%k+1是为了保证在其他情况下（rear不为0时）也能正常使用}
}

获取队头元素没什么好说的，主要是获取队尾元素，因为rear是指向最后一个元素的下一个位置，当rear为0时就不能直接rear-1来获取

上图分析了如何找到原位置，但是还要注意这只是一种情况，还有其他比较正常的情况也要适用，因此代码中需要%（k+1）

如果觉得使用%太复杂，也可以使用下面的方式

int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){//保证不为空return -1;}else{
//return obj->arr[(obj->rear+obj->k)%(obj->k+1)];//这里还需要%k+1是为了保证在其他情况下（rear不为0时）也能正常使用return obj->arr[obj->rear==0?obj->k:obj->rear-1];}
}

obj->k是有效空间的个数，它作为下标正好指向最后一个空间；rear正常情况下只需要-1即可访问队尾元素

9.释放空间

void myCircularQueueFree(MyCircularQueue* obj) 
{free(obj->arr);free(obj);
}

10.完整代码

这部分完整代码是leetcode答题区的，而不是能直接放在编译器中直接运行的

typedef struct {int* arr;//指向开辟的空间int k;//有效空间个数int front;//队头int rear;//队尾} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));//先在堆上创建一个结构体变量obj->arr=(int*)malloc(sizeof(int)*(k+1));//顺序表的开辟；k+1是为了能多一个空间来区别空和满obj->k=k;obj->front=obj->rear=0;//队头和队尾一开始都指向顺序表的头，此时为空return obj;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {if(obj->front==obj->rear)//只要队头队尾指向同一个位置，那么循环队列就为空{return true;}return false;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {//rear的下一个位置是front那么就为满，k+1是因为k是有效空间个数，但是空间是多一个的if((obj->rear+1)%(obj->k+1)==obj->front){return true;}return false;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj)){//满了就不能放元素了return false;}obj->arr[obj->rear++]=value;//直接在rear位置放入元素，同时位置向后+1obj->rear%=(obj->k+1);//保证不会越界，如果超过的最后一个位置，就需要回到第一个位置return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){//循环队列为空就无法删除return false;}obj->front++;//直接队头位置+1即可obj->front%=(obj->k+1);//保证不会越界return true;
}int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){//保证不为空return -1;}else{return obj->arr[obj->front];}
}int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){//保证不为空return -1;}else{
//return obj->arr[(obj->rear+obj->k)%(obj->k+1)];//这里还需要%k+1是为了保证在其他情况下（rear不为0时）也能正常使用return obj->arr[obj->rear==0?obj->k:obj->rear-1];}
}void myCircularQueueFree(MyCircularQueue* obj) {free(obj->arr);free(obj);
}/*** Your MyCircularQueue struct will be instantiated and called as such:* MyCircularQueue* obj = myCircularQueueCreate(k);* bool param_1 = myCircularQueueEnQueue(obj, value);* bool param_2 = myCircularQueueDeQueue(obj);* int param_3 = myCircularQueueFront(obj);* int param_4 = myCircularQueueRear(obj);* bool param_5 = myCircularQueueIsEmpty(obj);* bool param_6 = myCircularQueueIsFull(obj);* myCircularQueueFree(obj);
*/