Stacks, queues and linked lists · Lesson 12 of 23
Queues and deques
First in, first out, why `shift()` slows code down, and deques for sliding windows.
A queue is a line: join at the back, leave from the front (FIFO). It powers BFS, job queues, and anything served in order.
A classic JavaScript trap: arr.shift() removes the first element but shifts all the rest: O(n). Use it in a BFS over 100,000 items and you get O(n²).
// A queue with O(1) dequeue: keep a head index instead of shifting
class Queue {
constructor() { this.items = []; this.head = 0 }
enqueue(x) { this.items.push(x) }
dequeue() { return this.items[this.head++] }
get size() { return this.items.length - this.head }
}
const q = new Queue()
q.enqueue("Mona"); q.enqueue("Omar"); q.enqueue("Laila")
console.log(q.dequeue(), q.dequeue(), q.size)enqueue at the back
[Mona, Omar, Laila]
dequeue from the front
Deque: both ends
A deque (double-ended queue) adds and removes at both ends. Its star use: the maximum of every window of size k. Keep indexes whose values decrease: anything smaller than the newcomer is useless (the newcomer is bigger and lives longer), so drop it from the back; anything that slid out of the window drops from the front. The maximum is always first.
function windowMax(nums, k) {
const dq = [], out = []
let head = 0
for (let i = 0; i < nums.length; i++) {
while (dq.length > head && nums[dq[dq.length - 1]] <= nums[i]) dq.pop() // drop smaller from the back
dq.push(i)
if (dq[head] <= i - k) head++ // drop the expired front
if (i >= k - 1) out.push(nums[dq[head]])
}
return out
}
console.log(windowMax([1, 3, -1, -3, 5, 3, 6, 7], 3))Quick question
An empty queue: enqueue(1), enqueue(2), dequeue(), enqueue(3), dequeue(). What did the last dequeue return?
Exercise
Use the Queue class (included) to simulate a ticket line: each person needs some tickets, buys one, and rejoins the back if they still need more. Print the order people finish. It must print Omar Mona Laila.
Expected output: Omar Mona Laila
class Queue {
constructor() { this.items = []; this.head = 0 }
enqueue(x) { this.items.push(x) }
dequeue() { return this.items[this.head++] }
get size() { return this.items.length - this.head }
}
const q = new Queue()
q.enqueue({ name: "Mona", need: 2 })
q.enqueue({ name: "Omar", need: 1 })
q.enqueue({ name: "Laila", need: 3 })
const done = []
// your loop here
console.log(done.join(" "))Practise on real problems
Practice problems that use what you learned here. Solve them in JavaScript, Python or C++.
Learn more from
Played 0 of 2 games
Sign in to save your progress and earn XP.