Implement a queue from scratch

Easy

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]

Your solution ✓ Solved

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