LeetCode-Go 题解 622Design Circular Queue用数组实现循环队列Ring Buffer【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本篇文章以 LeetCode-Go 仓库中 622. Design Circular Queue 题目文档 为核心完整讲解循环队列环形缓冲器 Ring Buffer的设计思路与 Go 语言实现。读者将掌握MyCircularQueue六个核心 API 的底层原理、下标取模的环绕技巧以及仓库内配套源码与单元测试的验证方法可直接在本地复现 LeetCode 622 的满分解法。题目要求LeetCode 622. Design Circular Queue循环队列是一种线性数据结构其操作基于FIFO先进先出原则并且队尾被连接回队首形成一个环因此也被称为环形缓冲器Ring Buffer。循环队列最大的好处是能复用队列前部已经用过的空间在普通队列中一旦队列满了就无法再插入下一个元素即使队列头部已经腾出了空闲位置而循环队列可以借助取模运算让队尾指针绕回队首把这些空间继续用于存储新值。API 定义需要实现MyCircularQueue类接口如下方法行为返回MyCircularQueue(k)构造器初始化长度为k的队列对象实例Front()获取队首元素队列为空时返回-1intRear()获取队尾元素队列为空时返回-1intenQueue(value)向循环队列插入一个元素成功插入返回truebooleandeQueue()从循环队列删除一个元素成功删除返回truebooleanisEmpty()检查队列是否为空booleanisFull()检查队列是否已满boolean约束条件1 k 1000队列容量上限为 10000 value 1000元素取值非负最多进行3000次enQueue、deQueue、Front、Rear、isEmpty、isFull调用。官方示例Input [MyCircularQueue, enQueue, enQueue, enQueue, enQueue, Rear, isFull, deQueue, enQueue, Rear] [[3], [1], [2], [3], [4], [], [], [], [4], []] Output [null, true, true, true, false, 3, true, true, true, 4]对应的逐步执行过程MyCircularQueue myCircularQueue new MyCircularQueue(3); myCircularQueue.enQueue(1); // return True myCircularQueue.enQueue(2); // return True myCircularQueue.enQueue(3); // return True myCircularQueue.enQueue(4); // return False ← 容量为 3队列已满 myCircularQueue.Rear(); // return 3 myCircularQueue.isFull(); // return True myCircularQueue.deQueue(); // return True ← 弹出队首 1 myCircularQueue.enQueue(4); // return True ← 复用腾出的空间 myCircularQueue.Rear(); // return 4Follow-up 追问题目额外要求能否在不使用内置队列的前提下解决本题答案是肯定的——本仓库的解法完全不依赖任何内置队列容器而是用定长数组加双指针手写实现天然满足该要求。解题思路数组 双指针 下标取模本仓库 README 给出的解题思路非常明确设计一个环形队列底层用数组实现。额外维护 4 个变量队列的总容量cap、队列当前大小size、队首下标left、队尾下标right。每添加一个元素便维护left、right、size下标需要对cap取余因为超过cap大小之后需要循环存储。其核心机制可以概括为三点定长数组承载数据容量固定为k无论进出多少元素内存占用始终保持O(k)两个游标指针代替物理搬运left指向队首、right指向下一个可写位置出队/入队只移动指针不搬移数组元素取模实现环绕right (right 1) % cap、left (left 1) % cap让指针在越界时自动绕回数组头部形成逻辑上的环。判空、判满则直接依赖size计数size 0为空size cap为满。这样避免了头尾指针相遇无法区分空/满这一经典问题实现起来最直观。完整源码解析LeetCode-Go 的 Go 实现仓库中 622. Design Circular Queue.go 与题目文档中的代码一致全部操作均为O(1)时间复杂度。先看结构体定义type MyCircularQueue struct { cap int size int queue []int left int right int }字段含义cap队列总容量即构造时传入的ksize当前已存储的元素个数用于判空/判满queue底层定长数组make([]int, k)left队首元素的下标Front直接读它right下一个可写入位置的下标EnQueue写它构造器 Constructorfunc Constructor(k int) MyCircularQueue { return MyCircularQueue{cap: k, size: 0, left: 0, right: 0, queue: make([]int, k)} }一次性分配长度为k的底层数组四个指针/计数全部初始化为0。对应源码见 Constructor 实现。入队 EnQueuefunc (this *MyCircularQueue) EnQueue(value int) bool { if this.size this.cap { return false } this.size this.queue[this.right] value this.right this.right % this.cap return true }入队分四步先判满size cap直接返回falsesize自增把value写入right指向的位置right前进并对cap取模实现环绕。例如容量为 3 时right从 2 走到 3 后3 % 3 0自动回到数组头部。对应源码见 EnQueue 实现。出队 DeQueuefunc (this *MyCircularQueue) DeQueue() bool { if this.size 0 { return false } this.size-- this.left this.left % this.cap return true }出队同样先判空size 0返回falsesize自减left前进并取模。注意这里无需清空或搬移元素被弹出的位置会在后续入队时被覆盖写入这正是环形缓冲复用空间的体现。对应源码见 DeQueue 实现。队首 Frontfunc (this *MyCircularQueue) Front() int { if this.size 0 { return -1 } return this.queue[this.left] }队列非空时直接返回this.queue[this.left]空队列按题目约定返回-1。对应源码见 Front 实现。队尾 Rearfunc (this *MyCircularQueue) Rear() int { if this.size 0 { return -1 } if this.right 0 { return this.queue[this.cap-1] } return this.queue[this.right-1] }Rear是本实现中唯一需要特殊分支的方法队尾元素位于right - 1但当right恰好取模回到0时right - 1为-1此时真正的队尾在数组末尾queue[cap-1]。对应源码见 Rear 实现。判空与判满func (this *MyCircularQueue) IsEmpty() bool { return this.size 0 } func (this *MyCircularQueue) IsFull() bool { return this.size this.cap }两个方法都直接基于size计数判断逻辑极简且无歧义。对应源码见 IsEmpty / IsFull 实现。复杂度分析时间复杂度构造、入队、出队、取队首、取队尾、判空、判满全部为O(1)空间复杂度O(k)仅存储定长数组和几个标量不随调用次数增长。官方示例逐步推演以容量k 3为例跟踪left、right、size三个游标的变化初始left0, right0, size0操作结果sizeleftright数组内容仅展示有效区EnQueue(1)true101[1]EnQueue(2)true202[1, 2]EnQueue(3)true300[1, 2, 3]满EnQueue(4)false300已满拒绝Rear()3300走right 0分支读queue[2]isFull()true300size capDeQueue()true210弹出队首1EnQueue(4)true311复用下标 0 的空间写入4Rear()4311读queue[0]可以看到第 8 步中right在写入后由0前进到1元素4恰好写入之前被弹出的1所在的下标 0 位置——这就是循环队列利用队列前面空间的直观体现。仓库测试用例验证仓库在 622. Design Circular Queue_test.go 中提供了针对本题的单元测试覆盖了若干关键边界场景空队列边界对空队列执行DeQueue应返回falseFront、Rear应返回-1正常填充与判满连续入队 3 个元素后EnQueue(40)应返回false队首队尾取值Front()返回最先入队的10Rear()返回最后入队的30环绕分支覆盖先DeQueue腾出空间再EnQueue(40)让right取模回到0随后验证Rear()命中right 0分支返回40——该用例专门用于覆盖Rear中与普通分支不同的取模回绕路径。本地运行测试仓库根目录的 gotest.sh 使用如下命令一次性跑完所有题目并生成覆盖率报告go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...若只想验证本题可单独执行go test -v ./leetcode/0622.Design-Circular-Queue/由于Test_Problem622中所有分支包括right 0的特例都被显式断言覆盖该目录的 Go 代码在本仓库的测试体系中可达到完整的分支覆盖。拓展环形缓冲区与工程实践与仓库通用 Queue 的对比本仓库在 structures/Queue.go 中提供了一个通用的Queue结构其实现是切片 append 头部裁剪的普通队列Push通过append追加到尾部Pop通过q.nums q.nums[1:]移除头部元素。这种实现简单直接但存在两点差异空间复用普通队列每次Pop都会丢弃切片头部无法回头利用已弹出的空间而循环队列通过指针回绕固定复用底层数组容量上限structures.Queue可随append动态扩容而MyCircularQueue容量固定为k适合对内存占用有硬性上限的场景。数组双端实现的其他变体本题常见的另一种写法是不维护size而是额外预留一个空位让left指向队首、right指向队尾元素本身以(right 1) % cap left判满、left right判空代价是容量为k的数组实际只能存储k-1个元素。本仓库采用独立的size计数器牺牲一个int的空间换取满容量可用与更直观的判断逻辑是一种更实用的工程选择。现实世界的 Ring Buffer循环队列的工程原型环形缓冲区广泛用于生产者-消费者模型、内核/驱动中的 DMA 数据缓存、网络收发缓冲、日志环形记录等场景。其核心价值在于读写双方只需各自维护一个游标互不搬移数据就能在固定大小的内存上以 O(1) 代价持续流转数据。理解了本题的left/right取模回绕也就掌握了这一类工业级数据结构的基本盘。小结LeetCode 622 是一道简单但经典的数据结构设计题。LeetCode-Go 仓库给出的解法用定长数组 left/right双游标 对容量取模三件套实现了全部 O(1) 操作且不依赖任何内置队列正面回答了题目的 Follow-up。配合仓库内针对空队列、满队列、指针回绕分支的完整单测题目文档、源码实现 与 单元测试 三者互为印证可以作为理解环形缓冲区的首选参考资料。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考