Implement a circular queue
Problem
Implement a fixed-capacity circular queue (ring buffer) with enqueue, dequeue, front, rear, isEmpty and isFull. enqueue and dequeue return whether they succeeded; front and rear return −1 on an empty queue. The front and rear indices wrap around the array.
Example 1
Input: k = 3: enqueue 1, 2, 3, 4 → rear() → isFull() → dequeue() → enqueue(4) → rear() Output: true, true, true, false, 3, true, true, true, 4
Also asked as: Implement a Circular queue
Test cases
Case 1
Input: new CircularQueue(3) .enqueue(1) .enqueue(2) .enqueue(3) .enqueue(4) .rear() .isFull() .dequeue() .enqueue(4) .rear() Expected: [true,true,true,false,3,true,true,true,4]
Case 2
Input: new CircularQueue(2) .enqueue(1) .enqueue(2) .dequeue() .enqueue(3) .front() .rear() .isFull() Expected: [true,true,true,true,2,3,true]
Case 3
Input: new CircularQueue(1) .front() .dequeue() .isEmpty() .enqueue(5) .enqueue(6) .front() .rear() Expected: [-1,false,true,true,false,5,5]
View solutionHide solution1 approach
1. Fixed array with modular head/tail
Time O(1) per opSpace O(capacity)
Wrap indices with `% capacity`; track a count to distinguish full from empty.
class CircularQueue { constructor(k) { this.a = new Array(k); this.k = k; this.head = 0; this.count = 0; } enqueue(x) { if (this.count === this.k) return false; this.a[(this.head + this.count) % this.k] = x; this.count++; return true; } dequeue() { if (!this.count) return false; this.head = (this.head + 1) % this.k; this.count--; return true; } front() { return this.count ? this.a[this.head] : -1; } rear() { return this.count ? this.a[(this.head + this.count - 1) % this.k] : -1; } isFull() { return this.count === this.k; } isEmpty() { return this.count === 0; }}