目录

一.前言

二.正文

1.1题目描述

1.2题目分析

（1）定义栈的结构

 （2）创建我们的队列

（3）判断队列是否为空

 （4）判断队列是否数据已满

 （5）队列数据的插入

（6） 队列数据的删除

（7） 取出队头的数据

 （8）取出队尾的数据

 （9）销毁我们创建的对列

 1.3代码实现

三.结言

---

一.前言

上一次我们分享了关于队列的基本实现——https://blog.csdn.net/yiqingaa/article/details/139033067?spm=1001.2014.3001.5502

现在我们将使用队列知识来解决问题——设计循环队列：https://leetcode.cn/problems/design-circular-queue/submissions/533299335

二.正文

1.1题目描述

​

1.2题目分析

​

本题给了我们七个操作需求，需要我们将这些函数功能实现出来。

对于这道题，假如我们是使用数组来实现队列，在这里我们可以事先模拟走一下：

​

那么我们如何解决这个问题呢。在这里我们我们可以通过多创建一个空间的方式解决这个问题。

​

（1）定义栈的结构

typedef struct { int* a;//a是int*类型的数组 int k;//k代表了我们的数组长度 int head;//head会指向我们的头元素（head在这里不是指针，可以当成另类的下标） int tail;//tail在我们数据的后一个位置（tail在这里不是指针，可以当成另类的下标）} MyCircularQueue;

假如k是4，数组有1，2，3，4这些数据。那么就有：

​

 （2）创建我们的队列

MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue)); obj->a=(int*)malloc(sizeof(int)*(k+1)); if(obj->a==NULL) { perror("malloc fail!"); } obj->k=k; obj->head=obj->tail=0; return obj;}

我们首先为我们的队列结构体申请了sizeof(MyCircularQueue)字节大小的空间。

然后又为了我们数组申请了sizeof(int)*(k+1)字节大小的空间。

用我们的结构体成员k接受形参k的值。

并让head，tail都初始化为0。

（3）判断队列是否为空

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

这里我们先实现了判断队列是否为空的函数功能，因为这个函数功能在后面实现数据插入和删除中都需要用到，因此，在这里我们就先实现了。

 （4）判断队列是否数据已满

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

 （5）队列数据的插入

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

这里我们先进行了判断，如果队列数据已经满了，就插不了数据了，直接返回false即可。

在这里，我们需要额外注意这行代码：obj->tail=(obj->tail)%(obj->k+1);

相信同学们看到这里已经发现了，我们上述代码中很多都用到了取余%的应用，这是为了让head和tail能正常的循环。

（6） 队列数据的删除

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

这里我们需要知道，如果队列没有数据的时候，我们不能进行数据删除，因为本来队列都没数据了，再删除就会出现内存泄露的问题。

（7） 取出队头的数据

int myCircularQueueFront(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)==true) return -1; return obj->a[obj->head];}

 （8）取出队尾的数据

int myCircularQueueRear(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)==true) return -1; return obj->a[(obj->tail-1+obj->k+1)%(obj->k+1)];}

 （9）销毁我们创建的对列

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

 1.3代码实现

typedef struct { int* a; int k; int head; int tail;} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue)); obj->a=(int*)malloc(sizeof(int)*(k+1)); if(obj->a==NULL) { perror("malloc fail!"); } obj->k=k; obj->head=obj->tail=0; return obj;}bool myCircularQueueIsEmpty(MyCircularQueue* obj) { if(obj->head==obj->tail) return true; return false;}bool myCircularQueueIsFull(MyCircularQueue* obj) { if((obj->tail+1)%(obj->k+1)==obj->head) return true; return false;}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if(myCircularQueueIsFull(obj)==true) return false;obj->a[obj->tail]=value;obj->tail++;obj->tail=(obj->tail)%(obj->k+1);return true;}bool myCircularQueueDeQueue(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)==true) return false; obj->head++; obj->head=(obj->head)%(obj->k+1); return true;}int myCircularQueueFront(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)==true) return -1; return obj->a[obj->head];}int myCircularQueueRear(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)==true) return -1; return obj->a[(obj->tail-1+obj->k+1)%(obj->k+1)];}void myCircularQueueFree(MyCircularQueue* obj) { free(obj->a); 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);*/

以上代码就是我们在力扣网上运行的代码。

三.结言

本题的分享就到这了，有兴趣的小伙伴，能不能给个三连，真的求求了。

帅哥美女们，咱们下期再见。