Stop 21 · Data Structures & AlgorithmsTopics · 5/17

Queue

In short

First come, first served. Queues power task schedulers, print jobs and, most importantly for interviews, breadth-first search on trees and graphs.

A First-In-First-Out (FIFO) data structure — the natural fit for breadth-first traversal, task scheduling, and processing items in arrival order.

The jaadu hands a ticket to the first person in a short line at a railway counter.

Think of it like this

The railway ticket counter line

New people join at the back, and the clerk serves whoever is at the front. Nobody jumps the line (in theory). That's FIFO: first in, first out.

Watch it happen

First in, first out with a head index

enqueue(A)

Front of the queue is coloured

1/6enqueue(A): A joins at the back. head is 0.

The big ideas

What you need to know

Add at the back, remove at the front

enqueue adds to the rear, dequeue takes from the front. Both should be O(1).

array.shift() is not free

shift moves every remaining item forward, so it's O(n). Fine for small inputs, slow for huge ones.

Use a head index

Keep the array and just move a head pointer forward. Dequeue becomes O(1).

Queues drive BFS

Breadth-first search visits things level by level, and a queue keeps that order for you.

See it in code

Walk through the code

1class Queue {2  constructor() {3    this.items = [];4    this.head = 0;5  }6  enqueue(x) { this.items.push(x); }7  dequeue() {8    if (this.head === this.items.length) return undefined;9    return this.items[this.head++];10  }11  get size() { return this.items.length - this.head; }12}

1/4A plain array plus a head index that marks the front.

dequeue just reads at head and moves the index, so both operations are O(1). The trade-off: old items aren't freed until you reset the array.

Save yourself the pain

Common mistakes

Oops

Calling shift() inside a BFS over a grid with lakhs of cells.

Do this instead

Use a head index, or swap the queue for a fresh array each level.

Oops

Mixing up stack and queue when doing level-order traversal.

Do this instead

A queue gives level order (BFS). A stack gives depth-first order (DFS).

Your mission

Queue drills

~30 min

Quick check

You enqueue A, B, C, then dequeue twice. What's left in the queue?

Go deeper

1Implement a queue from scratch and compare its operations to a stack's.
2Use a queue to implement breadth-first search (BFS) on a graph or tree.
3Learn about circular queues and deques (double-ended queues) as variants.