MediumArrayLinked ListDesignQueue

Design Circular Deque

1 approach, code in every language

Design a double-ended queue with a fixed capacity, commonly called a circular deque. It is created with a maximum size k and must support inserting and removing elements at both ends while never exceeding that capacity.

Implement the MyCircularDeque class with these operations: the constructor MyCircularDeque(k) sets the capacity; insertFront(value) and insertLast(value) add an element at the front or back and return whether the operation succeeded; deleteFront() and deleteLast() remove from the front or back and return whether the operation succeeded; getFront() and getRear() return the front or rear element (or -1 when empty); isEmpty() and isFull() report the current state.

Every operation must run in constant time.

Example 1

Input: ["MyCircularDeque","insertLast","insertLast","insertFront","insertFront","getRear","isFull","deleteLast","insertFront","getFront"] [[3],[1],[2],[3],[4],[],[],[],[4],[]]

Output: [null,true,true,true,false,2,true,true,true,4]

Capacity 3. insertLast(1) and insertLast(2) succeed, insertFront(3) succeeds, insertFront(4) fails because it is full; getRear() is 2, isFull() is true; deleteLast() removes 2; insertFront(4) succeeds; getFront() is 4.

Example 2

Input: ["MyCircularDeque","insertFront","getFront","isEmpty","deleteFront","isEmpty"] [[1],[8],[],[],[],[]]

Output: [null,true,8,false,true,true]

Capacity 1. insertFront(8) succeeds, getFront() is 8, isEmpty() is false; after deleteFront() the deque is empty again.

Constraints

1 <= k <= 1000
0 <= value <= 1000
At most 2000 calls will be made to insertFront, insertLast, deleteFront, deleteLast, getFront, getRear, isEmpty, and isFull.

Fixed Array With Modular Indices

Back the deque with an array of capacity k, tracking a front index and a size counter so both ends wrap around modulo the capacity.

Loading animation…

Intuition

A ring buffer gives us constant-time access at both ends without shifting elements. We store the position of the current front element and how many elements are present; the rear position is derived as (front + size - 1) modulo capacity. Inserting at the front moves the front index one step backward (with wraparound), while inserting at the back writes at the slot just past the current rear. Deletions simply advance the front or shrink the size, since stale slots get overwritten by future inserts. A size counter cleanly distinguishes the empty and full states, which a bare pair of pointers cannot do on its own.

Algorithm walkthrough

1In the constructor, allocate an array of length k, set front to 0, and set size to 0.
2For insertFront, fail if full; otherwise move front backward with (front - 1 + capacity) % capacity, store the value there, and increment size.
3For insertLast, fail if full; otherwise compute rear = (front + size) % capacity, store the value there, and increment size.
4For deleteFront, fail if empty; otherwise advance front with (front + 1) % capacity and decrement size.
5For deleteLast, fail if empty; otherwise just decrement size, leaving the slot to be overwritten later.
6getFront and getRear return -1 when empty, else read data[front] and data[(front + size - 1) % capacity]; isEmpty and isFull compare size against 0 and capacity.

Implementation

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

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

    def insertLast(self, value: int) -> bool:
        if self.isFull():
            return False
        rear = (self.front + self.size) % self.capacity
        self.data[rear] = value
        self.size += 1
        return True

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

    def deleteLast(self) -> bool:
        if self.isEmpty():
            return False
        self.size -= 1
        return True

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

    def getRear(self) -> int:
        if self.isEmpty():
            return -1
        return self.data[(self.front + self.size - 1) % self.capacity]

    def isEmpty(self) -> bool:
        return self.size == 0

    def isFull(self) -> bool:
        return self.size == self.capacity

Time

O(1) per operation

Space

O(k)

The backing array is allocated once with capacity k; every insert, delete, and query touches only a constant number of slots.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Stacks & Queues

After the pattern

Now solve one you haven't seen.

Reading a pattern isn't the same as using it. The practice set has 1,194 original problems on the same techniques, each graded in your browser.

Open the practice set Start the FDE path

1,194 problems · 15,062 graded tests · free