Design Circular Queue

medium queue array design

Problem

Design your own circular queue supporting enQueue, deQueue, Front, Rear, isEmpty, isFull. A circular queue wraps around — enqueue at the tail and dequeue at the head, both in O(1).

Operationsk=3, enQueue 1, enQueue 2, enQueue 3, deQueue, enQueue 4, Rear

Outputtrue, true, true, true, true, 4

The tail index wraps around modulo k after the dequeue makes a slot free.

capacity k

operations (semicolon-separated)

class MyCircularQueue:
    def __init__(self, k):
        self.q = [0] * k
        self.head = 0
        self.tail = 0
        self.size = 0
        self.k = k
    def enQueue(self, v):
        if self.size == self.k: return False
        self.q[self.tail] = v
        self.tail = (self.tail + 1) % self.k
        self.size += 1
        return True
    def deQueue(self):
        if self.size == 0: return False
        self.head = (self.head + 1) % self.k
        self.size -= 1
        return True
    def Front(self):
        return -1 if self.size == 0 else self.q[self.head]
    def Rear(self):
        return -1 if self.size == 0 else self.q[(self.tail - 1) % self.k]

class MyCircularQueue {
  constructor(k) { this.q = new Array(k).fill(0); this.head = 0; this.tail = 0; this.size = 0; this.k = k; }
  enQueue(v) {
    if (this.size === this.k) return false;
    this.q[this.tail] = v;
    this.tail = (this.tail + 1) % this.k;
    this.size++;
    return true;
  }
  deQueue() {
    if (this.size === 0) return false;
    this.head = (this.head + 1) % this.k;
    this.size--;
    return true;
  }
  Front() { return this.size === 0 ? -1 : this.q[this.head]; }
  Rear()  { return this.size === 0 ? -1 : this.q[(this.tail - 1 + this.k) % this.k]; }
}

class MyCircularQueue {
    int[] q; int head, tail, size, k;
    public MyCircularQueue(int k) { this.k = k; q = new int[k]; }
    public boolean enQueue(int v) {
        if (size == k) return false;
        q[tail] = v;
        tail = (tail + 1) % k;
        size++;
        return true;
    }
    public boolean deQueue() {
        if (size == 0) return false;
        head = (head + 1) % k;
        size--;
        return true;
    }
    public int Front() { return size == 0 ? -1 : q[head]; }
    public int Rear()  { return size == 0 ? -1 : q[(tail - 1 + k) % k]; }
}

class MyCircularQueue {
    vector<int> q;
    int head = 0, tail = 0, sz = 0, k;
public:
    MyCircularQueue(int kk) : q(kk), k(kk) {}
    bool enQueue(int v) {
        if (sz == k) return false;
        q[tail] = v;
        tail = (tail + 1) % k;
        sz++;
        return true;
    }
    bool deQueue() {
        if (sz == 0) return false;
        head = (head + 1) % k;
        sz--;
        return true;
    }
    int Front() { return sz == 0 ? -1 : q[head]; }
    int Rear()  { return sz == 0 ? -1 : q[(tail - 1 + k) % k]; }
};

Explanation

A circular queue stores its items in a fixed-size array and lets the front and back wrap around to reuse freed slots. The whole trick is modulo arithmetic on two pointers plus a size counter, so both enqueue and dequeue stay O(1).

We keep head (where the next item leaves), tail (where the next item is written), and size. To enQueue we write at q[tail], then advance tail = (tail + 1) % k so it loops back to 0 after the last slot. To deQueue we just advance head = (head + 1) % k and shrink size; the old value is simply ignored.

The size counter is what makes "full" and "empty" unambiguous: isFull is size == k and isEmpty is size == 0. Front reads q[head], and Rear reads q[(tail - 1 + k) % k], stepping one slot back from tail with a +k guard so it never goes negative.

Example: k = 3, enqueue 1, 2, 3 (now full), dequeue (frees index 0), then enqueue 4. The tail wraps to index 0 and stores 4, so Rear returns 4.

Every operation is a couple of array accesses and a modulo, so each is O(1), using O(k) space.

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