重庆选科网站,深圳外贸soho网站建设,常州做网站的,宁安网站建设LeetCode刷题记录 #x1f310; 我的博客主页#xff1a;iiiiiankor#x1f3af; 如果你觉得我的内容对你有帮助#xff0c;不妨点个赞#x1f44d;、留个评论✍#xff0c;或者收藏⭐#xff0c;让我们一起进步#xff01;#x1f4dd; 专栏系列#xff1a;LeetCode…
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 可以看到此时已经满了 但是大家看一下我们设计的这个有没有什么缺陷呢 对 我们可以看到队列什么时候满呢 headtail的时候满 那么什么时候为空呢 headtail的时候为空 所以 这里判断空和满是有问题的
那么解决方法是什么呢
给一个size记录队列的大小循环队列的节点数为k每一次push的时候sizepop时size–当headtail 时如果size为k说明已经满了如果size为0 则说明为空给一个flag 刚开始flag为0表示队列为空如果headtail了 flag置为1表示已经满了当再pop的时候就把flag改成0表示未满比较官方的做法 我们直接开辟k1个链表节点其中有一个节点不存储有效数据 判满的条件就是 tail的下一个为head
如图push 4 5 6 7 只能插入4 5 6 到7的时候 tail-nexthead 所以已经满了无法插入 通常来说 结构就是这样的
但是这时候这个队列还有别的问题吗 我们要实现 push pop 判空 判满 获取队头数据 获取队尾数据 等等… 我们可以发现如果想要获取队尾数据 是比较麻烦的 因为我们的tail是下一个要push的位置而不是真正的队尾 所以 我们如果想要解决必须找到tail的前一个
方法1 双向链表方法2记录尾的同时还要记录尾的前一个
显然 都是麻烦事 所以利用链表是不方便实现的
所以我们选择用数组实现
三、题解
我们利用数组实现 先简单分析一下 对于一个数组我们要实现循环队列那么 因为队列是循环的所以什么时候队列是满的呢 这就和我们链表部分分析的一样了有三种方法
flag标识size记录队列大小多开辟一个空间 ✅
我们采取对数组多开辟一个空间的方法开辟(k1)个空间 下面是具体接口实现 ✨代码中都有详细注释哦✨
定义队列结构
typedef struct {int* a;//动态开辟数组int head;//队头int tail;//队尾int k;//队的大小,因为后面传参的时候不会再传 k 所以我们定义在结构体里面
} MyCircularQueue;Create(创建队列
我们以k5为例 首先创建一个队列结构然后开辟出队列中大小为k1的数组然后把结构中的head和tail初始化为0如图
判断是否为空
前面我们对链表实现的分析的时候
我们已经分析过了
当headtail的时候为空
只是这里的head和tail变成了下标而不是节点bool myCircularQueueIsEmpty(MyCircularQueue* obj) {//判断是不是为空 只需要判断tail是不是等于headreturn obj-headobj-tail;}判断是不是满了
这里是稍微有点麻烦的
首先我们要知道判断满的条件是tail的下一个等于head 但是这是数组 not 链表 如果是环形链表他会自动实现很自然的循环 但是链表不一样 链表会走到一个边界所以我们需要考虑tail的下一个是谁 我们定义一个next来标识下一个 一般的tail的下一个就是tail1 如下图 但是存在特殊情况如果tail已经是最后一个位置了那么这时候其实他的下一个就是返回开头0
找到下一个
1. 定义一个nexttail1如果tailk1那么next就为02. 利用取模我们知道一共有k1个空间所以下标的返回时 0~ k这时候 next(tail1)%(k1)不管next是不是超过了数组的返回结果都是正确的
代码
bool myCircularQueueIsFull(MyCircularQueue* obj) {//判断是不是满了//一般是判断tail的下一个是不是 head//需要考虑tail的下一个是什么int nextobj-tail1;if(nextobj-k1){next0;}//next(obj-tail1)%(k1);if(nextobj-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呢 注意 如果我们让tailk1 tail就变成了6 这时候tail-1是不是就等于prev了? tail为0实际上就说明了tail已经走到数组最后一个位置的后一个了 细细剖析理解一下这里 而我们再看正确的情况是不是满足呢 显然 满足的 这样 我们就有两种情况控制边界情况
1. if判断
2. 利用取模
具体看个人喜欢用那种小编这里就用第一种啦比较直观int myCircularQueueRear(MyCircularQueue* obj) {//首先判断是否为空if(myCircularQueueIsEmpty(obj)){return -1;}//如果不为空//找到tail的前一个int prevobj-tail-1;if(obj-tail0)prevobj-k;return obj-a[prev];
}
push接口
我们开始以k5为例即开辟了一个大小为6的数组 正常情况下我们push只需要把tail位置放入元素然后tail就可以了 向后走一步 如图 我们把一个空的队列 push 1 2 3 4 操作过程 但是会存在特殊情况 如图
这时候怎么push呢tail已经走到末尾了
直接控制正常走的话tail1tail就变成了6 所以 如果tailk1 那么我们让tail0就可以了利用取模 因为数组的总空间就是k1 所以如果我们tail等于6了说明tail应该走到0 所以让tail%k1也就是 6%60
还有一个问题就是 什么时候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-tailobj-k1){obj-tail0;}return true;
}pop接口
我们来看一个例子 如果操作为 pop pop 那么 head就需要往前走两步从而实现删除的效果 但是如果继续pop 操作 pop pop 可以看到此时队列已经空了 此时继续pop就返回false失败
正常情况下pop只需要让head向后走就可以了 因为前面的数据可以随意被覆盖就相当于被删了
但是也会有特殊情况即当head走到边界 此时如果继续pop head就变成了6 但是head应该返回到数组的头部0 所以 解决方法依旧有两个
如果headk1 那么 head变成0取模如果head之后变成6 那么headhead%k1
代码
bool myCircularQueueDeQueue(MyCircularQueue* obj) {//如果 队列已经空空了 就返回falseif(myCircularQueueIsEmpty(obj)){return false;}//如果队列不为空obj-head;if(obj-headobj-k1){obj-head0;}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)*(k1));obj-kk;obj-headobj-tail0;return obj;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {//判断是不是为空 只需要判断tail是不是等于headreturn obj-headobj-tail;}bool myCircularQueueIsFull(MyCircularQueue* obj) {//判断是不是满了//一般是判断tail的下一个是不是 head//需要考虑tail的下一个是什么int nextobj-tail1;if(nextobj-k1){next0;}//next(obj-tail1)%(k1);if(nextobj-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-tailobj-k1){obj-tail0;}return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {//如果 队列已经空空了 就返回falseif(myCircularQueueIsEmpty(obj)){return false;}//如果队列不为空obj-head;if(obj-headobj-k1){obj-head0;}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 prevobj-tail-1;if(obj-tail0)prevobj-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)✨感谢阅读~ ✨ ❤️码字不易给个赞吧~❤️
