A queue enforces a simple rule: the first item added is the first item removed. This is FIFO - First In, First Out. The reason this matters is that many real problems depend on processing things in the order they arrive. A print queue sends documents to the printer in submission order. A web server handles requests in the order they reach the server. A breadth-first search explores nodes in the order they were discovered. All of these rely on the same underlying structure.

A queue supports two core operations:

• Enqueue - add an item to the back of the queue
• Dequeue - remove an item from the front of the queue

Both operations must run in O(1) time. If either operation is slower than constant time, the queue becomes a bottleneck in any algorithm that depends on it.

Why Python Lists Are the Wrong Choice

Your first instinct might be to use a Python list as a queue. Appending to the end is O(1), so enqueue works fine. But removing from the front with list.pop(0) is O(n) - Python shifts every remaining element left by one position. For a queue with 100,000 elements, every dequeue operation copies 99,999 elements. This turns an O(n) BFS into O(n squared).

The fix is collections.deque, which is implemented as a doubly-linked list of fixed-size blocks. Both append (enqueue) and popleft (dequeue) run in O(1):

BFS: The Queue Algorithm

Breadth-first search is the most important application of queues. The idea is straightforward: start at a source node, explore all its neighbors first, then explore all neighbors of those neighbors, and so on. The queue ensures you process nodes in the order they were discovered - which means you explore level by level.

Here is BFS on a binary tree to collect nodes level by level:

The key insight is the level_size variable. At the start of each iteration, every node currently in the queue belongs to the same level. By processing exactly that many nodes before moving on, you separate the tree into distinct levels. Without this trick, you would process all nodes correctly but lose track of which level each node belongs to.

See how BFS spreads outward from multiple sources simultaneously in a grid:

Why BFS Finds the Shortest Path

In an unweighted graph, BFS guarantees the shortest path from the source to every reachable node. The reason is the queue's FIFO property: nodes at distance 1 are processed before nodes at distance 2, which are processed before nodes at distance 3. By the time you reach a node, you have already explored all shorter paths. No backtracking or re-evaluation needed.

This property makes BFS the foundation for shortest-path problems in unweighted graphs, level-order traversal in trees, and even state-space exploration in puzzles like word ladders and sliding tiles.