LeetCode 641 设计循环双端队列（Design Circular Deque）

难度：Medium
标签：设计、队列、循环数组、双向链表

题目原文

题目描述

设计实现循环双端队列。循环双端队列可以在队列头部、尾部都执行插入、删除操作，并且队列容量固定为k。

需要实现MyCircularDeque类，包含下面8个方法：

1. MyCircularDeque(int k)：构造函数，初始化双端队列，最大容量为k
2. insertFront(int value)：把元素添加到队首；成功返回true，队列满返回false
3. insertLast(int value)：把元素添加到队尾；成功返回true，队列满返回false
4. deleteFront()：删除队首元素；成功返回true，队列为空返回false
5. deleteLast()：删除队尾元素；成功返回true，队列为空返回false
6. getFront()：获取队首元素；空队列返回 -1
7. getRear()：获取队尾元素；空队列返回 -1
8. isEmpty()：判断队列是否为空，空返回true
9. isFull()：判断队列是否已满，满返回true

样例

MyCircularDeque dq=MyCircularDeque(3)dq.insertLast(1)# Truedq.insertLast(2)# Truedq.insertFront(3)# Truedq.insertFront(4)# False，队列容量3已经满了dq.getRear()# 2dq.isFull()# Truedq.deleteLast()# Truedq.insertFront(4)# Truedq.getFront()# 4

费曼学习法拆解本题（用大白话讲给小白）

第一步：用通俗语言复述需求（费曼第一步）

普通队列：只能尾部加、头部删（先进先出）。
双端队列 deque：两头都能加、两头都能删。
循环 = 底层数组想象成一个圆环。数组最后一个位置的下一个是数组下标0。
循环双端队列 =容量固定，两端插入删除，满了就不能再加。

想象游乐园旋转木马座位，一共k个座位。
你既可以从第一个座位前面塞人（队首插入），也可以从最后座位后面塞人（队尾插入）；
也可以从最前面、最后面把人带走；
座位全部坐满，就不能再加人；没人的时候不能删除。

核心难点：
数组下标到边界（0或者k-1）的时候，加减下标要模运算实现循环，防止下标越界。

第二步：两种解法思路对比（费曼第二步）

解法1：循环数组（推荐面试首选，O(1)所有操作）

思路：
底层是固定大小数组，维护3个变量

1. front：队首元素下标
2. rear：队尾元素下标
3. count：当前队列里元素个数

✅ 优点：内存连续，访问速度快，所有操作O(1)，代码简洁
✅ 判断空/满极其简单：count ==0为空，count ==k为满，不需要浪费数组空位（这是本实现的关键简化技巧）

很多循环队列写法会空一个位置区分空和满，这里直接用count计数器，降低理解难度。

指针移动规则：

• 队首往前插：front = (front - 1 + k) % k
  加k再取模，是为了防止front=0，front-1变成负数
• 队尾往后插：rear = (rear + 1) % k

解法2：双向循环链表实现

思路：节点带前驱、后继指针，头尾相连成环；维护size、最大容量k。
✅优点：不需要处理数组下标、不用模运算；
❌缺点：需要创建节点对象，内存开销更大，指针操作容易写错，面试写代码更长。

本题优先写循环数组版本，面试写的快，bug更少。

第三步：挖掘坑点（费曼第三步）

坑1：(front -1) %k，front=0的时候，0-1=-1，负数模运算容易出错，必须先+k再%k：(front -1 +k) %k
坑2：getFront / getRear，如果队列空，必须返回-1，不能报错
坑3：insert的时候先判断isFull；delete的时候先判断isEmpty，不能操作满队列插入、空队列删除
坑4：插入队首和插入队尾，指针更新顺序不一样（先移动指针再放值）

第四步：现实应用场景举例

1. 滑动窗口最大值（LeetCode239）：单调双端队列，窗口左右滑动，两端增删元素；
2. 操作系统任务窃取调度器work stealing：每个线程维护一个deque，自己从尾部取任务，别的线程从头部偷任务；
3. 编辑器撤销重做undo/redo，双向保存操作记录；
4. 限流、环形缓冲区，网络IO固定大小ring buffer，固定容量循环读写；
5. 回文字符串校验，把字符放入双端队列，不断取出首尾对比。

解法1：循环数组实现，Python代码（每行详细注释）

classMyCircularDeque:def__init__(self,k:int):# 构造函数：初始化循环双端队列，最大容量kself.capacity=k# 队列最大容量，固定不变self.arr=[0]*k# 底层存储数组，长度kself.front=0# front：队首元素所在数组下标self.rear=0# rear：队尾元素所在数组下标self.count=0# count：当前队列里面元素数量definsertFront(self,value:int)->bool:""" 在队首插入元素 """# 如果队列满，直接返回False，插入失败ifself.isFull():returnFalse# 队首向前移动一位；front-1可能负数，+capacity再取模保证>=0self.front=(self.front-1+self.capacity)%self.capacity# 把value放到新的front位置self.arr[self.front]=value# 元素数量+1self.count+=1returnTruedefinsertLast(self,value:int)->bool:""" 在队尾插入元素 """ifself.isFull():returnFalse# 队尾向后移动一位，模运算实现循环self.rear=(self.rear+1)%self.capacity# 赋值self.arr[self.rear]=value self.count+=1returnTruedefdeleteFront(self)->bool:""" 删除队首元素 """ifself.isEmpty():returnFalse# 队首指针往后移动一位，相当于删掉原来front元素self.front=(self.front+1)%self.capacity self.count-=1returnTruedefdeleteLast(self)->bool:""" 删除队尾元素 """ifself.isEmpty():returnFalse# 队尾指针向前移动一位self.rear=(self.rear-1+self.capacity)%self.capacity self.count-=1returnTruedefgetFront(self)->int:""" 获取队首元素，空返回-1 """ifself.isEmpty():return-1returnself.arr[self.front]defgetRear(self)->int:""" 获取队尾元素，空返回-1 """ifself.isEmpty():return-1returnself.arr[self.rear]defisEmpty(self)->bool:""" 判断队列是否为空 """returnself.count==0defisFull(self)->bool:""" 判断队列是否满 """returnself.count==self.capacity# ========== 测试样例 ==========if__name__=="__main__":dq=MyCircularDeque(3)print(dq.insertLast(1))# Trueprint(dq.insertLast(2))# Trueprint(dq.insertFront(3))# Trueprint(dq.insertFront(4))# Falseprint(dq.getRear())# 2print(dq.isFull())# Trueprint(dq.deleteLast())# Trueprint(dq.insertFront(4))# Trueprint(dq.getFront())# 4

复杂度分析

• 所有操作insertFront / insertLast / deleteFront / deleteLast / getFront / getRear / isEmpty / isFull：O(1)，只是简单的数组赋值、下标计算、加减计数。
• 空间复杂度 O(k)，数组固定k个位置。

解法2：双向循环链表实现（Python，带详细注释）

# 定义双向链表节点classListNode:def__init__(self,value):self.val=value self.prev=None# 前驱指针self.next=None# 后继指针classMyCircularDeque:def__init__(self,k:int):self.capacity=k# 最大容量self.size=0# 当前元素个数self.head=None# 头节点self.tail=None# 尾节点definsertFront(self,value:int)->bool:ifself.isFull():returnFalsenew_node=ListNode(value)# 如果是空队列ifself.isEmpty():self.head=new_node self.tail=new_node new_node.next=new_node new_node.prev=new_nodeelse:# 新节点的next指向原来headnew_node.next=self.head# 原来head的prev指向新节点self.head.prev=new_node# 新节点prev指向tail，形成环new_node.prev=self.tail self.tail.next=new_node# 更新head为新节点self.head=new_node self.size+=1returnTruedefinsertLast(self,value:int)->bool:ifself.isFull():returnFalsenew_node=ListNode(value)ifself.isEmpty():self.head=new_node self.tail=new_node new_node.next=new_node new_node.prev=new_nodeelse:new_node.prev=self.tail new_node.next=self.head self.tail.next=new_node self.head.prev=new_node self.tail=new_node self.size+=1returnTruedefdeleteFront(self)->bool:ifself.isEmpty():returnFalse# 只有一个节点ifself.size==1:self.head=Noneself.tail=Noneelse:# 删除head，head移动到下一个self.head=self.head.next# 新head的prev指向tailself.head.prev=self.tail self.tail.next=self.head self.size-=1returnTruedefdeleteLast(self)->bool:ifself.isEmpty():returnFalseifself.size==1:self.head=Noneself.tail=Noneelse:self.tail=self.tail.prev self.tail.next=self.head self.head.prev=self.tail self.size-=1returnTruedefgetFront(self)->int:ifself.isEmpty():return-1returnself.head.valdefgetRear(self)->int:ifself.isEmpty():return-1returnself.tail.valdefisEmpty(self)->bool:returnself.size==0defisFull(self)->bool:returnself.size==self.capacity# 测试if__name__=="__main__":dq=MyCircularDeque(3)print(dq.insertLast(1))print(dq.insertLast(2))print(dq.insertFront(3))print(dq.insertFront(4))print(dq.getRear())print(dq.isFull())print(dq.deleteLast())print(dq.insertFront(4))print(dq.getFront())

两种方案对比

费曼复盘总结

这道题本质考察固定容量双端容器，核心考点是：循环下标模运算、边界判断。
数组版本用count计数器是简化技巧，避开传统循环队列“空位置区分满和空”的复杂判断。
记住：插入队首的时候，先移动front指针，再写入值；删除先判断是否为空，插入先判断是否已满。