Design your implementation of a circular queue with enQueue, deQueue, Front, Rear, isEmpty, and isFull operations.
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
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].
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)