Implement a circular queue

Easy

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]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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; }
}