The first person goes first
Picture
Ana joins a line. Then Bo joins behind her. Ana gets served first. A queue keeps this first-in, first-out order.
Predict
Ana joined before Bo. Who leaves the front of the queue first?
Let's look
Ana. A later arrival doesn’t jump ahead.
A little Python, if you want it
from collections import deque
line = deque(["Ana", "Bo"])
assert line.popleft() == "Ana"
assert list(line) == ["Bo"]Use append to join the back and popleft to leave the front. Python’s deque supports both without shifting all the remaining items.
Change one rule
We serve the newest arrival first instead. Which earlier idea does that resemble?
Let's try it
A stack. Changing which end we use changes the order of work.
Connect
BFS uses a queue to finish the current layer before the next. First, let’s remember what we’ve already seen.