目录一题目二思路讲解三代码一题目解释front指向队头元素rear指向队尾元素①循环队列就是首尾相连的队列且一个元素被出队列了该位置仍在不会被释放等待下次被使用若数组实现就是下标位置还在链表实现就是节点还在只是值被清空了而已②我们采用数组实现因为若采用链表实现则起码都是单向循环链表当你删除了当前的尾节点你需要把尾指针“回退”到前一个节点。同样在单向链表中你无法直接知道前一个节点是谁又得重新遍历整个链表去找效率极低。所以至少得用双向循环链表才能保证复杂度③而采用数组下标的和--就可以随意前后访问数据循环则直接下标%上数组元素个数即可形成循环❓️而此题的难点在于既然front指向队头元素rear指向队尾元素那一开始为空的时候front和rear都指向数组的第一个位置当数组装满的时候front和rear都指向数组的最后一个位置这两种情况front rear怎么区分空还是满❌️数组对应位置无元素则设置为-1或者0当front rear时判断位置的值为-1或者0就是空反之满当然不行万一元素就是-1或者0呢所以这种把数组全部装满的设计是行不通的解决途径就是让数组随时都保持有一个空余的位置这样就能让只有空的时候front rear此外永远不会出现front rear的时候也就不存在难以分辨是空还是满的情况所以当数组只剩一个空余位置的时候则代表满了我们就不能插入了二思路讲解前提a本文采取数组来实现队列去解决题目b开辟k1个空间front指向队首rear指向队尾的后一个rear这样会更好的判空和判满以下根据pop和push感受满和空以及所有的边界的处理1初始状态解释当front rear 即空2 push 1 2 3 4解释rera指向队尾的下一个元素3在满的情况push 5解释当然不能push5进来所以我们需要用一个条件限制满的再次push那就是判满条件rear1%k1 front此公式的意义在于判断rear的下一个是否为front是则满不是则还能pushQ为什么不直接rear1 front去判满A这只适用于rear在数组非末尾位置的时候而上面的表达式均适用本质就是利用%的特性其中的k1就是数组的容量大小4pop 1 25push5 6解释rear的边界处理rear (rear1)%(k1)6在满的情况下 push 7解释这是rear在非末尾的位置的判满 rear1%k1 front同样适用7pop 3 4 5 6 得到空解释①可得只要rear和front相等就是空②front的边界处理 front front%k1最后一个边界处理取队尾数据当rear下标为0 的时候这时候取队尾rear-1 会等于-1所以需要处理有两种方式1三目操作符 rear rear0k:rear2取模rear reark%k1(04)%54这两种方法都适用与所有的取队尾总结通过这几步我们可知满和空的判断表达式 以及front和rear超过边界的处理表达式满rear1%k1 frontrear 的下一个是front就是满空front rearrear超过边界rear (rear)%(k1)front超过边界front front%k1rear下标为0取队尾rear rear0k:rear 或 rear reark%k1(04)%54边界处理就是下标取模数组空间几个公式都是大同小异的都是%上k1这个数组容量大小三代码1初始化解释定义我们需要的值a是数组front指向第一个元素rear只想最后一个元素的下一个位置k是循环队列的大小我们按照设计思路实际申请k1个空间2MyCircularQueue(k): 构造器设置队列长度为 k1解释malloc k1个整形的数组空间给a3isEmpty(): 检查循环队列是否为空解释根据我们前文的判空表达式4isFull(): 检查循环队列是否已满解释根据我们前文的判满表达式5enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。解释①先判满满了则无法插入返回false②有空间根据前文插入到下标为rear处再rear要③最后再通过rear的边界的处理的表达式处理rear6deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。解释①先判空空了则无法删除返回false②能删直接front③最后再通过front的边界的处理的表达式处理front7Front: 从队首获取元素。如果队列为空返回 -1 。解释直接返回front处的数据8Rear: 获取队尾元素。如果队列为空返回 -1 。解释通过的前文的取队尾的rear的处理表达式来取队尾1三目操作符 rear rear0k:rear2取模rear reark%k1我用的第二种方法9 销毁队列解释先free a 再free obj总代码typedef struct { int * a; int k; int front; int rear; } MyCircularQueue; MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* obj (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); obj-a (int*)malloc(sizeof(int)*(k1)); obj-front 0; obj-rear 0; obj-k k; return obj; } bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj-front obj-rear; } bool myCircularQueueIsFull(MyCircularQueue* obj) { return (obj-rear1) % (obj-k1) obj-front; } bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if(myCircularQueueIsFull(obj)) return false; obj-a[obj-rear] value; obj-rear 1; obj-rear obj-rear %(obj-k1); return true; } bool myCircularQueueDeQueue(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return false; obj-front 1; obj-front obj-front % (obj-k1); return true; } int myCircularQueueFront(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return -1; return obj-a[obj-front]; } int myCircularQueueRear(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return -1; return obj-a[obj-rear0?obj-k:obj-rear-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); */ [ 作者 ] shylyly [ 首次发布 ] 2024.7.23❌ [ 最新修改 ] 2026.5.26 [ 声明 ] 由于笔者水平有限文中难免有疏漏或不妥之处还望读者不吝赐教
622.设计循环队列
目录一题目二思路讲解三代码一题目解释front指向队头元素rear指向队尾元素①循环队列就是首尾相连的队列且一个元素被出队列了该位置仍在不会被释放等待下次被使用若数组实现就是下标位置还在链表实现就是节点还在只是值被清空了而已②我们采用数组实现因为若采用链表实现则起码都是单向循环链表当你删除了当前的尾节点你需要把尾指针“回退”到前一个节点。同样在单向链表中你无法直接知道前一个节点是谁又得重新遍历整个链表去找效率极低。所以至少得用双向循环链表才能保证复杂度③而采用数组下标的和--就可以随意前后访问数据循环则直接下标%上数组元素个数即可形成循环❓️而此题的难点在于既然front指向队头元素rear指向队尾元素那一开始为空的时候front和rear都指向数组的第一个位置当数组装满的时候front和rear都指向数组的最后一个位置这两种情况front rear怎么区分空还是满❌️数组对应位置无元素则设置为-1或者0当front rear时判断位置的值为-1或者0就是空反之满当然不行万一元素就是-1或者0呢所以这种把数组全部装满的设计是行不通的解决途径就是让数组随时都保持有一个空余的位置这样就能让只有空的时候front rear此外永远不会出现front rear的时候也就不存在难以分辨是空还是满的情况所以当数组只剩一个空余位置的时候则代表满了我们就不能插入了二思路讲解前提a本文采取数组来实现队列去解决题目b开辟k1个空间front指向队首rear指向队尾的后一个rear这样会更好的判空和判满以下根据pop和push感受满和空以及所有的边界的处理1初始状态解释当front rear 即空2 push 1 2 3 4解释rera指向队尾的下一个元素3在满的情况push 5解释当然不能push5进来所以我们需要用一个条件限制满的再次push那就是判满条件rear1%k1 front此公式的意义在于判断rear的下一个是否为front是则满不是则还能pushQ为什么不直接rear1 front去判满A这只适用于rear在数组非末尾位置的时候而上面的表达式均适用本质就是利用%的特性其中的k1就是数组的容量大小4pop 1 25push5 6解释rear的边界处理rear (rear1)%(k1)6在满的情况下 push 7解释这是rear在非末尾的位置的判满 rear1%k1 front同样适用7pop 3 4 5 6 得到空解释①可得只要rear和front相等就是空②front的边界处理 front front%k1最后一个边界处理取队尾数据当rear下标为0 的时候这时候取队尾rear-1 会等于-1所以需要处理有两种方式1三目操作符 rear rear0k:rear2取模rear reark%k1(04)%54这两种方法都适用与所有的取队尾总结通过这几步我们可知满和空的判断表达式 以及front和rear超过边界的处理表达式满rear1%k1 frontrear 的下一个是front就是满空front rearrear超过边界rear (rear)%(k1)front超过边界front front%k1rear下标为0取队尾rear rear0k:rear 或 rear reark%k1(04)%54边界处理就是下标取模数组空间几个公式都是大同小异的都是%上k1这个数组容量大小三代码1初始化解释定义我们需要的值a是数组front指向第一个元素rear只想最后一个元素的下一个位置k是循环队列的大小我们按照设计思路实际申请k1个空间2MyCircularQueue(k): 构造器设置队列长度为 k1解释malloc k1个整形的数组空间给a3isEmpty(): 检查循环队列是否为空解释根据我们前文的判空表达式4isFull(): 检查循环队列是否已满解释根据我们前文的判满表达式5enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。解释①先判满满了则无法插入返回false②有空间根据前文插入到下标为rear处再rear要③最后再通过rear的边界的处理的表达式处理rear6deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。解释①先判空空了则无法删除返回false②能删直接front③最后再通过front的边界的处理的表达式处理front7Front: 从队首获取元素。如果队列为空返回 -1 。解释直接返回front处的数据8Rear: 获取队尾元素。如果队列为空返回 -1 。解释通过的前文的取队尾的rear的处理表达式来取队尾1三目操作符 rear rear0k:rear2取模rear reark%k1我用的第二种方法9 销毁队列解释先free a 再free obj总代码typedef struct { int * a; int k; int front; int rear; } MyCircularQueue; MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* obj (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); obj-a (int*)malloc(sizeof(int)*(k1)); obj-front 0; obj-rear 0; obj-k k; return obj; } bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj-front obj-rear; } bool myCircularQueueIsFull(MyCircularQueue* obj) { return (obj-rear1) % (obj-k1) obj-front; } bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if(myCircularQueueIsFull(obj)) return false; obj-a[obj-rear] value; obj-rear 1; obj-rear obj-rear %(obj-k1); return true; } bool myCircularQueueDeQueue(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return false; obj-front 1; obj-front obj-front % (obj-k1); return true; } int myCircularQueueFront(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return -1; return obj-a[obj-front]; } int myCircularQueueRear(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return -1; return obj-a[obj-rear0?obj-k:obj-rear-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); */ [ 作者 ] shylyly [ 首次发布 ] 2024.7.23❌ [ 最新修改 ] 2026.5.26 [ 声明 ] 由于笔者水平有限文中难免有疏漏或不妥之处还望读者不吝赐教
