Implement a queue from scratch
Problem
Implement a queue (FIFO) with enqueue, dequeue, front, isEmpty and size, where every operation is O(1). A plain array with shift() is O(n) per dequeue.
Example 1
Input: enqueue(1), enqueue(2), dequeue(), front() Output: 1, 2
Also asked as: Implement Queue from Scratch
Test cases
Case 1
Input: new Queue() .enqueue(1) .enqueue(2) .dequeue() .front() .isEmpty() Expected: [null,null,1,2,false]
Case 2
Input: new Queue() .enqueue(7) .dequeue() .isEmpty() .enqueue(8) .front() Expected: [null,7,true,null,8]
Case 3
Input: new Queue() .isEmpty() .dequeue() .front() Expected: [true,null,null]
View solutionHide solution1 approach
1. Circular buffer
Time O(1) per opSpace O(capacity)
Fixed array with head/tail indices modulo capacity; O(1) enqueue/dequeue with no shifting.
class Queue { constructor(cap = 1024) { this.a = new Array(cap); this.head = 0; this.tail = 0; this.count = 0; this.cap = cap; } enqueue(x) { if (this.count === this.cap) throw new Error('full'); this.a[this.tail] = x; this.tail = (this.tail + 1) % this.cap; this.count++; } dequeue() { if (!this.count) return undefined; const x = this.a[this.head]; this.head = (this.head + 1) % this.cap; this.count--; return x; } front() { return this.count ? this.a[this.head] : undefined; } isEmpty() { return this.count === 0; }}