What is the best approach for solving the Design Circular Deque problem?

Using a doubly linked list is the most efficient approach, allowing constant-time operations for insertion and deletion at both ends while maintaining a circular structure.

How do I handle the circular nature of the deque?

By keeping pointers to both the front and rear, and manipulating the `prev` and `next` pointers, you can ensure the circular structure is maintained during all operations.

What are the time and space complexities of the solution?

All operations in the `MyCircularDeque` class run in O(1) time, and the space complexity is O(k), where `k` is the size of the deque.

Can I implement the deque with an array instead of a linked list?

Yes, it is possible to implement a deque using an array, but it would require handling resizing when the deque is full, and it may not be as efficient as the linked-list approach for insertion and deletion at both ends.

What should I watch out for when implementing the Design Circular Deque problem?

Make sure you handle boundary conditions such as overflow and underflow properly, and ensure the circular structure is maintained by correctly updating the pointers during each operation.

#641

Medium

auto_awesome链表指针操作

LeetCode 题解工作台

设计循环双端队列

设计实现双端队列。实现 MyCircularDeque 类: MyCircularDeque(int k) ：构造函数,双端队列最大为 k 。 boolean insertFront() ：将一个元素添加到双端队列头部。如果操作成功返回 true ，否则返回 false 。 boolean in…

数组链表设计队列

题目描述

设计实现双端队列。

实现 MyCircularDeque 类:

MyCircularDeque(int 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 。

示例 1：

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

解释
MyCircularDeque circularDeque = new MycircularDeque(3); // 设置容量大小为3
circularDeque.insertLast(1);			        // 返回 true
circularDeque.insertLast(2);			        // 返回 true
circularDeque.insertFront(3);			        // 返回 true
circularDeque.insertFront(4);			        // 已经满了，返回 false
circularDeque.getRear();  				// 返回 2
circularDeque.isFull();				        // 返回 true
circularDeque.deleteLast();			        // 返回 true
circularDeque.insertFront(4);			        // 返回 true
circularDeque.getFront();				// 返回 4

提示：

1 <= k <= 1000
0 <= value <= 1000
insertFront, insertLast, deleteFront, deleteLast, getFront, getRear, isEmpty, isFull 调用次数不大于 2000 次

lightbulb

解题思路

方法一：数组

我们可以使用一个数组来实现循环双端队列。我们维护一个指向队头的指针 $\textit{front}$ 和一个表示队列中元素个数的变量 $\textit{size}$ ，以及一个表示队列容量的变量 $\textit{capacity}$ 。我们使用一个数组 $\textit{q}$ 来存储队列中的元素。

调用 $\textit{insertFront}$ 时，首先检查队列是否已满，如果已满则返回 $\text{false}$ 。如果队列不为空，则将 $\textit{front}$ 向前移动一个位置（使用模运算实现循环），然后将新元素插入到 $\textit{front}$ 位置，并将 $\textit{size}$ 加 1。

调用 $\textit{insertLast}$ 时，首先检查队列是否已满，如果已满则返回 $\text{false}$ 。如果队列不为空，则计算新元素应该插入的位置（使用 $\textit{front}$ 和 $\textit{size}$ 计算），将新元素插入到该位置，并将 $\textit{size}$ 加 1。

调用 $\textit{deleteFront}$ 时，首先检查队列是否为空，如果为空则返回 $\text{false}$ 。如果队列不为空，则将 $\textit{front}$ 向后移动一个位置（使用模运算实现循环），并将 $\textit{size}$ 减 1。

调用 $\textit{deleteLast}$ 时，首先检查队列是否为空，如果为空则返回 $\text{false}$ 。如果队列不为空，则将 $\textit{size}$ 减 1。

调用 $\textit{getFront}$ 时，首先检查队列是否为空，如果为空则返回 $-1$ 。如果队列不为空，则返回 $\textit{q}[\textit{front}]$ 。

调用 $\textit{getRear}$ 时，首先检查队列是否为空，如果为空则返回 $-1$ 。如果队列不为空，则计算队尾元素的位置（使用 $\textit{front}$ 和 $\textit{size}$ 计算），并返回该位置的元素。

调用 $\textit{isEmpty}$ 时，检查 $\textit{size}$ 是否为 $0$ 。

调用 $\textit{isFull}$ 时，检查 $\textit{size}$ 是否等于 $\textit{capacity}$ 。

以上操作的时间复杂度均为 $O(1)$ ，空间复杂度为 $O(k)$ ，其中 $k$ 是队列的容量。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

class MyCircularDeque:
    def __init__(self, k: int):
        """
        Initialize your data structure here. Set the size of the deque to be k.
        """
        self.q = [0] * k
        self.front = 0
        self.size = 0
        self.capacity = k

    def insertFront(self, value: int) -> bool:
        """
        Adds an item at the front of Deque. Return true if the operation is successful.
        """
        if self.isFull():
            return False
        if not self.isEmpty():
            self.front = (self.front - 1 + self.capacity) % self.capacity
        self.q[self.front] = value
        self.size += 1
        return True

    def insertLast(self, value: int) -> bool:
        """
        Adds an item at the rear of Deque. Return true if the operation is successful.
        """
        if self.isFull():
            return False
        idx = (self.front + self.size) % self.capacity
        self.q[idx] = value
        self.size += 1
        return True

    def deleteFront(self) -> bool:
        """
        Deletes an item from the front of Deque. Return true if the operation is successful.
        """
        if self.isEmpty():
            return False
        self.front = (self.front + 1) % self.capacity
        self.size -= 1
        return True

    def deleteLast(self) -> bool:
        """
        Deletes an item from the rear of Deque. Return true if the operation is successful.
        """
        if self.isEmpty():
            return False
        self.size -= 1
        return True

    def getFront(self) -> int:
        """
        Get the front item from the deque.
        """
        if self.isEmpty():
            return -1
        return self.q[self.front]

    def getRear(self) -> int:
        """
        Get the last item from the deque.
        """
        if self.isEmpty():
            return -1
        idx = (self.front + self.size - 1) % self.capacity
        return self.q[idx]

    def isEmpty(self) -> bool:
        """
        Checks whether the circular deque is empty or not.
        """
        return self.size == 0

    def isFull(self) -> bool:
        """
        Checks whether the circular deque is full or not.
        """
        return self.size == self.capacity


# Your MyCircularDeque object will be instantiated and called as such:
# obj = MyCircularDeque(k)
# param_1 = obj.insertFront(value)
# param_2 = obj.insertLast(value)
# param_3 = obj.deleteFront()
# param_4 = obj.deleteLast()
# param_5 = obj.getFront()
# param_6 = obj.getRear()
# param_7 = obj.isEmpty()
# param_8 = obj.isFull()

speed

复杂度分析

指标	值
时间	O(1)
空间	O(k)

psychology

面试官常问的追问

外企场景

question_mark
The candidate should demonstrate knowledge of linked-list pointer manipulation, especially handling both ends of a deque.
question_mark
Look for an understanding of circular structures and how they impact space and time complexity.
question_mark
Candidates who can explain efficient handling of boundary conditions (overflow and underflow) will show solid problem-solving skills.

warning

常见陷阱

外企场景

error
Forgetting to update both `next` and `prev` pointers correctly when inserting or deleting elements.
error
Not handling the circular nature of the deque properly, especially with the front and rear pointers.
error
Failing to efficiently manage the size of the deque, leading to overflow or underflow errors.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Implementing a deque using arrays or other data structures for comparison of space and time efficiency.
arrow_right_alt
Designing a fixed-size deque with resizing capabilities when full or empty.
arrow_right_alt
Optimizing memory usage by adjusting node structure or implementing a static array-based deque.

help

常见问题

外企场景

继续练习

#622 设计循环队列 #705 设计哈希集合 #706 设计哈希映射