LeetCode 641. 设计循环双端队列
题目描述
题意分析
设计最大容量为
k的双端队列，支持两端插入、删除和读取，并能判断空、满。插入到满队列或从空队列删除时返回false；读取空队列的两端时返回-1。若每次队首操作都移动整个数组，开销会随元素数量增长。环形数组将逻辑顺序与物理下标分开，只移动端点下标，就能让所有队列接口保持常数时间。题目保证容量至少为一。
解法：环形数组加队首下标与元素数
核心思路
[!blue]
使用长度为
k的数组保存值，head指向当前队首，size记录有效元素数量。逻辑上的第t个元素存放在values[(head+t)%k]，其中0 <= t < size。超过数组末尾后取模回到开头，逻辑顺序仍然连续。非空时，队尾是逻辑下标
size-1，对应(head+size-1)%k；尾插位置紧随其后，是(head+size)%k。尾插只需在这个位置写值并增加size，队首不变。前插则先把
head移到前一个循环位置(head-1+k)%k，写入新值并增加size。旧元素的物理位置不用变化，只是在新的逻辑顺序中整体后移一位。加上容量后再取模，可以避免 Java 和 Go 的负余数产生负下标。前删把
head循环后移一位，再减少size；尾删只减少size，原来的末项就退出有效范围。删除无需清空槽位，后续操作只按head和size判断哪些位置有效，旧值不会参与读取。空、满分别由
size == 0和size == k判断。未满时，新插入位置在当前有效范围之外，不会覆盖仍在队列中的元素；删除前先判断非空，也不会让数量变成负数。这样每次成功操作后，上述逻辑下标公式仍成立。判空判满必须发生在修改状态之前，失败的操作直接返回，不移动
head或size。读取时也先判空，再计算有效端点。
解题步骤
- 构造长度为
k的数组，两个状态量初始均为零。- 前插先检查未满，前移队首再写入；尾插在逻辑下标
size的槽位写入。成功后均将数量加一。- 前删先检查非空，再移动队首并减一；尾删只需在非空时减一。
- 读取队首时用
head，读取队尾时用(head+size-1)%k；空队列统一返回-1。删除到空以后，不需要把
head重置为零，下次插入仍可从当前循环位置建立新的有效范围。容量为一时，各种取模都回到唯一槽位，空满状态仍由数量准确区分。
代码实现
class MyCircularDeque {
private final int[] values;
private int head;
private int size;
public MyCircularDeque(int k) {
values = new int[k];
}
public boolean insertFront(int value) {
if (isFull()) {
return false;
}
head = (head - 1 + values.length) % values.length;
values[head] = value;
size++;
return true;
}
public boolean insertLast(int value) {
if (isFull()) {
return false;
}
values[(head + size) % values.length] = value;
size++;
return true;
}
public boolean deleteFront() {
if (isEmpty()) {
return false;
}
head = (head + 1) % values.length;
size--;
return true;
}
public boolean deleteLast() {
if (isEmpty()) {
return false;
}
size--;
return true;
}
public int getFront() {
return isEmpty() ? -1 : values[head];
}
public int getRear() {
return isEmpty() ? -1 : values[(head + size - 1) % values.length];
}
public boolean isEmpty() {
return size == 0;
}
public boolean isFull() {
return size == values.length;
}
}
type MyCircularDeque struct {
values []int
head, size int
}
func Constructor(k int) MyCircularDeque { return MyCircularDeque{values: make([]int, k)} }
func (q *MyCircularDeque) InsertFront(value int) bool {
if q.IsFull() {
return false
}
q.head = (q.head - 1 + len(q.values)) % len(q.values)
q.values[q.head] = value
q.size++
return true
}
func (q *MyCircularDeque) InsertLast(value int) bool {
if q.IsFull() {
return false
}
q.values[(q.head+q.size)%len(q.values)] = value
q.size++
return true
}
func (q *MyCircularDeque) DeleteFront() bool {
if q.IsEmpty() {
return false
}
q.head = (q.head + 1) % len(q.values)
q.size--
return true
}
func (q *MyCircularDeque) DeleteLast() bool {
if q.IsEmpty() {
return false
}
q.size--
return true
}
func (q *MyCircularDeque) GetFront() int {
if q.IsEmpty() {
return -1
}
return q.values[q.head]
}
func (q *MyCircularDeque) GetRear() int {
if q.IsEmpty() {
return -1
}
return q.values[(q.head+q.size-1)%len(q.values)]
}
func (q *MyCircularDeque) IsEmpty() bool { return q.size == 0 }
func (q *MyCircularDeque) IsFull() bool { return q.size == len(q.values) }
复杂度分析
- 时间复杂度：构造数组为 $O(k)$；每个队列接口只进行常数次判断、下标计算和读写，均为 $O(1)$。
- 空间复杂度：$O(k)$，固定数组加两个状态量，不随操作次数增长。
关键点总结
[!green]
head与size共同确定全部有效位置，队尾可以随时算出，无需再同步维护一个尾指针。- 取模只处理物理下标回绕，队列是否有元素、能否插入由
size决定。- 删除改变有效范围，不必搬移元素或清除旧槽位。
易错点总结
[!yellow]
- 把尾插位置写成
head+size-1，会覆盖当前末项；这个公式用于读取已有队尾。- 前移下标时没有先加容量，可能得到负余数。
- 满队列插入失败后仍更新状态，会破坏原有内容与数量。
- 用槽位是否为零判断空满：零本身是合法元素，槽位旧值也不能代表有效范围。
- 空队列没有有效队尾，必须先判空再读取。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 622. 设计循环队列 | 中等 | 同样使用 head、size 区分空满；双端队列额外支持 head 向前回绕和尾部删除。 |