What are a stack and a queue?
A stack is a pile where you always take the newest item first. A queue is a line where you always take the oldest item first.
Your editor's undo button uses a stack, and a shared printer uses a queue. A compiler uses a stack to check that every bracket in your code is closed.
By the end of this lesson
Note
I can use a stack and a queue to solve a problem.
Key words
| Word | What it means | Example |
|---|---|---|
| Stack | a collection where the newest item leaves first | |
| Queue | a collection where the oldest item leaves first | |
| Push | put an item on top of a stack | stack.append(3) |
| Pop | take the top item off a stack | stack.pop() |
| LIFO | last in, first out: the rule of a stack | |
| FIFO | first in, first out: the rule of a queue |
The cells students fill in are left blank in this preview.
A stack removes the newest item first
A stack has two jobs. Push puts an item on top. Pop takes the top item off and gives it back.
This is LIFO, last in, first out. A pile of plates works the same way: you only reach the top plate. With a Python list, append pushes and pop() pops, and both work at the cheap end.
Worked example: an undo history
| Action | Stack (top on the right) | Item returned |
|---|---|---|
| Type "a" | a | None |
| Type "b" | a b | None |
| Type "c" | a b c | None |
| Undo | a b | c |
| Undo | a | b |
The cells students fill in are left blank in this preview.
Push two items and pop one
python3 -c "s = []; s.append(1); s.append(2); print(s.pop(), s)"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Read three lines newest first
printf 'one\ntwo\nthree\n' | tacShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
A queue removes the oldest item first
A queue also has two jobs. Enqueue adds an item at the back. Dequeue removes the item at the front.
This is FIFO, first in, first out, like people waiting at a till. A print queue sends jobs to the printer in the order they arrived.
Worked example: a print queue
| Event | Queue (front on the left) | Printed |
|---|---|---|
| Ana sends report.pdf | report.pdf | Nothing |
| Ben sends slides.pdf | report.pdf slides.pdf | Nothing |
| Printer takes a job | slides.pdf | report.pdf |
| Cai sends notes.pdf | slides.pdf notes.pdf | Nothing |
| Printer takes a job | notes.pdf | slides.pdf |
The cells students fill in are left blank in this preview.
A list is a poor queue
A list is cheap at its end only. Removing the front of a list shifts every item, as the last lesson showed.
Python's deque (say "deck") is built for both ends. append adds at the back and popleft removes from the front, and neither shifts anything.
Add to the back, remove from the front
python3 -c "from collections import deque; q = deque(['a', 'b']); q.append('c'); print(q.popleft(), list(q))"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
A common mistake
Warning
Many people mix up the two orders and think a stack and a queue behave alike. They do not. A stack gives back the newest item. A queue gives back the oldest. Ask which item must leave next: if it is the one that arrived last, you need a stack.
A stack checks that brackets match
Read the text from left to right. Push every opening bracket. For a closing bracket, pop the top and see whether it matches.
If the stack is empty at a closer, or the kinds differ, the text is wrong. If anything is left on the stack at the end, a bracket was never closed.
Worked example: checking {[()]}
| Character | Action | Stack afterwards |
|---|---|---|
| { | Push | { |
| [ | Push | { [ |
| ( | Push | { [ ( |
| ) | Pop ( and match | { [ |
| ] | Pop [ and match | { |
| } | Pop { and match | Empty: correct |
The cells students fill in are left blank in this preview.
Find the missing bracket
# Check brackets with a stack: push an opener, pop on a closer.
text = "square(7) + (3"
stack = []
ok = True
for ch in text:
if ch == "(":
stack.append(ch)
elif ch == ")":
if len(stack) == 0:
ok = False
else:
stack.pop()
if len(stack) > 0:
ok = False
print(ok, len(stack))
# Change text to "square(7) + (3)" and run again.