145. Why does breadth-first search use a queue, and what is it used for?
EasyQueues
Technical
Show model answer
BFS must finish all vertices at distance d before any at distance d + 1. A FIFO queue gives exactly that: vertices discovered from the current layer are enqueued behind the rest of that layer. Using a stack instead turns it into depth-first search. BFS is O(V + E) time and O(V) space.
Typical uses: shortest paths in unweighted graphs (fewest edges, fewest moves in a puzzle), level-order tree traversal, connected components and flood fill, bipartite checking by two-colouring layers, finding all nodes within k hops in a social or network graph, and multi-source spreading problems such as rotting oranges or distance to the nearest exit.