Unit 21: Stacks & Queues
Rules about which end you touch.
Unit 21 of 31 in Python for kids. Its 5 lessons are Boxes in a Row, Stacks, Stacks at Work, Queues and Stack & Queue Master — below is everything each one explains, and a question or two from it to try.
Every sample on this page was run through real Python before it shipped, and prints exactly what it says it prints.
This unit opens with a fortnight’s trial of everything — no card needed — or with a family plan, bought in the iPhone app. The first two units of every track are free for ever. Try it in the app.
🗄️ Boxes in a Row
Why lists find things instantly
An array is a row of boxes, all the same size, side by side. Because they are in a row, the computer works out where box 5 is with a sum — it never has to look through the first four. Python lists work this way.
Python
pets = ["cat", "dog", "cow", "hen"]
print(pets[2])
print(len(pets))It prints
cow 4
The cost of squeezing one in
Adding to the end is cheap. Inserting at the front means shifting every other item along one box to make room — which is why it gets slower the longer the list is.
Python
pets = ["dog", "cow"]
pets.append("hen")
print(pets)
pets.insert(0, "cat")
print(pets)It prints
['dog', 'cow', 'hen'] ['cat', 'dog', 'cow', 'hen']
A grid is a list of lists
Put lists inside a list and you have a 2D array — a grid. The first number picks the row, the second picks the column.
Python
grid = [
[1, 2, 3],
[4, 5, 6],
]
print(grid[0][2])
print(grid[1][0])
for row in grid:
print(row)It prints
3 4 [1, 2, 3] [4, 5, 6]
Try it yourself
Why is pets[500] just as fast as pets[0]?
- Python remembers every item
- The boxes are in a row, so the position can be worked out with a sum
- It is not, it is slower
- Because lists are short
What does this print?
Python
grid = [[1, 2], [3, 4]]
total = 0
for row in grid:
for cell in row:
total = total + cell
print(total)Answer them in the app
🥞 Stacks
Last in, first out
A stack is a pile of plates. You add to the top and take from the top — the last thing in is the first thing out. A Python list is already a stack: append puts on, pop takes off.
Python
stack = []
stack.append("a")
stack.append("b")
stack.append("c")
print(stack)
print(stack.pop())
print(stack)It prints
['a', 'b', 'c'] c ['a', 'b']
Looking without taking
The last item is [-1]. Reading it leaves the stack alone — useful when you want to check before you commit.
Python
stack = ["a", "b"]
print(stack[-1])
print(len(stack))It prints
b 2
Popping an empty stack
Taking from an empty stack raises IndexError, so always check it is not empty first. An empty list is falsy, which makes that check short.
Python
stack = []
if stack:
print(stack.pop())
else:
print("nothing to take")It prints
nothing to take
Try it yourself
You push 1, then 2, then 3 onto a stack. What comes off first?
- 1
- 2
- 3
- Whichever you ask for
What does this print?
Python
stack = []
for n in [1, 2, 3]:
stack.append(n)
print(stack.pop())
print(stack.pop())Answer them in the app
🔙 Stacks at Work
The undo button is a stack
Every action goes on a stack. Undo takes the top one off — which is exactly the last thing you did.
Python
history = []
history.append("typed hello")
history.append("made it red")
print("undo:", history.pop())
print("undo:", history.pop())It prints
undo: made it red undo: typed hello
Checking brackets match
This is the classic. Push every opening bracket; on a closing one, pop and check it matches. If the stack is empty at the end, everything paired up.
Python
def balanced(text):
stack = []
for c in text:
if c == "(":
stack.append(c)
elif c == ")":
if not stack:
return False
stack.pop()
return len(stack) == 0
print(balanced("(()) "))
print(balanced("(()"))It prints
True False
Try it yourself
Why is a stack the right tool for matching brackets?
- It is the fastest list
- The most recent unclosed bracket is always the one that must close next
- Brackets are stored in order
- It uses less memory
What does this print?
Python
stack = []
for c in "abc":
stack.append(c)
out = ""
while stack:
out = out + stack.pop()
print(out)Answer them in the app
🚶 Queues
First in, first out
A queue is a line at a shop. You join the back and leave from the front — the opposite rule to a stack. Whoever waited longest is served first.
Python
queue = ["Ada", "Sam"]
queue.append("Kim")
print(queue.pop(0))
print(queue)It prints
Ada ['Sam', 'Kim']
Why a list is the wrong tool here
pop(0) takes the front — but then every other item has to shuffle along one box. For a long queue that is slow. deque is built to be quick at *both* ends.
Python
from collections import deque
queue = deque(["Ada", "Sam"])
queue.append("Kim")
print(queue.popleft())
print(list(queue))It prints
Ada ['Sam', 'Kim']
Try it yourself
You join 1, then 2, then 3 to a queue. Who leaves first?
- 3
- 2
- 1
- Nobody
What does this print?
Python
from collections import deque
q = deque()
for n in [1, 2, 3]:
q.append(n)
print(q.popleft())
print(q.popleft())Answer them in the app
🏆 Stack & Queue Master
Try it yourself
What does this print?
Python
from collections import deque
stack = []
queue = deque()
for n in [1, 2, 3]:
stack.append(n)
queue.append(n)
print(stack.pop(), queue.popleft())Answer it in the app