Design Circular Deque

medium design queue array

Problem

Implement insertFront, insertLast, deleteFront, deleteLast, getFront, getRear, isEmpty, isFull on a circular deque.

Inputk=3 ins F(1) ins L(2) ins F(3) ins F(4) get R

OutputFalse then 2

Fourth insert fails; rear is 2.

input

class MyCircularDeque:
    def __init__(self, k): self.a = [0]*k; self.h = 0; self.n = 0; self.k = k
    def insertFront(self, v):
        if self.n == self.k: return False
        self.h = (self.h - 1) % self.k; self.a[self.h] = v; self.n += 1; return True
    def insertLast(self, v):
        if self.n == self.k: return False
        self.a[(self.h + self.n) % self.k] = v; self.n += 1; return True
    def deleteFront(self):
        if self.n == 0: return False
        self.h = (self.h + 1) % self.k; self.n -= 1; return True
    def deleteLast(self):
        if self.n == 0: return False
        self.n -= 1; return True
    def getFront(self): return -1 if self.n == 0 else self.a[self.h]
    def getRear(self): return -1 if self.n == 0 else self.a[(self.h + self.n - 1) % self.k]
    def isEmpty(self): return self.n == 0
    def isFull(self): return self.n == self.k

class MyCircularDeque {
  constructor(k) { this.a = new Array(k); this.h = 0; this.n = 0; this.k = k; }
  insertFront(v) { if (this.n === this.k) return false; this.h = (this.h - 1 + this.k) % this.k; this.a[this.h] = v; this.n++; return true; }
  insertLast(v) { if (this.n === this.k) return false; this.a[(this.h + this.n) % this.k] = v; this.n++; return true; }
  deleteFront() { if (!this.n) return false; this.h = (this.h + 1) % this.k; this.n--; return true; }
  deleteLast() { if (!this.n) return false; this.n--; return true; }
  getFront() { return this.n ? this.a[this.h] : -1; }
  getRear() { return this.n ? this.a[(this.h + this.n - 1) % this.k] : -1; }
  isEmpty() { return this.n === 0; }
  isFull() { return this.n === this.k; }
}

class MyCircularDeque {
    int[] a; int h = 0, n = 0, k;
    public MyCircularDeque(int k) { this.k = k; a = new int[k]; }
    public boolean insertFront(int v) { if (n == k) return false; h = (h - 1 + k) % k; a[h] = v; n++; return true; }
    public boolean insertLast(int v) { if (n == k) return false; a[(h + n) % k] = v; n++; return true; }
    public boolean deleteFront() { if (n == 0) return false; h = (h + 1) % k; n--; return true; }
    public boolean deleteLast() { if (n == 0) return false; n--; return true; }
    public int getFront() { return n == 0 ? -1 : a[h]; }
    public int getRear() { return n == 0 ? -1 : a[(h + n - 1) % k]; }
    public boolean isEmpty() { return n == 0; }
    public boolean isFull() { return n == k; }
}

class MyCircularDeque {
    vector a; int h = 0, n = 0, k;
public:
    MyCircularDeque(int k) : a(k), k(k) {}
    bool insertFront(int v) { if (n == k) return false; h = (h - 1 + k) % k; a[h] = v; n++; return true; }
    bool insertLast(int v) { if (n == k) return false; a[(h + n) % k] = v; n++; return true; }
    bool deleteFront() { if (n == 0) return false; h = (h + 1) % k; n--; return true; }
    bool deleteLast() { if (n == 0) return false; n--; return true; }
    int getFront() { return n == 0 ? -1 : a[h]; }
    int getRear() { return n == 0 ? -1 : a[(h + n - 1) % k]; }
    bool isEmpty() { return n == 0; }
    bool isFull() { return n == k; }
};

Explanation

A circular deque is built on a fixed-size array that "wraps around" using modular arithmetic. Instead of shifting elements when you add or remove at the front, you just move indices and take them % k, so every operation stays O(1).

We track the head index h and the current count n. The front element lives at a[h], and the rear lives at a[(h + n - 1) % k]. Inserting at the front moves the head backward with h = (h - 1) % k; inserting at the back writes to the first empty slot at (h + n) % k.

Capacity checks are simple counter comparisons: insertFront and insertLast return False when n == k (full), while the delete operations return False when n == 0 (empty). Deleting from the front just advances the head; deleting from the back just decrements n.

Example with k = 3: insertFront(1), insertLast(2), insertFront(3) fill the deque so n == 3. A fourth insertFront(4) sees the deque is full and returns False. getRear() reads a[(h + n - 1) % 3], which is 2.

Time: O(1) Space: O(k)