Queue

A queue is a first-in, first-out structure. The earliest added item is the first item removed.

Queues are important because breadth-first search depends on processing discovered items in the order they were discovered.

Core Idea

The main operations are enqueue and dequeue. In Python algorithm code, collections.deque is the standard tool because it supports efficient appends and pops at both ends.

A queue keeps work fair by not letting newer items jump ahead of older items.

The queue answers the question: “What was discovered earliest among the unfinished work?” This is why it fits layer-by-layer traversal and simulations where order of arrival matters.

Function Contract

process_in_order(graph, start) expects an adjacency list where graph[node] lists the next vertices to visit and start is a key in graph.

It returns nodes in breadth-first processing order. The queue stores discovered but not-yet-processed nodes, and the visited set prevents repeated processing.

Python Example

from collections import deque
 
queue = deque()
queue.append("first")
queue.append("second")
 
item = queue.popleft()

After popleft, item is "first".

BFS Shape

A queue is the core of BFS:

from collections import deque
 
def process_in_order(graph, start):
    queue = deque([start])
    visited = {start}
    order = []
 
    while queue:
        item = queue.popleft()
        order.append(item)
 
        for next_item in graph[item]:
            if next_item not in visited:
                visited.add(next_item)
                queue.append(next_item)
 
    return order

The earliest discovered item is processed first. That creates layers: all items one step away are processed before items two steps away.

Cost in Python

Use deque.popleft() for efficient front removal. Avoid this pattern:

item = values.pop(0)

On a Python list, removing index 0 shifts the remaining elements and costs O(n).

Step-by-Step Trace

If A connects to B and C, the queue starts as [A]. Processing A appends B and C, so the queue becomes [B, C]. B is processed before C because it entered first.

That ordering is the reason a queue supports layer-by-layer traversal.

Common Confusions

A Python list can append at the end, but removing from the front with pop(0) is slow because the remaining elements must shift.

A queue is different from a priority queue. A normal queue removes by arrival order. A priority queue removes by priority.

A queue is also different from a stack. A stack returns the newest item. A queue returns the oldest item.

When To Use It

Use a queue when the algorithm must process work in discovery order, especially in BFS, level-order traversal, simulations, and shortest paths where all edges have equal cost.

Use a priority queue instead when the next item should be chosen by best cost or priority rather than arrival order.

The Main Point

A queue processes work in first-in, first-out order. It is the structure that gives BFS its layer-by-layer behavior.