Queue

Process work in first-in, first-out order. Queues are the missing linear-structure foundation behind BFS, buffering, and fair scheduling.

queue

fifo

bfs

linear

Interactive visualization

Use the controls to connect the idea to concrete operations before diving into the full write-up.

Step 1 / 6

front

empty queue

back

Start empty

A queue processes items in first-in, first-out order.

Why queues matter

Queues model fair processing. The oldest item gets handled first, which is exactly why BFS discovers nodes level by level, schedulers process jobs in arrival order, and streaming systems buffer work without reordering it.

Family

Linear structures

State that flows from one end to the other: lists, deques, stacks, and windows.

Builds on

Foundational

You can start here without another page first.

Unlocks

3 next topics

Use these follow-ups when you want to apply the current idea in a richer setting.

Learning paths

This topic appears in curated progressions so you can keep moving without guessing the next step.

Problem

You need to process items in the same order they arrive.

Examples:

users waiting in line
tasks waiting for a worker
nodes waiting for breadth-first exploration
packets waiting inside a buffer

A stack is wrong because it reverses the order. A queue keeps the oldest item at the front.

Core idea

A queue supports two main operations:

enqueue(x) inserts at the back
dequeue() removes from the front

That makes it a FIFO structure: first in, first out.

Why it matters

Queues are simple, but they unlock a surprising amount of the atlas:

BFS depends on a queue to expand the graph one layer at a time
Deque generalizes a queue by allowing work at both ends
Monotonic queue builds on queue order plus a dominance rule

Without a queue, breadth-first processing has no clean data structure behind it.

Implementations

Array with head pointer

Fast and compact if you avoid shifting all elements on every pop.

Circular buffer

The classic fixed-capacity queue. Head and tail wrap around.

Linked list

Useful when dynamic growth matters and you want $O(1)$ insertion/removal at both logical ends.

Complexity

Operation	Time
Enqueue	$O(1)$
Dequeue	$O(1)$
Front	$O(1)$

Common mistakes

Using an array and calling a full left-shift on every dequeue
Reaching for a deque when a plain queue would be clearer
Forgetting that FIFO order is the reason BFS gives shortest paths in unweighted graphs

Key takeaways

A queue is the canonical FIFO structure
It is the missing conceptual step between linked lists and graph traversal
BFS is not just “a graph algorithm”; it is graph traversal powered by queue discipline
Deque and monotonic queue both make more sense once the plain queue comes first

Practice problems

Problem	Difficulty	Key idea
Number of Recent Calls	🟢 Easy	Keep only active items in FIFO order
Implement Stack using Queues	🟡 Medium	Understand exactly what FIFO gives you
Open the Lock	🟡 Medium	BFS frontier is literally a queue