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

LeetCode刷题记录

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

🚀LeetCode622.设计循环队列

链接：LeetCode622.设计循环队列

一、🌟题目描述🌟

二、🎨分析🎨

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

链表实现分析

如下图：
刚开始head和tail都指向一个头！

这种结构下

• 插入数据只需要把数据放到tail节点，然后tail向后走
  如图：push 1 2 3
  
• pop数据 只需要让head走向下一个，数据清除或者不清楚无所谓，反正可以被替换，
  如图：pop pop
  
  注意节点不需要释放！
  而如果继续插入数据：push 4 5 6 7
  
  可以看到此时已经满了！
  但是，大家看一下我们设计的这个有没有什么缺陷呢？
  ！对！ 我们可以看到！队列什么时候满呢？
  head==tail的时候满
  那么什么时候为空呢？
  head==tail的时候为空！
  所以！ 这里判断空和满是有问题的！

那么解决方法是什么呢？

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

如图：push 4 5 6 7
只能插入4 5 6 到7的时候 tail->next==head 所以已经满了，无法插入！

通常来说 结构就是这样的：

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

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

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

所以我们选择用数组实现

三、💥题解💥

我们利用数组实现
先简单分析一下：

对于一个数组，我们要实现循环队列，那么

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

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

我们采取对数组多开辟一个空间的方法：开辟(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是不是等于headreturn obj->head==obj->tail;}

判断是不是满了

这里是稍微有点麻烦的

首先我们要知道，判断满的条件是tail的下一个等于head
但是这是数组 ！not 链表
如果是环形链表，他会自动实现很自然的循环
但是链表不一样
链表会走到一个边界，所以我们需要考虑tail的下一个是谁？
我们定义一个next来标识下一个
一般的tail的下一个就是tail+1 ，如下图

但是存在特殊情况：如果tail已经是最后一个位置了，那么这时候其实他的下一个就是返回开头0

找到下一个？
1.  定义一个next=tail+1如果tail==k+1那么next就为02.  利用取模我们知道一共有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;elsereturn false;
}

获取队头元素

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

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

int myCircularQueueFront(MyCircularQueue* obj) {//如果队列为空 返回-1if(myCircularQueueIsEmpty(obj)){return -1;}//队头就是 headreturn 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已经走到末尾了！

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

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

当满的时候会push 失败！

push代码：

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {//首先判断是不是满了//如果满了 push失败--返回falseif(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
所以 解决方法依旧有两个：

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

代码：

bool myCircularQueueDeQueue(MyCircularQueue* obj) {//如果 队列已经空空了 就返回falseif(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是不是等于headreturn 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;elsereturn false;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {//首先判断是不是满了//如果满了 push失败--返回falseif(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) {//如果 队列已经空空了 就返回falseif(myCircularQueueIsEmpty(obj)){return false;}//如果队列不为空obj->head++;if(obj->head==obj->k+1){obj->head=0;}return true;
}int myCircularQueueFront(MyCircularQueue* obj) {//如果队列为空 返回-1if(myCircularQueueIsEmpty(obj)){return -1;}//队头就是 headreturn 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)

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