C语言/数据结构——每日一题（设计循环队列）

目录

一.前言

二.正文

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);*/

---

三.结言

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

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