Stack/QueueData structureaka FIFO, first-in first-out

Queue

A first-in, first-out collection: elements enter at the back and leave from the front.

▶ Visualize Pattern: Breadth-First Search Practice (5)

Progress

Definition

A queue supports enqueue (add at the back) and dequeue (remove from the front). Elements leave in the exact order they arrived — FIFO.

A naive array with shift() from the front costs O(n) per dequeue. Correct implementations use a Linked List with head and tail pointers, a Circular Queue over a fixed buffer, or two stacks. All achieve O(1) per operation.

Queues are the engine behind Breadth-First Search (BFS): they guarantee nodes are explored in order of discovery, which is what makes BFS find shortest paths in unweighted graphs.

FIFOO(1)linearBFSscheduling

Intuition

A mental model before the formal terms.

A line at a ticket counter. New people join at the back; the person at the front is served next. Nobody cuts in line, so service order equals arrival order.

A conveyor belt: items placed on one end come off the other end in the same sequence.

How it works

Keep a linked list with head (front) and tail (back) pointers, or an array with head and tail indices.
enqueue(x): create a node, link it after tail, move tail to it (or set both head and tail if empty).
dequeue(): return head value and advance head to head.next; if the list becomes empty, reset tail to null.
peek(): return the value at head without removing it.

Why it works

Maintaining explicit pointers to both ends means neither insertion nor removal has to traverse or shift anything, so each operation is a constant number of pointer updates.

FIFO order is exactly "process things in the order they were discovered", which is the invariant that makes level-order traversal and BFS shortest paths correct: all distance-d nodes are dequeued before any distance-d+1 node.

Operations

Operation	Description	Cost
enqueue(x)	Add x at the back.	O(1)
dequeue()	Remove and return the front element.	O(1)
peek() / front()	Return the front element without removing it.	O(1)
isEmpty()	True when the queue is empty.	O(1)
size()	Number of stored elements.	O(1)

Recognition

How to tell a problem wants this.

The problem mentions level-by-level, shortest path in an unweighted graph, or minimum number of steps.
Tasks must be processed in arrival order: schedulers, message buffers, rate limiters, print jobs.
You are simulating a real queue: sliding time windows of recent events, "hit counter" designs.

“minimum steps” → Breadth-First Search

Interactive demo

Play, step, change the input. ← → and space work too.

Commands — Comma separated: enqueue N, dequeue, peek

1/12A queue is first-in, first-out: elements enter at the back and leave from the front, so the order of arrival is preserved.

Just enqueuedFrontBeing dequeued

PseudocodeLearn Queue →

1enqueue(x): items.append(x)      # at the back
2dequeue(): return items.pop_front()  # from the front
3peek(): return items[front]

Variables

size0

Complexity

access O(n)

search O(n)

insert O(1)

delete O(1)

Speed

Pseudocode

1class Queue:
2  head = null, tail = null, n = 0
3  enqueue(x): node = Node(x); if tail: tail.next = node else head = node; tail = node; n++
4  dequeue(): if empty: error; v = head.val; head = head.next; if head == null: tail = null; n--; return v
5  peek(): return head.val

Implementation

1from typing import Generic, Optional, TypeVar
2 
3T = TypeVar("T")
4 
5 
61 · Node and end pointers
7class _QNode(Generic[T]):
8    __slots__ = ("value", "next")
9 
10    def __init__(self, value: T) -> None:
11        self.value = value
12        self.next: Optional[_QNode[T]] = None
13 
14 
15class Queue(Generic[T]):
16    def __init__(self) -> None:
17        self._head: Optional[_QNode[T]] = None  # front: dequeue here
18        self._tail: Optional[_QNode[T]] = None  # back: enqueue here
19        self._n = 0
20 
212 · Enqueue at the tail
22    def enqueue(self, x: T) -> None:
23        node = _QNode(x)
24        if self._tail is not None:
25            self._tail.next = node
26        else:
27            self._head = node  # was empty: node is both ends
28        self._tail = node
29        self._n += 1
30 
313 · Dequeue from the head
32    def dequeue(self) -> T:
33        if self._head is None:
34            raise IndexError("dequeue from empty queue")
35        value = self._head.value
36        self._head = self._head.next
37        if self._head is None:
38            self._tail = None  # emptied: drop the stale tail
39        self._n -= 1
40        return value
41 
424 · Peek, size, emptiness
43    def peek(self) -> T:
44        if self._head is None:
45            raise IndexError("peek from empty queue")
46        return self._head.value
47 
48    def is_empty(self) -> bool:
49        return self._n == 0
50 
51    def __len__(self) -> int:
52        return self._n

Walkthrough

_QNode uses __slots__ to keep per-node memory down; the leading underscore marks it internal.
enqueue links after _tail or initialises both pointers when empty.
dequeue advances _head and clears _tail when the queue empties; the removed node is garbage-collected.
__len__ lets callers write len(q) and while q: naturally.

Complexity (this implementation)

time O(1) enqueue/dequeue/peek · space O(n)

collections.deque does the same job in C with block allocation — use it in real code; list.pop(0) is O(n).

Language notes

collections.deque is the canonical Python queue: append() to enqueue, popleft() to dequeue, both O(1).
queue.Queue is for *threads* — it adds locking you do not want in single-threaded algorithm code.
This class is didactic; in interviews, saying "I would use deque" and using it is the expected move.

Common mistakes in this language

Using list.pop(0) — every remaining element shifts left, O(n) per dequeue.
Reaching for queue.Queue in an algorithm and paying lock overhead for nothing.
Forgetting to clear _tail on the last dequeue, so the next enqueue appends to a detached node.

Language differences that matter here

Built-ins: C++ std::queue and Python collections.deque are ready-made O(1) queues; JS/TS have none — a naive Array.shift() dequeue is O(n).
Python queue.Queue is a thread-synchronised channel, not an algorithm queue; the JS/TS equivalent trap is shift() in hot loops.
Memory management: the C++ version must delete nodes (destructor) and forbid shallow copies; GC languages only need the pointer logic.
C++ std::queue::pop() returns void; JS/TS/Python dequeues return the removed value.

Complexity

Operation	Average	Worst	Note
Access	O(n)	O(n)	Front is O(1).
Search	O(n)	O(n)
Insert	O(1)	O(1)	Only at the back.
Delete	O(1)	O(1)	Only at the front.
Update	—	—
Enqueue	O(1)	O(1)
Dequeue	O(1)	O(1)
Peek	O(1)	O(1)
Space	O(n)

Advantages & disadvantages

Advantages

Constant-time insert and remove at opposite ends with the right backing store.
Preserves arrival order, giving fairness in scheduling and correctness in BFS.
Simple to reason about; bounded versions naturally provide back-pressure.

Disadvantages

No random access or search better than O(n).
Naive array implementations (shift/pop(0)) degrade to O(n) per dequeue.
Linked-list versions pay per-node allocation and poorer cache locality than arrays.

Use cases

Breadth-first search and level-order tree traversal.
Task scheduling, job queues, producer/consumer pipelines.
Buffering I/O and network packets.
Simulations of waiting lines and time-ordered event processing.

Use it when

Order of processing must equal order of arrival.
Breadth-first exploration: shortest path in unweighted graphs, level-order traversal, multi-source spread (rotting oranges).
Decoupling producers from consumers with a buffer.

Avoid it when

You need to process the most recent item first — use a Stack.
Items have priorities and the highest priority must leave first — use a Priority Queue.
You need efficient push/pop at both ends — use a Deque.

Alternatives

Deque Circular Queue Priority Queue Stack

Compare: Stack vs Queue

Common mistakes

Using list.pop(0) in Python or Array.shift() in JS for a hot loop — both are O(n). Use collections.deque or a head-index.
Forgetting to reset tail when the last element is dequeued, leaving a dangling pointer that corrupts the next enqueue.
In BFS, marking a node visited when it is dequeued instead of when it is enqueued, causing duplicates in the queue.
Iterating a level in BFS without first capturing len(queue), so newly enqueued children are mistaken for the current level.

Interview patterns

BFS level-order traversal: snapshot queue size, process exactly that many nodes per level.
Implement a queue with two stacks: push to in, pop from out, refill out by draining in when empty (amortized O(1)).
Multi-source BFS: enqueue all sources at distance 0 before starting.
Sliding time-window counters: dequeue timestamps older than the window.

Interview questions on this

Choosing between BFS, DFS, Dijkstra and DPAdvanced
Stack versus queueBeginner
Choosing a shortest-path algorithmAdvanced
Union-Find or DFS for connectivity?Advanced

Mock interviews

Course ScheduleIntermediate
Network Delay TimeAdvanced
Number of IslandsIntermediate

Interview problems

Task Schedulermedium Binary Tree Level Order Traversalmedium Word Ladderhard Shortest Path in Binary Matrixmedium Rotting Orangesmedium

Definition

Intuition

How it works

Why it works

Operations

Recognition

Interactive demo

Pseudocode

Implementation

Complexity

Advantages & disadvantages

Use cases

Alternatives

Common mistakes

Interview patterns

Interview problems

Related