Design Circular Deque: Array-Based Ring Buffer

Think of a conveyor belt at an airport baggage carousel. Bags can be loaded from either end and passengers can grab them from either end too. That is the idea behind a double-ended queue, or deque. Design Circular Deque is LeetCode problem 641. You need to build a deque with a fixed capacity backed by a circular array, where both the front and the rear support insertion and deletion in O(1) time.

Why this problem matters

Most queue problems only require insertion at one end and removal at the other. A deque doubles the surface area: you need to handle four operations (insertFront, insertLast, deleteFront, deleteLast) while keeping the same O(1) performance guarantees. This forces you to really understand how circular indexing works in both directions, not just forward.

The circular deque also shows up as a building block in sliding window problems (Python's collections.deque is a deque under the hood) and in system-level designs like work-stealing schedulers where threads pull tasks from both ends of a shared queue.

The approach

The strategy is almost identical to the circular queue (LeetCode 622), but with two extra operations that move pointers backward instead of forward.

You maintain three pieces of state alongside the array:

1. front - the index of the first element in the deque
2. rear - the index of the slot just past the last element (where the next insertLast would go)
3. count - how many elements are currently in the deque

The key insight is directional pointer arithmetic:

• Moving forward (insertLast, deleteFront): (index + 1) % k
• Moving backward (insertFront, deleteLast): (index - 1 + k) % k

The + k in the backward formula prevents negative indices. Without it, (0 - 1) % k could produce -1 in some languages. Adding k before the modulo guarantees a non-negative result.

On insertFront: move front one step backward, then place the value at the new front index.

On insertLast: place the value at rear, then move rear one step forward.

On deleteFront: move front one step forward. The old value will be overwritten later.

On deleteLast: move rear one step backward. The old value will be overwritten later.

The solution

class MyCircularDeque:
    def __init__(self, k):
        self.data = [0] * k
        self.size = k
        self.front = 0
        self.rear = 0
        self.count = 0

    def insertFront(self, value):
        if self.isFull():
            return False
        self.front = (self.front - 1 + self.size) % self.size
        self.data[self.front] = value
        self.count += 1
        return True

    def insertLast(self, value):
        if self.isFull():
            return False
        self.data[self.rear] = value
        self.rear = (self.rear + 1) % self.size
        self.count += 1
        return True

    def deleteFront(self):
        if self.isEmpty():
            return False
        self.front = (self.front + 1) % self.size
        self.count -= 1
        return True

    def deleteLast(self):
        if self.isEmpty():
            return False
        self.rear = (self.rear - 1 + self.size) % self.size
        self.count -= 1
        return True

    def getFront(self):
        if self.isEmpty():
            return -1
        return self.data[self.front]

    def getRear(self):
        if self.isEmpty():
            return -1
        return self.data[(self.rear - 1 + self.size) % self.size]

    def isEmpty(self):
        return self.count == 0

    def isFull(self):
        return self.count == self.size

Let's break down the important details:

1. insertFront: moves front backward first, then writes. This is the opposite order from insertLast, which writes first and then moves rear forward. Getting this order wrong causes elements to overwrite each other.

2. insertLast: identical to the circular queue's enQueue. Write at rear, advance rear.

3. deleteFront: identical to the circular queue's deQueue. Advance front, decrement count.

4. deleteLast: moves rear backward. The element at the new rear position is logically removed. It will be overwritten by a future insertLast.

5. getRear(): the last inserted element sits at (rear - 1 + k) % k, just like the circular queue's Rear() method.

Step-by-step walkthrough

Let's trace through a sequence of operations on a circular deque with capacity 3. Pay attention to how front and rear move in opposite directions, and how the wrap-around works when inserting at the front.

The critical moment is Step 7. After deleteLast freed up index 1, the insertFront of 9 moves the front pointer backward from index 2 to index 1. The value 9 lands at index 1 even though the front was previously at index 2. That backward movement is what distinguishes a deque from a plain circular queue.

Complexity analysis

Time: every operation performs a constant number of array accesses and arithmetic operations. No loops, no scanning.

Space: the array has exactly k slots. The three integer variables (front, rear, count) add O(1) overhead.

Edge cases to watch for

Before submitting, verify your solution handles these:

• Deque of capacity 1. insertFront, then insertLast should fail (and vice versa). deleteFront and deleteLast both remove the same single element. getFront and getRear return the same value.
• Empty deque operations. deleteFront, deleteLast, getFront, and getRear on an empty deque must all return False or -1 respectively. Forgetting the empty check causes stale-data bugs.
• Full deque after mixed operations. Fill the deque using a mix of insertFront and insertLast, then verify isFull returns True. The front and rear pointers may not be in the positions you expect after alternating front and rear insertions.
• getRear() when rear is 0. After a wrap-around, rear points to index 0. getRear must compute (0 - 1 + k) % k = k - 1 to find the last inserted element.
• Alternating front and rear operations. insertFront(1), insertLast(2), deleteFront, insertFront(3), deleteLast. The pointers bounce in both directions. Make sure the count stays consistent and isEmpty/isFull report correctly.

The building blocks

This problem exercises two fundamental patterns:

Bidirectional modular arithmetic

The circular queue only needs forward pointer movement: (index + 1) % k. The deque adds the backward direction: (index - 1 + k) % k. Together, these two expressions form the complete toolkit for circular buffer navigation. You will see this same arithmetic in problems involving circular arrays, rotating arrays, and the Josephus problem.

Fixed-capacity design with a count variable

Using a count variable to track the number of elements avoids the classic ambiguity where front == rear could mean either "empty" or "full." The count makes isEmpty and isFull trivial one-liners. This pattern applies to any bounded data structure where you need to distinguish between the two states.

From understanding to recall

The circular deque adds a layer of complexity on top of the circular queue. You now have four mutation operations instead of two, and the backward index arithmetic introduces a new source of off-by-one errors. Does insertFront move front before writing or after? Does deleteLast move rear before or after? Is the formula (index - 1 + k) % k or (index - 1) % k?

These are exactly the kinds of details that slip away between study sessions. The code is about 40 lines, but every line carries weight. Spaced repetition drilling forces you to reconstruct the implementation from scratch at increasing intervals, turning these pointer mechanics into muscle memory. When the interview clock is ticking, you want the bidirectional modular arithmetic to feel automatic.

Related posts

• Design Circular Queue - The single-ended version of this problem, which shares the same circular array foundation
• Implement Queue Using Stacks - Another queue design problem where you build a FIFO structure from limited primitives
• LRU Cache - A harder design problem that also manages fixed-capacity storage with specific eviction rules