LeetCode 641中等设计
设计循环双端队列 图解题解
这道题到底在问什么
设计实现 MyCircularDeque 类。构造函数 MyCircularDeque(k) 设置双端队列最大容量为 k。insertFront、insertLast 在头部或尾部插入元素，成功返回 true，否则返回 false；deleteFront、deleteLast 删除头部或尾部元素，成功返回 true，否则返回 false；getFront、getRear 返回头部或尾部元素，空队列返回 -1；isEmpty 和 isFull 分别判断空和满。
- 输入
- ["MyCircularDeque","insertLast","insertLast","insertFront","insertFront","getRear","isFull","deleteLast","insertFront","getFront"]
- 参数
- [[3],[1],[2],[3],[4],[],[],[],[4],[]]
- 输出
- [null,true,true,true,false,2,true,true,true,4]
最优解：一步一步想明白
- 3这题想让你把固定长度数组当成一个环：下标走到末尾后绕回开头，头尾移动都只改指针。
- 4保留一个空槽后，空和满就不会都长成 front == rear。所有头尾操作都围绕这两个指针定义展开。
- 5执行：cap = k + 1; q = [None] * cap; front = rear = 0front 和 rear 都指向下标 0：这不是满，而是空。满要看 (rear + 1) % cap 是否追上 front。
- 6执行：q[rear] = 1; rear = (rear + 1) % cap尾插时，rear 指向“队尾后面的空位”。先把 1 写到 rear=0，再让 rear 前进到 1。
- 7执行：q[rear] = 2; rear = (rear + 1) % cap再插入 2，写入下标 1，rear 前进到 2。rear 仍然指向下一个可写空槽。
- 8执行：front = (front - 1) % cap; q[front] = 3头插要先把 front 往前挪一格。0 的前一格通过取模绕到 3，再把 3 写进去。
- 9执行：if isFull(): return False虽然数组下标 2 还是空的，但它正是 rear 指向的保留空槽，不能写。保留它才能区分空和满。
- 10执行：q[(rear - 1) % cap]rear 自己指向空位，不是尾元素。真正队尾是 (rear - 1) % cap。
- 11执行：(rear + 1) % cap == front这一步对应官方示例里的 isFull()。判断满不数元素，只看 rear 再走一步是否撞上 front。
- 12执行：rear = (rear - 1) % cap; q[rear] = None尾删要先让 rear 回到真正的尾元素位置，再把这个槽清空。现在 rear=1，队尾后空位变成下标 1。
- 13执行：front = (front - 1) % cap; q[front] = 4删除尾部以后不满了。front 从 3 往前到 2，写入 4，队首就变成 4。
- 14执行：return q[front]front 始终指向队首元素，所以 getFront 只要判空后返回 q[front]。
- 15执行：q[front] = None; front = (front + 1) % cap头删和尾删方向相反：deleteFront 清空当前 front 槽位，然后让 front 向后走一格，新的队首变成 3。
- 18设计类题最怕边写边改定义。先固定 front/rear 的语义，后面的代码只是把语义翻译成公式。
⚠️ 容易写错的地方
✗ 错：内部数组只开 k 格
✓ 对：开 k+1 格并保留一个空槽
否则 front==rear 无法区分空和满。
✗ 错：把 rear 当成尾元素下标
✓ 对：rear 指向队尾后面的空位
getRear 要读 (rear - 1) % cap。
✗ 错：insertFront 先写 q[front] 再移动 front
✓ 对：先 front = (front - 1) % cap，再写 q[front]
front 必须始终指向新的队首元素。
✗ 错：deleteLast 先清 q[rear] 再 rear 后退
✓ 对：先 rear 后退到尾元素，再清空
rear 原本指向空位，不是要删除的元素。
完整代码（Python）
Python
class MyCircularDeque:
def __init__(self, k: int):
self.cap = k + 1
self.q = [None] * self.cap
self.front = 0
self.rear = 0
def insertFront(self, value: int) -> bool:
if self.isFull():
return False
self.front = (self.front - 1) % self.cap
self.q[self.front] = value
return True
def insertLast(self, value: int) -> bool:
if self.isFull():
return False
self.q[self.rear] = value
self.rear = (self.rear + 1) % self.cap
return True
def deleteFront(self) -> bool:
if self.isEmpty():
return False
self.q[self.front] = None
self.front = (self.front + 1) % self.cap
return True
def deleteLast(self) -> bool:
if self.isEmpty():
return False
self.rear = (self.rear - 1) % self.cap
self.q[self.rear] = None
return True
def getFront(self) -> int:
if self.isEmpty():
return -1
return self.q[self.front]
def getRear(self) -> int:
if self.isEmpty():
return -1
return self.q[(self.rear - 1) % self.cap]
def isEmpty(self) -> bool:
return self.front == self.rear
def isFull(self) -> bool:
return (self.rear + 1) % self.cap == self.front复杂度
时间复杂度
O(1)
每个操作只改常数个下标或数组槽位。
空间复杂度
O(k)
内部使用长度为 k+1 的数组。
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 设计循环双端队列 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这道题为什么用「设计」，换最直接的暴力解会差在哪？+
设计抓住了本题的结构特征，把暴力解里重复的工作省掉；暴力解通常要多嵌套一层枚举，数据一大就超时。具体对比见上文「暴力解及其卡点」与「最优解逐步推演」两节。
时间复杂度为什么是 undefined？怎么推出来的？+
按上文复杂度小节的推导，时间复杂度为 undefined。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。