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.)
Code exercise · python
Run this BFS over a small friend network stored as a dict of lists. It records how many introductions away each person is from "you". This exact pattern returns in unit 9 as graph traversal.
Quiz
In BFS, what breaks if you swap the queue for a stack (popleft → pop)?
Problem
Using the friend network from the code above, how many introductions away from "you" is "eli"?
Quiz
Undo history, printer jobs, BFS frontier, bracket matching. Which two use a QUEUE?