Design Circular Deque

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

1. 1In the constructor, allocate an array of length k, set front to 0, and set size to 0.
2. 2For insertFront, fail if full; otherwise move front backward with (front - 1 + capacity) % capacity, store the value there, and increment size.
3. 3For insertLast, fail if full; otherwise compute rear = (front + size) % capacity, store the value there, and increment size.
4. 4For deleteFront, fail if empty; otherwise advance front with (front + 1) % capacity and decrement size.
5. 5For deleteLast, fail if empty; otherwise just decrement size, leaving the slot to be overwritten later.
6. 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