最近，又开始连续有大厂员工猝死消息了

来一道和「设计数据结构」高度相关的题目。

题目描述

平台：LeetCode

题号：622

设计你的循环队列实现。

循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环，它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。

在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。

但是使用循环队列，我们能使用这些空间去存储新的值。

你的实现应该支持如下操作：

• MyCircularQueue(k): 构造器，设置队列长度为

。

• Front: 从队首获取元素。如果队列为空，返回

。

• Rear: 获取队尾元素。如果队列为空，返回

。

• enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
• deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
• isEmpty(): 检查循环队列是否为空。
• isFull(): 检查循环队列是否已满。

示例：

提示：

• 所有的值都在

至

的范围内；

• 操作数将在

至

的范围内；

• 请不要使用内置的队列库。

数据结构

创建一个长度为

的数组充当循环队列，使用两个变量 he 和 ta 来充当队列头和队列尾（起始均为

），整个过程 he 始终指向队列头部，ta 始终指向队列尾部的下一位置（待插入元素位置）。

两变量始终自增，通过与

取模来确定实际位置。

分析各类操作的基本逻辑：

• isEmpty 操作：当 he 和 ta 相等，队列存入元素和取出元素的次数相同，此时队列为空；
• isFull 操作：ta - he 即队列元素个数，当元素个数为

个时，队列已满；

• enQueue 操作：若队列已满，返回

，否则在 nums[ta % k] 位置存入目标值，并将 ta 指针后移；

• deQueue 操作：若队列为空，返回

，否则将 he 指针后移，含义为弹出队列头部元素；

• Front 操作：若队列为空，返回

，否则返回 nums[he % k] 队头元素；

• Rear 操作：若队列为空，返回

，否则返回 nums[(ta - 1) % k] 队尾元素；

Java 代码：

C++ 代码：

Python 代码：

TypeScript 代码：

• 时间复杂度：构造函数复杂度为

，其余操作复杂度为

• 空间复杂度：