Design Circular Queue

Share

Design your implementation of a circular queue with enQueue, deQueue, Front, Rear, isEmpty, and isFull operations.

Example 1
MyCircularQueue(3), enQueue(1)→true, enQueue(2)→true, enQueue(3)→true, enQueue(4)→false, Rear()→3, isFull()→true, deQueue()→true, enQueue(4)→true, Rear()→4

Solution Approach

Use an array with head and tail pointers. Wrap around using modulo.

  • Array of size k, head=0, tail=0, size=0.
  • enQueue: if full return false; arr[tail]=val; tail=(tail+1)%k; size++.
  • deQueue: if empty return false; head=(head+1)%k; size--.
  • Front: arr[head]; Rear: arr[(tail-1+k)%k].
Java
class MyCircularQueue {
    int[] q;
    int head, tail, size, cap;

    public MyCircularQueue(int k) { q = new int[k]; cap = k; }
    public boolean enQueue(int val) {
        if (isFull()) return false;
        q[tail] = val; tail = (tail+1)%cap; size++; return true;
    }
    public boolean deQueue() {
        if (isEmpty()) return false;
        head = (head+1)%cap; size--; return true;
    }
    public int Front() { return isEmpty() ? -1 : q[head]; }
    public int Rear() { return isEmpty() ? -1 : q[(tail-1+cap)%cap]; }
    public boolean isEmpty() { return size == 0; }
    public boolean isFull() { return size == cap; }
}
  • Time Complexity: All operations O(1)
  • Space Complexity: O(K)