641. 设计循环双端队列

题目描述

设计实现双端队列。

实现 MyCircularDeque 类：

MyCircularDeque(k)：构造函数，双端队列最大为 k 。
boolean insertFront()：将一个元素添加到双端队列头部。如果操作成功返回 true，否则返回 false 。
boolean insertLast()：将一个元素添加到双端队列尾部。如果操作成功返回 true，否则返回 false 。
boolean deleteFront()：从双端队列头部删除一个元素。如果操作成功返回 true，否则返回 false 。
boolean deleteLast()：从双端队列尾部删除一个元素。如果操作成功返回 true，否则返回 false 。
int getFront()：从双端队列头部获得一个元素。如果双端队列为空，返回 -1 。
int getRear()：获得双端队列的最后一个元素。如果双端队列为空，返回 -1 。
boolean isEmpty()：若双端队列为空，则返回 true ，否则返回 false 。
boolean isFull()：若双端队列满了，则返回 true ，否则返回 false 。

示例

text

输入：
["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]

解释

text

MyCircularDeque myCircularDeque = new MyCircularDeque(3);
myCircularDeque.insertLast(1);   // 返回 true
myCircularDeque.insertLast(2);   // 返回 true
myCircularDeque.insertFront(3);  // 返回 true
myCircularDeque.insertFront(4);  // 已经满了，返回 false
myCircularDeque.getRear();       // 返回 2
myCircularDeque.isFull();        // 返回 true
myCircularDeque.deleteLast();    // 返回 true
myCircularDeque.insertFront(4);  // 返回 true
myCircularDeque.getFront();      // 返回 4

约束

1 <= k <= 1000
0 <= value <= 1000
最多调用 2000 次 insertFront、insertLast、deleteFront、deleteLast、getFront、getRear、isEmpty、isFull

核心思路

这题本质上是在实现一个：

可以从头部插入 / 删除
也可以从尾部插入 / 删除
容量固定
并且首尾能够“循环复用”空间

的数据结构。

关键点有两个：

它是 双端队列，所以头尾都能操作。
它是循环的，所以当数组走到末尾时，可以绕回开头继续用。

这题至少有两种常见做法：

解法一：定长数组 + 头指针 + 元素个数（推荐）
解法二：双向链表 + 容量计数

虽然题目名字里有“循环”，但实际上只要你正确维护容量和头尾位置，两种做法都能通过。

解法一：定长数组 + 头指针 + 元素个数

这是最标准、最贴合题意的做法。

思路拆解

我们准备一个长度为 k 的数组 data，然后维护两个量：

front：当前队头元素所在的位置
size：当前已经存了多少个元素

有了这两个量之后：

队尾元素位置可以算出来
队列是否为空 / 是否已满也能判断
插入和删除时，只需要用取模运算让下标循环移动

为什么只维护 `front` 和 `size` 就够了？

因为：

队头位置是 front
队尾位置就是：

(front + size - 1) % capacity

所以我们不一定非要再额外存一个 rear 指针。

这样反而更统一。

一步一步写出算法

第一步：定义数据结构

class MyCircularDeque {
    private data: number[]
    private front: number
    private size: number
    private capacity: number

    constructor(k: number) {
        this.data = new Array(k)
        this.front = 0
        this.size = 0
        this.capacity = k
    }
}

第二步：判断空和满

isEmpty(): boolean {
    return this.size === 0
}

isFull(): boolean {
    return this.size === this.capacity
}

第三步：头部插入

头插时，新元素会出现在当前 front 的前一个位置。

由于数组是循环的，所以：

this.front = (this.front - 1 + this.capacity) % this.capacity

然后把值放进去，size++。

insertFront(value: number): boolean {
    if (this.isFull()) {
        return false
    }

    this.front = (this.front - 1 + this.capacity) % this.capacity
    this.data[this.front] = value
    this.size++
    return true
}

第四步：尾部插入

尾插时，新元素应该放在当前队尾的下一个位置。

也就是：

const rearIndex = (this.front + this.size) % this.capacity

然后放值，size++。

insertLast(value: number): boolean {
    if (this.isFull()) {
        return false
    }

    const rearIndex = (this.front + this.size) % this.capacity
    this.data[rearIndex] = value
    this.size++
    return true
}

第五步：头部删除

头删其实不用真的清空数组，只要让 front 往后走一格，然后 size-- 即可。

deleteFront(): boolean {
    if (this.isEmpty()) {
        return false
    }

    this.front = (this.front + 1) % this.capacity
    this.size--
    return true
}

第六步：尾部删除

尾删同样不用真正删值，只要 size-- 即可。

因为尾部位置是由 front 和 size 推出来的。

deleteLast(): boolean {
    if (this.isEmpty()) {
        return false
    }

    this.size--
    return true
}

第七步：读取队头和队尾

队头：

getFront(): number {
    if (this.isEmpty()) {
        return -1
    }
    return this.data[this.front]
}

队尾：

getRear(): number {
    if (this.isEmpty()) {
        return -1
    }
    const rearIndex = (this.front + this.size - 1) % this.capacity
    return this.data[rearIndex]
}

代码实现（TypeScript）

class MyCircularDeque {
    private data: number[]
    private front: number
    private size: number
    private capacity: number

    constructor(k: number) {
        this.data = new Array(k)
        this.front = 0
        this.size = 0
        this.capacity = k
    }

    insertFront(value: number): boolean {
        if (this.isFull()) {
            return false
        }

        this.front = (this.front - 1 + this.capacity) % this.capacity
        this.data[this.front] = value
        this.size++
        return true
    }

    insertLast(value: number): boolean {
        if (this.isFull()) {
            return false
        }

        const rearIndex = (this.front + this.size) % this.capacity
        this.data[rearIndex] = value
        this.size++
        return true
    }

    deleteFront(): boolean {
        if (this.isEmpty()) {
            return false
        }

        this.front = (this.front + 1) % this.capacity
        this.size--
        return true
    }

    deleteLast(): boolean {
        if (this.isEmpty()) {
            return false
        }

        this.size--
        return true
    }

    getFront(): number {
        if (this.isEmpty()) {
            return -1
        }
        return this.data[this.front]
    }

    getRear(): number {
        if (this.isEmpty()) {
            return -1
        }
        const rearIndex = (this.front + this.size - 1) % this.capacity
        return this.data[rearIndex]
    }

    isEmpty(): boolean {
        return this.size === 0
    }

    isFull(): boolean {
        return this.size === this.capacity
    }
}

复杂度分析

每个操作时间复杂度：O(1)
空间复杂度：O(k)

这一解法的优缺点

优点：

完全符合“循环队列”的设计思路
所有操作都是 O(1)
是最标准的解法

缺点：

下标取模稍微绕一点
第一次写时容易把头尾位置算错

解法二：双向链表 + 容量计数

这个做法更容易从“数据结构行为”角度理解。

思路拆解

我们维护一个双向链表，并记录：

size：当前元素个数
capacity：最大容量
head：头哨兵节点
tail：尾哨兵节点

双向链表天然支持：

头部 O(1) 插入 / 删除
尾部 O(1) 插入 / 删除

所以只要再额外判断一下是否为空 / 是否已满，就能实现题目要求。

这个做法虽然没有显式体现“循环数组”，但依然满足题目接口要求。

一步一步写出算法

第一步：定义链表节点

class Node {
    val: number
    prev: Node | null = null
    next: Node | null = null

    constructor(val: number) {
        this.val = val
    }
}

第二步：定义双端队列结构

我们用两个哨兵节点把真实数据夹在中间。

class MyCircularDeque {
    private capacity: number
    private size: number
    private head: Node
    private tail: Node

    constructor(k: number) {
        this.capacity = k
        this.size = 0
        this.head = new Node(-1)
        this.tail = new Node(-1)
        this.head.next = this.tail
        this.tail.prev = this.head
    }
}

第三步：封装插入节点操作

头插：把新节点插到 head 后面。

尾插：把新节点插到 tail 前面。

第四步：实现删除操作

头删：删掉 head.next。

尾删：删掉 tail.prev。

都只需要改几根指针。

第五步：实现查询和判空判满

getFront() 返回 head.next
getRear() 返回 tail.prev
isEmpty() 看 size === 0
isFull() 看 size === capacity

代码实现（TypeScript）

class Node {
    val: number
    prev: Node | null = null
    next: Node | null = null

    constructor(val: number) {
        this.val = val
    }
}

class MyCircularDeque {
    private capacity: number
    private size: number
    private head: Node
    private tail: Node

    constructor(k: number) {
        this.capacity = k
        this.size = 0
        this.head = new Node(-1)
        this.tail = new Node(-1)
        this.head.next = this.tail
        this.tail.prev = this.head
    }

    insertFront(value: number): boolean {
        if (this.isFull()) {
            return false
        }

        const node = new Node(value)
        const first = this.head.next!

        node.next = first
        node.prev = this.head
        this.head.next = node
        first.prev = node
        this.size++
        return true
    }

    insertLast(value: number): boolean {
        if (this.isFull()) {
            return false
        }

        const node = new Node(value)
        const last = this.tail.prev!

        node.prev = last
        node.next = this.tail
        last.next = node
        this.tail.prev = node
        this.size++
        return true
    }

    deleteFront(): boolean {
        if (this.isEmpty()) {
            return false
        }

        const first = this.head.next!
        const second = first.next!
        this.head.next = second
        second.prev = this.head
        this.size--
        return true
    }

    deleteLast(): boolean {
        if (this.isEmpty()) {
            return false
        }

        const last = this.tail.prev!
        const secondLast = last.prev!
        secondLast.next = this.tail
        this.tail.prev = secondLast
        this.size--
        return true
    }

    getFront(): number {
        if (this.isEmpty()) {
            return -1
        }
        return this.head.next!.val
    }

    getRear(): number {
        if (this.isEmpty()) {
            return -1
        }
        return this.tail.prev!.val
    }

    isEmpty(): boolean {
        return this.size === 0
    }

    isFull(): boolean {
        return this.size === this.capacity
    }
}

复杂度分析

每个操作时间复杂度：O(1)
空间复杂度：O(k)

这一解法的优缺点

优点：

头尾操作更直观
不用处理取模下标
双端队列语义很清晰

缺点：

代码量更大
不如数组法贴近“循环队列”的本意

两种解法对比

解法	时间复杂度	空间复杂度	特点
定长数组 + `front` + `size`	`O(1)`	`O(k)`	最标准，最贴题
双向链表 + 容量计数	`O(1)`	`O(k)`	更直观，但代码更长

如果你是为了刷题和面试，建议优先掌握第一种数组写法。

手动模拟一遍数组解法

假设：

text

k = 3

初始：

front = 0
size = 0
data = [_, _, _]

第一步：`insertLast(1)`

尾部位置：

text

(front + size) % 3 = (0 + 0) % 3 = 0

放入后：

text

data = [1, _, _]
front = 0
size = 1

第二步：`insertLast(2)`

尾部位置：

text

(0 + 1) % 3 = 1

放入后：

text

data = [1, 2, _]
front = 0
size = 2

第三步：`insertFront(3)`

头部前移：

text

front = (0 - 1 + 3) % 3 = 2

放入后：

text

data = [1, 2, 3]
front = 2
size = 3

此时队列逻辑顺序是：

text

3, 1, 2

第四步：`getRear()`

尾部位置：

text

(front + size - 1) % 3 = (2 + 3 - 1) % 3 = 1

所以队尾值是：

text

面试时最容易错的点

1. 别把“循环双端队列”理解成必须用链表

题目里的“循环”更强调：

固定容量
空间可复用

所以最标准解其实是数组 + 取模。

2. 删除时不一定要真的清空值

在数组实现里：

头删只改 front
尾删只改 size

旧值留在数组里也没关系，因为逻辑上已经不属于队列了。

3. 头插时下标可能变成负数

所以一定要写成：

(this.front - 1 + this.capacity) % this.capacity

不能只写 this.front - 1。

这条公式的核心作用，就是处理：

front = 0 时，再往前走一格应该绕到数组最后面

比如容量是 5：

如果 front = 3：

(3 - 1 + 5) % 5 = 2

结果其实就和 3 - 1 一样。

如果 front = 1：

(1 - 1 + 5) % 5 = 0

结果也还是正常的前一个位置。

只有当 front = 0 时：

(0 - 1 + 5) % 5 = 4

它才体现出“循环”的意义，也就是：

从数组开头再往前走一格
会绕回数组末尾

所以你可以这样理解：

大多数时候，这个公式等价于 front - 1
只有在 front = 0 时，它负责把下标安全地绕回最后一个位置

4. 队尾位置别算错

队尾下标是：

(this.front + this.size - 1) % this.capacity

而尾插位置是：

(this.front + this.size) % this.capacity

这两个公式不要混了。

一句话总结

这题的本质是：

在固定容量下，支持双端 O(1) 插入删除，并让数组下标能够循环复用。

想写最标准答案：用 定长数组 + front + size
想从数据结构角度理解：用 双向链表 + 容量计数

641. 设计循环双端队列

题目描述

示例

解释

约束

核心思路

解法一：定长数组 + 头指针 + 元素个数

思路拆解

为什么只维护 front 和 size 就够了？

一步一步写出算法

第一步：定义数据结构

第二步：判断空和满

第三步：头部插入

第四步：尾部插入

第五步：头部删除

第六步：尾部删除

第七步：读取队头和队尾

代码实现（TypeScript）

复杂度分析

这一解法的优缺点

解法二：双向链表 + 容量计数

思路拆解

一步一步写出算法

第一步：定义链表节点

第二步：定义双端队列结构

第三步：封装插入节点操作

第四步：实现删除操作

第五步：实现查询和判空判满

代码实现（TypeScript）

复杂度分析

这一解法的优缺点

两种解法对比

手动模拟一遍数组解法

第一步：insertLast(1)

第二步：insertLast(2)

第三步：insertFront(3)

第四步：getRear()

面试时最容易错的点

1. 别把“循环双端队列”理解成必须用链表

2. 删除时不一定要真的清空值

3. 头插时下标可能变成负数

4. 队尾位置别算错

一句话总结

推荐你最后记住的标准写法

为什么只维护 `front` 和 `size` 就够了？

第一步：`insertLast(1)`

第二步：`insertLast(2)`

第三步：`insertFront(3)`

第四步：`getRear()`