【LeetCode刷题之路】622.设计循环队列

在这里插入图片描述

LeetCode刷题记录

🌐 我的博客主页：iiiiiankor
🎯 如果你觉得我的内容对你有帮助，不妨点个赞👍、留个评论✍，或者收藏⭐，让我们一起进步！
📝 专栏系列：LeetCode 刷题日志
🌱 文章内容来自我的学习与实践经验，如果你有任何想法或问题，欢迎随时在评论区交流讨论。让我们一起探索更多的可能！🚀

文章目录

🚀LeetCode622.设计循环队列
- 一、🌟题目描述🌟
- 二、🎨分析🎨
- - 链表实现分析
- 三、💥题解💥
- - 定义队列结构
  - Create(创建队列）
  - 判断是否为空
  - 判断是不是满了
  - 获取队头元素
  - 获取队尾元素
  - push接口
  - pop接口
  - 销毁
  - ✏️总代码✏️
💥💥最后贴一个题 💥💥

🚀LeetCode622.设计循环队列

链接：LeetCode622.设计循环队列

一、🌟题目描述🌟

在这里插入图片描述

二、🎨分析🎨

题目理解：
这是让我们实现的是一个大小固定的循环队列
正常的大小固定的队列如果满了就不能插入了
而这里所说的循环队列是队尾和队头连在一起的
所以我们首先想到的就是利用链表实现循环队列

链表实现分析

如下图：
刚开始head和tail都指向一个头！
在这里插入图片描述
这种结构下

插入数据只需要把数据放到tail节点，然后tail向后走
如图：push 1 2 3
pop数据只需要让head走向下一个，数据清除或者不清楚无所谓，反正可以被替换，
如图：pop pop

注意节点不需要释放！
而如果继续插入数据：push 4 5 6 7

可以看到此时已经满了！
但是，大家看一下我们设计的这个有没有什么缺陷呢？
！对！我们可以看到！队列什么时候满呢？
head==tail的时候满
那么什么时候为空呢？
head==tail的时候为空！
所以！这里判断空和满是有问题的！

那么解决方法是什么呢？

给一个size记录队列的大小，循环队列的节点数为k，每一次push的时候size++，pop时size–当head==tail 时，如果size为k说明已经满了，如果size为0 则说明为空
给一个flag 刚开始flag为0表示队列为空，如果head==tail了 flag置为1，表示已经满了，当再pop的时候，就把flag改成0表示未满
比较官方的做法：
我们直接开辟k+1个链表节点，其中有一个节点不存储有效数据
判满的条件就是 tail的下一个为head

如图：push 4 5 6 7
只能插入4 5 6 到7的时候 tail->next==head 所以已经满了，无法插入！
在这里插入图片描述
通常来说结构就是这样的：

但是这时候这个队列还有别的问题吗？
我们要实现 push pop 判空判满获取队头数据获取队尾数据等等…
我们可以发现，如果想要获取队尾数据是比较麻烦的！！
因为我们的tail是下一个要push的位置而不是真正的队尾
所以我们如果想要解决，必须找到tail的前一个

方法1：双向链表
方法2：记录尾的同时还要记录尾的前一个

显然都是麻烦事！所以利用链表是不方便实现的

所以我们选择用数组实现

三、💥题解💥

我们利用数组实现
先简单分析一下：
在这里插入图片描述
对于一个数组，我们要实现循环队列，那么

因为队列是循环的，所以什么时候队列是满的呢？
这就和我们链表部分分析的一样了，有三种方法！

flag标识
size记录队列大小
多开辟一个空间 ✅

我们采取对数组多开辟一个空间的方法：开辟(k+1)个空间

下面是具体接口实现：
✨代码中都有详细注释哦！！✨

定义队列结构

typedef struct {
    int* a;//动态开辟数组
    int head;//队头
    int tail;//队尾
    int k;//队的大小,因为后面传参的时候不会再传 k 所以我们定义在结构体里面
} MyCircularQueue;

Create(创建队列）

我们以k=5为例

	首先创建一个队列结构
	然后开辟出队列中大小为`k+1`的数组
	然后把结构中的head和tail初始化为0

如图：
在这里插入图片描述

判断是否为空

前面我们对链表实现的分析的时候
我们已经分析过了
当`head`==`tail`的时候，为空
只是这里的`head`和`tail`变成了下标而不是节点

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    //判断是不是为空 只需要判断tail是不是等于head

    return obj->head==obj->tail;
    
}

判断是不是满了

这里是稍微有点麻烦的

首先我们要知道，判断满的条件是tail的下一个等于head
但是这是数组！not 链表
如果是环形链表，他会自动实现很自然的循环
但是链表不一样
链表会走到一个边界，所以我们需要考虑tail的下一个是谁？
我们定义一个next来标识下一个
一般的tail的下一个就是tail+1 ，如下图
在这里插入图片描述
但是存在特殊情况：如果tail已经是最后一个位置了，那么这时候其实他的下一个就是返回开头0

找到下一个？
1.  定义一个next=tail+1
	如果tail==k+1
	那么next就为0
	
2.  利用取模
	我们知道
	一共有k+1个空间
	所以下标的返回时 0~ k
	这时候 next=(tail+1)%(k+1)
	不管next是不是超过了数组的返回，结果都是正确的

代码：

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    //判断是不是满了
    //一般是判断tail的下一个是不是 head
    //需要考虑tail的下一个是什么？
    int next=obj->tail+1;
    if(next==obj->k+1)
    {
        next=0;
    }
    //next=(obj->tail+1)%(k+1);
    if(next==obj->head)
        return true;
    else
        return false;
}

获取队头元素

队头其实就是`head`
所以只需要访问数组中的`head`位置处的元素就可以了

但是需要注意：如果队列为空，返回-1

int myCircularQueueFront(MyCircularQueue* obj) {
    //如果队列为空 返回-1
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }

    //队头就是 head
    return obj->a[obj->head];
}

获取队尾元素

在这里插入图片描述
我们可以看到tail表示的是下一个Push的位置
而如果我们想获得队尾元素
应该是获得tail的前一个元素

所以我们定义一个prev来找到tail的前一个元素

但是也会有特殊情况

在这里插入图片描述
如果是这种情况，也就是 tail已经折回去了
tail为0 prev应该为5
怎么找到prev呢？
注意如果我们让tail+k+1 ，tail就变成了6
这时候tail-1是不是就等于prev了?
tail为0实际上就说明了tail已经走到数组最后一个位置的后一个了

细细剖析理解一下这里：

而我们再看正确的情况是不是满足呢？

显然满足的！

这样 我们就有两种情况控制边界情况
1. if判断
2. 利用取模
具体看个人喜欢用那种，小编这里就用第一种啦（比较直观）

int myCircularQueueRear(MyCircularQueue* obj) {
    //首先判断是否为空
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    //如果不为空
    //找到tail的前一个
    int prev=obj->tail-1;
    if(obj->tail==0)
        prev=obj->k;
    return obj->a[prev];
}

push接口

我们开始以k=5为例，即开辟了一个大小为6的数组

在这里插入图片描述

正常情况下，我们push只需要把tail位置放入元素，然后tail++就可以了
（向后走一步）
如图我们把一个空的队列 push 1 2 3 4
操作过程：在这里插入图片描述

在这里插入图片描述

但是会存在特殊情况
如图：在这里插入图片描述

这时候怎么push呢？tail已经走到末尾了！

直接控制：正常走的话tail+1，tail就变成了6
所以如果tail==k+1 那么我们让tail=0就可以了！
利用取模
因为数组的总空间就是k+1
所以如果我们tail等于6了，说明tail应该走到0
所以让tail%=（k+1），也就是 6%6==0

还有一个问题就是
什么时候push失败呢？

当满的时候会push 失败！

在这里插入图片描述
push代码：

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    //首先判断是不是满了
    //如果满了 push失败--返回false
    if(myCircularQueueIsFull(obj))
    {
        return false;
    }

    //如果不满 直接插入就可以了
    obj->a[obj->tail]=value;
    //然后tail需要移动！
    obj->tail++;
    //如果移动之后tail走到末尾了 tail返回到数组的最开始
    if(obj->tail==obj->k+1)
    {
        obj->tail=0;
    }

    return true;
}

pop接口

我们来看一个例子
在这里插入图片描述
如果操作为 pop pop
那么 head就需要往前走两步，从而实现删除的效果

但是如果继续pop
操作： pop pop

可以看到，此时队列已经空了！
此时继续pop就返回false（失败）

正常情况下pop只需要让head向后走，就可以了
因为前面的数据可以随意被覆盖就相当于被删了

但是也会有特殊情况，即当head走到边界
在这里插入图片描述
此时如果继续pop head++就变成了6
但是head应该返回到数组的头部0
所以解决方法依旧有两个：

如果head==k+1
那么 head变成0
取模：如果head++之后变成6
那么head=head%（k+1）

代码：

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    //如果 队列已经空空了 就返回false
    if(myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    //如果队列不为空
    obj->head++;
    if(obj->head==obj->k+1)
    {
        obj->head=0;
    }
    return true;
}

销毁

销毁就很简单了
只需要把结构销毁就可以了

注意：销毁结构之前，需要把结构中malloc的动态数组释放
否则容易造成内存泄漏！！

void myCircularQueueFree(MyCircularQueue* obj) {
    //首先释放数组空间
    free(obj->a);
    //然后释放队列
    free(obj);
}

总结：这道题还是比较麻烦的！
很多细节：比如边界需要我们考虑全面！
下面是总代码供参考！

✏️总代码✏️

//使用数组实现

typedef struct {
    int* a;//动态开辟数组
    int head;//队头
    int tail;//队尾
    int k;//队的大小,因为后面传参的时候不会再传k 所以我们定义在结构体里面
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->a=(int*)malloc(sizeof(int)*(k+1));
    obj->k=k;
    obj->head=obj->tail=0;

    return obj;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    //判断是不是为空 只需要判断tail是不是等于head

    return obj->head==obj->tail;
    
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    //判断是不是满了
    //一般是判断tail的下一个是不是 head
    //需要考虑tail的下一个是什么？
    int next=obj->tail+1;
    if(next==obj->k+1)
    {
        next=0;
    }
    //next=(obj->tail+1)%(k+1);
    if(next==obj->head)
        return true;
    else
        return false;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    //首先判断是不是满了
    //如果满了 push失败--返回false
    if(myCircularQueueIsFull(obj))
    {
        return false;
    }

    //如果不满 直接插入就可以了
    obj->a[obj->tail]=value;
    //然后tail需要移动！
    obj->tail++;
    //如果移动之后tail走到末尾了 tail返回到数组的最开始
    if(obj->tail==obj->k+1)
    {
        obj->tail=0;
    }

    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    //如果 队列已经空空了 就返回false
    if(myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    //如果队列不为空
    obj->head++;
    if(obj->head==obj->k+1)
    {
        obj->head=0;
    }
    return true;
}

int myCircularQueueFront(MyCircularQueue* obj) {
    //如果队列为空 返回-1
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }

    //队头就是 head
    return obj->a[obj->head];
}

int myCircularQueueRear(MyCircularQueue* obj) {
    //首先判断是否为空
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    //如果不为空
    //找到tail的前一个
    int prev=obj->tail-1;
    if(obj->tail==0)
        prev=obj->k;
    return obj->a[prev];
}



void myCircularQueueFree(MyCircularQueue* obj) {
    //首先释放数组空间
    free(obj->a);
    //然后释放队列
    free(obj);
}

💥💥最后贴一个题 💥💥

这个题适合 LeetCode622.循环队列中的边界问题相关的
看一下你学废了吗

5.现有一循环队列，其队头指针为front，队尾指针为rear；循环队列长度为N。
其队内有效长度为？(假设队头不存放数据)
A (rear - front + N) % N + 1
B (rear - front + N) % N
C ear - front) % (N + 1)
D (rear - front + N) % (N - 1)

✨感谢阅读~ ✨
❤️码字不易，给个赞吧~❤️

在这里插入图片描述