Wiring history and queue
Wire history and queue into main.go.
$ algo history -n 4
viewing:
→ Gubątėva
→ Pūlolė
→ Pugopa
→ Šąguke Gako
history holds 4
undo:
← Šąguke Gako
← Pugopa
← Pūlolė
← Gubątėva
history holds 0
Back out in exactly the reverse order. That is the whole of a stack.
In a real system: the queue that finds a route
The transit planner has a graph of 1,531 stops and 2,190 connections — the
Vilnius network. For "what is the fewest stops from A to B" it runs a
breadth-first search, and BFS is driven by a queue: take a stop, look at its
neighbours, put them on the back of the queue, repeat.
Our capture puts that at 5.8–8.3 µs per query.
That is a small number, and it should be read correctly: the queue is not a bottleneck here and nobody is optimising it. But the structure is doing real work in a real system — it is what decides the order stops are visited in, and that order is why BFS finds the shortest route rather than just a route.
Swap the queue for a stack and you get depth-first search — a correct program answering a different question. You will build both in lesson 14.
BFS in transit is written iteratively, with an explicit queue, not with
recursion. Why it is written that way is lesson 5, which begins with this stack.