Undo, and the office printer
You press Undo in a document. The last thing you did disappears, not the first.
Three people send work to the office printer. The first person to send prints first.
Both keep a list of waiting things. They hand them back in opposite orders. Picking the right one is a choice developers make every week.
By the end of this lesson
Note
I can choose a stack or a queue for a job.
Key words
| Word | What it means | Example |
|---|---|---|
| Stack | a pile where the newest item comes out first | |
| Queue | a line where the oldest item comes out first | |
| Push | to put an item on a stack | history.append(edit) |
| Pop | to take the top item off a stack | history.pop() |
| LIFO | last in, first out: how a stack works | |
| FIFO | first in, first out: how a queue works |
The cells students fill in are left blank in this preview.
A stack gives back the newest first
Think of a pile of plates. You put a plate on top. You take a plate from the top.
A stack works the same way. Putting an item on is a push. Taking the top one off is a pop.
In Python a list is a good stack. append pushes to the end, and pop() takes from the end.
Try it: an undo history
# Each edit is pushed on to the stack as it happens.
history = []
history.append("type Hello")
history.append("make it bold")
history.append("change colour")
print("History:", history)
# Undo takes the newest edit off the top.
last = history.pop()
print("Undo:", last)
print("History now:", history)
# Add a second undo line, then press Run.
Worked example: the undo stack
| Action | Stack afterwards, bottom to top | Comes out |
|---|---|---|
| push "type Hello" | type Hello | nothing |
| push "make it bold" | type Hello, make it bold | nothing |
| push "change colour" | type Hello, make it bold, change colour | nothing |
| pop | type Hello, make it bold | change colour |
| pop | type Hello | make it bold |
The cells students fill in are left blank in this preview.
A queue gives back the oldest first
A queue is a line at a till. You join at the back. The person at the front is served first.
Print jobs, support tickets and parcels to pack all wait in queues. Nobody is skipped.
Python has deque for queues. append adds at the back, and popleft takes from the front.
Try it: a print queue
from collections import deque
# Jobs waiting for the office printer, oldest first.
printer = deque()
printer.append("Amira: invoice")
printer.append("Ben: rota")
printer.append("Chloe: contract")
# The printer always takes the oldest job.
while len(printer) > 0:
job = printer.popleft()
print("Printing", job)
# Append a fourth job before the loop, then press Run.
A common mistake
Warning
Many people think pop() takes the oldest item. On a list it takes the newest, from the end. That is right for a stack and wrong for a queue. For a queue, take from the front with popleft(), or pop(0) on a short list.
Ask which item should come out next
To choose, ask one question: should the newest item come out next, or the oldest?
Newest first means a stack: undo, Back, going back up through folders.
Oldest first means a queue: tickets, orders, messages waiting to be sent. Fair order matters to customers, so most waiting lines at work are queues.