LeetCode 641中等设计
设计循环双端队列 图解题解
这道题到底在问什么
设计循环双端队列 MyCircularDeque(k)：容量固定为 k。支持从队头/队尾插入与删除、查看队头/队尾、判空、判满。要求每个操作都是 O(1)。
- 输入
- new MyCircularDeque(3); insertLast(1); insertLast(2); insertFront(3); isFull();
- 输出
- true（容量 3 已放满 3,1,2）
最优解：一步一步想明白
- 3记住三样东西：front（队头格）、rear（队尾格）、size（元素个数）。下标越界就取模绕回，这就是「循环」的全部秘密。
- 4刚建好的双端队列：底盘是长度 5 的数组，全是空位 ·。还没有任何元素，size=0。
- 5下一步：insertLast(1)。先看当前状态——队列里是 [空]，size=0。准备从队尾插入 1。
- 6insertLast(1)：队列原本是空的，把第一个元素放进下标 0，front 和 rear 都指这里，size 变 1。
- 7下一步：insertLast(2)。先看当前状态——队列里是 [1]，size=1。准备从队尾插入 2。
- 8insertLast(2)：从队尾进。rear 往右挪一格到下标 1，把 2 写进去，size 变 2。
- 9下一步：insertLast(3)。先看当前状态——队列里是 [1 , 2]，size=2。准备从队尾插入 3。
- 10insertLast(3)：从队尾进。rear 往右挪一格到下标 2，把 3 写进去，size 变 3。
- 11下一步：insertFront(9)。先看当前状态——队列里是 [1 , 2 , 3]，size=3。准备从队头插入 9。
- 12insertFront(9)：从队头进。front 往左挪一格，越过左边界，取模绕回到末尾下标 4，写入 9，size 变 4。
- 13下一步：insertFront(8)。先看当前状态——队列里是 [9 , 1 , 2 , 3]，size=4。准备从队头插入 8。
- 14insertFront(8)：从队头进。front 往左挪一格到下标 3，写入 8，size 变 5。
- 15现在 size=5 等于容量，队列满了。isFull() 返回 true——这时候再 insert 会直接失败，不能覆盖已有元素。
- 16下一步：deleteLast()。先看当前状态——队列里是 [8 , 9 , 1 , 2 , 3]，size=5。准备删除队尾元素。
- 17deleteLast()：从队尾出。把队尾那格（标红，原值 3）清空，rear 往左收一格回到下标 1。size 变 4。
- 18下一步：insertFront(7)。先看当前状态——队列里是 [8 , 9 , 1 , 2]，size=4。准备从队头插入 7。
- 19insertFront(7)：从队头进。front 往左挪一格到下标 2，写入 7，size 变 5。
- 20现在 size=5 等于容量，队列满了。isFull() 返回 true——这时候再 insert 会直接失败，不能覆盖已有元素。
- 21下一步：deleteFront()。先看当前状态——队列里是 [7 , 8 , 9 , 1 , 2]，size=5。准备删除队头元素。
- 22deleteFront()：从队头出。把队头那格（标红，原值 7）清空，front 往右收一格到下标 3。size 变 4。
- 23下一步：deleteFront()。先看当前状态——队列里是 [8 , 9 , 1 , 2]，size=4。准备删除队头元素。
- 24deleteFront()：从队头出。把队头那格（标红，原值 8）清空，front 往右收一格到下标 4。size 变 3。
- 25回看整趟：数组长度始终是 5，元素没真的搬家，动的只是 front、rear、size 三个变量。下标越界就取模绕回——这就是循环双端队列。
⚠️ 容易写错的地方
✗ 错：下标 -1 直接取模：(front-1)%k
✓ 对：先加 k 再取模：(front-1+k)%k
很多语言里负数取模结果是负的，会算出非法下标；加 k 保证非负
✗ 错：用 front==rear 判空又判满，分不清
✓ 对：额外维护一个 size 计数
环上 front==rear 既可能是空也可能是满，光靠两个下标会歧义，加 size 最省心
✗ 错：删到只剩 0 个还去挪 front/rear
✓ 对：size 变 0 后不再挪下标
空队列再挪下标会让 front/rear 错位，下次插入位置就乱了
完整代码（Python / C++ / Java）
Python
class MyCircularDeque:
def __init__(self, k):
self.cap = k
self.q = [0]*k # 定长数组
self.front = self.rear = 0
self.size = 0
def insertFront(self, v):
if self.size == self.cap: return False
if self.size:
self.front = (self.front-1) % self.cap
self.q[self.front] = v; self.size += 1; return True
def insertLast(self, v):
if self.size == self.cap: return False
if self.size:
self.rear = (self.rear+1) % self.cap
self.q[self.rear] = v; self.size += 1; return True
def deleteFront(self):
if not self.size: return False
self.size -= 1
if self.size: self.front = (self.front+1) % self.cap
return True
def deleteLast(self):
if not self.size: return False
self.size -= 1
if self.size: self.rear = (self.rear-1) % self.cap
return True
def getFront(self): return -1 if not self.size else self.q[self.front]
def getRear(self): return -1 if not self.size else self.q[self.rear]
def isEmpty(self): return self.size == 0
def isFull(self): return self.size == self.capC++
class MyCircularDeque {
vector<int> q; int cap, front=0, rear=0, sz=0;
public:
MyCircularDeque(int k): q(k), cap(k) {}
bool insertFront(int v){
if(sz==cap) return false;
if(sz) front=(front-1+cap)%cap;
q[front]=v; sz++; return true; }
bool insertLast(int v){
if(sz==cap) return false;
if(sz) rear=(rear+1)%cap;
q[rear]=v; sz++; return true; }
bool deleteFront(){
if(!sz) return false; sz--;
if(sz) front=(front+1)%cap; return true; }
bool deleteLast(){
if(!sz) return false; sz--;
if(sz) rear=(rear-1+cap)%cap; return true; }
int getFront(){ return sz? q[front] : -1; }
int getRear(){ return sz? q[rear] : -1; }
bool isEmpty(){ return sz==0; }
bool isFull(){ return sz==cap; }
};Java
class MyCircularDeque {
int[] q; int cap, front=0, rear=0, sz=0;
public MyCircularDeque(int k){ q=new int[k]; cap=k; }
public boolean insertFront(int v){
if(sz==cap) return false;
if(sz>0) front=(front-1+cap)%cap;
q[front]=v; sz++; return true; }
public boolean insertLast(int v){
if(sz==cap) return false;
if(sz>0) rear=(rear+1)%cap;
q[rear]=v; sz++; return true; }
public boolean deleteFront(){
if(sz==0) return false; sz--;
if(sz>0) front=(front+1)%cap; return true; }
public boolean deleteLast(){
if(sz==0) return false; sz--;
if(sz>0) rear=(rear-1+cap)%cap; return true; }
public int getFront(){ return sz==0? -1 : q[front]; }
public int getRear(){ return sz==0? -1 : q[rear]; }
public boolean isEmpty(){ return sz==0; }
public boolean isFull(){ return sz==cap; }
}复杂度
时间
O(1)
每个操作只是改几个下标、读写一格，跟容量无关
空间
O(k)
一个长度为 k 的定长数组，外加 front/rear/size 三个变量
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 设计循环双端队列 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
front 和 rear 分别指什么？+
front 指向当前队头元素所在的格子，rear 指向当前队尾元素所在的格子。两者都是数组下标，会在环上移动。
为什么要单独存一个 size，不能只靠 front 和 rear 判断空/满吗？+
环上 front==rear 时既可能是空（一个都没有）也可能是满（绕了一圈），两个下标无法区分。多存一个 size 计数，判空看 size==0、判满看 size==容量，既简单又无歧义。
如果容量 k 传 0 会怎样？+
k=0 的队列永远是满的（size==0==cap），任何插入都返回 false，任何删除也返回 false。代码逻辑天然兼容，不需特判。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 设计循环双端队列 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
把这道题真正拿下
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。