Exploring in rings
The most important queue in computer science does not hold customers or print jobs. It holds places to explore next.
Say you want everyone within 3 introductions of you in a friend network. The natural order is ring by ring: your direct friends (round 1), then their friends (round 2), then theirs (round 3). That is breadth-first search (BFS), and a queue is the engine that enforces the ring order:
- Put the start in a queue, the frontier.
- Dequeue a person, look at their friends.
- Any friend never seen before: mark seen, record their round, enqueue them.
- Repeat until the queue empties.
FIFO guarantees every round-1 person is processed before any round-2 person, so the first time you reach someone is via a shortest path. (A seen set stops infinite loops when friendships point back.)
BFS over a friend network
The network is a dict mapping each person to their friends, and the search records how many introductions away each person is.
from collections import deque friends = { "you": ["ana", "ben"], "ana": ["you", "cai"], "ben": ["you", "cai", "dee"], "cai": ["ana", "ben"], "dee": ["ben", "eli"], "eli": ["dee"], } frontier = deque(["you"]) seen = {"you"} rounds = {"you": 0} while frontier: person = frontier.popleft() for friend in friends[person]: if friend not in seen: seen.add(friend) rounds[friend] = rounds[person] + 1 frontier.append(friend) for person in ["ana", "cai", "dee", "eli"]: print(person, rounds[person])
Output
ana 1 cai 2 dee 2 eli 3
Three collections do three separate jobs. frontier holds places still to explore, seen prevents revisiting, and rounds records the answer.
The line rounds[friend] = rounds[person] + 1 is where distance accumulates. A newly discovered person is exactly one step further than whoever introduced them, and because the frontier is FIFO, that introduction always comes from the closest possible person.
The seen set is what keeps this terminating. Friendships point both ways here, so ana lists you, and without the check the search would bounce between them indefinitely.
This exact pattern returns in unit 9 as graph traversal, where the friend network becomes an adjacency list and nothing else about the code changes.
Swapping the queue for a stack means exploring newest-first, diving deep down one path before finishing nearby ones, so the recorded rounds stop meaning shortest distance.
A stack pops the most recently added place, so the search plunges along a single chain of friends as far as it goes before backing up. Numbers still get recorded, but they count the steps of whatever winding route happened to arrive first rather than the shortest one.
That variant has a name and genuine uses. It is depth-first search, DFS, and lesson 9-3 builds it deliberately.
Only FIFO processes ring k completely before ring k+1, which is what makes BFS's first arrival at a person a shortest path. Everything still terminates in either version, since seen does that job independently of the ordering.
Eli is 3 introductions away from you.
The chain runs you to ben in round 1, ben to dee in round 2, and dee to eli in round 3. No shorter route exists, because eli is reachable only through dee, and dee is reachable only through ben.
The guarantee is stronger than this one example, though. Because BFS finishes every person at distance k before starting on distance k+1, the round number recorded on first arrival is always the shortest possible chain.
That property is what makes BFS worth its queue. A search in some other order would still find eli, but the number it reported would be the length of the path it happened to take rather than the best one.
The two that use a queue are printer jobs and the BFS frontier.
Both need oldest-first service. The printer respects arrival order, and BFS needs ring-by-ring exploration, which means every place discovered earlier must be processed before anything discovered later.
The other two need newest-first. Undo history reverses the latest edit, and bracket matching closes the latest opener, so both are stacks.
Applying the newest-or-oldest test to the BFS case is worth doing slowly, since it is the least obvious of the four. Round-1 people were all discovered before any round-2 person, so serving oldest first is exactly what keeps the rounds honest.