A stack is like a pile of pancakes đĨ or plates: you add to the top and remove from the top. The last item you put in is the first one to come out â LIFO.
You use stacks every day:
Undo (Ctrl+Z) â the most recent action is undone first.
The browser Back button.
The function call stack in recursion!
stack = []
stack.append("a") # push
stack.append("b")
stack.append("c")
print(stack.pop()) # c (last in, first out)
print(stack.pop()) # b
đ In Python
A plain list is a stack: .append() to push, .pop() to remove the top.
đļââī¸đļââī¸ A Queue â First In, First Out (FIFO)
A queue is like a line at a store: the first person to arrive is the first served â FIFO. You add at the back and remove from the front.
Queues power printers (first document prints first), task schedulers, and breadth-first search (next lesson territory!).
from collections import deque
queue = deque()
queue.append("a") # enqueue (add at back)
queue.append("b")
queue.append("c")
print(queue.popleft()) # a (first in, first out)
print(queue.popleft()) # b
Why not just use list.pop(0)?
Removing from the front of a list is O(n) â Python has to shift every item. A deque (double-ended queue) does it in O(1). Use deque for queues!
đ Quick comparison
Stack (LIFO)
Queue (FIFO)
Add
append()
append()
Remove
pop() (end)
popleft() (front)
Real-world
Undo, Back button
Print line, ticket queue
â What you learned
Stack = LIFO. Push/pop from the same end. Use a list.
Queue = FIFO. Add at back, remove from front. Use deque.
Both add and remove in O(1) when used correctly.
đŽ Time to Practice!
Push, pop, enqueue, dequeue! đ
đĨ
Task 1: Use a Stack
Easy
Push "a", "b", "c" onto the stack, then pop and print all three. Because it's LIFO, the output is c, b, a.
A classic stack problem! Check if brackets are balanced. Push every (; when you see a ), pop one. It's balanced if you never pop an empty stack and it ends empty. Test "(())" â True.
đī¸
Task 3: Serve the Queue
Medium
Three people join a line. Serve them in FIFO order using popleft(). Output should be Alice, Bob, Carol.
from collections import deque
line = deque()
line.append("Alice")
line.append("Bob")
line.append("Carol")
print(line.popleft())
print(line.popleft())
print(line.popleft())
đī¸ Extra Practice â Algorithm Reps
Stacks and queues show up in browsers, printers, undo buttons and text editors. Build them over and over until the push/pop rhythm is second nature.
đ
Task 4: Reverse With a Stack
Easy
Push every letter of "stack" onto a list, then pop them off one by one into a new string. Last in, first out â so the word comes out backwards. Print the result.
kcats
stack = []
for letter in "stack":
stack.append(letter)
reversed_word = ""
while stack:
reversed_word += stack.pop()
print(reversed_word)
âŠī¸
Task 5: Undo History
Medium
A drawing app remembers actions in a stack. Push "circle", "square" and "line", then undo twice â printing what each undo removes â and finally print what is left.
A queue is first in, first out. Using from collections import deque, add "Ana", "Ben" and "Cy", then serve them in order with .popleft(), printing Serving Ana each time.
Serving Ana
Serving Ben
Serving Cy
from collections import deque
line = deque()
line.append("Ana")
line.append("Ben")
line.append("Cy")
while line:
print("Serving", line.popleft())
đĨ
Task 7: Hot Potato
Tricky
Five kids stand in a circle: ["A", "B", "C", "D", "E"]. Pass the potato 3 times (move the front kid to the back), then the kid holding it is out â print who leaves. Repeat until one winner remains, then print Winner: X.
Out: D
Out: C
Out: E
Out: B
Winner: A
from collections import deque
kids = deque(["A", "B", "C", "D", "E"])
while len(kids) > 1:
for pass_number in range(3):
kids.append(kids.popleft())
print("Out:", kids.popleft())
print("Winner:", kids[0])
đ
Task 8: A Stack That Knows Its Minimum
Tricky
Keep a second stack of running minimums so you can ask for the smallest value instantly. Push 5, 3, 7 and 2, printing the current minimum after each push.
min is 5
min is 3
min is 3
min is 2
stack = []
mins = []
def push(value):
stack.append(value)
if not mins or value <= mins[-1]:
mins.append(value)
else:
mins.append(mins[-1])
print("min is", mins[-1])
push(5)
push(3)
push(7)
push(2)
đ§Ž
Task 9: Boss Level: Calculator in Reverse
Boss
Computers love postfix maths: "3 4 + 2 *" means (3 + 4) Ã 2. Read the tokens one by one â push numbers onto a stack, and when you meet an operator pop two numbers, apply it, and push the answer back. Print the final value.
14
expression = "3 4 + 2 *"
stack = []
for token in expression.split():
if token in "+-*/":
b = stack.pop()
a = stack.pop()
if token == "+":
stack.append(a + b)
elif token == "-":
stack.append(a - b)
elif token == "*":
stack.append(a * b)
else:
stack.append(a // b)
else:
stack.append(int(token))
print(stack.pop())