Stacks: Last In, First Out

Lesson 1 of 10 · 5 min · Free, no account needed

What you will learn

A stack keeps things in a pile: you add to the top and take from the top.
Push puts an item on top; pop takes the top item off. The last one in is the first one out (LIFO).
In Python a list is a stack: s.append(x) pushes, s.pop() pops the last item.
Undo, the Back button and matching brackets all run on a stack.

You type, delete, paste, then hit Undo. How does the app know what to undo?
Edit this note yourself first. Do four things, in any order.
You press Undo once. Which of your actions disappears?
Here they are, mixed up. Tap your bet.
Press Undo three times.
Each action you did is a plate on a pile. Watch which plate comes off.
Every action is put on top of the pile when you do it. Undo always takes from the top, so it takes back the most recent action first.
That pile is a stack.
A stack is a pile: you only ever touch the top.
Push puts an item on top. Pop takes the top item off. The last one in is the first one out: LIFO.
In Python a plain list works as a stack: s.append(x) pushes, s.pop() pops the last item and gives it back.
Plate tower.
Push and pop until your stack matches the target. Try to hit par.
Now the same pile in Python.
Step through the code. Before each pop, tap the plate you think leaves.
A Python list grows at its end, and pop() with no number removes the last item. So the end of the list is the top of the stack.
Speed round: in what order do the plates leave?
Four rounds. Tap the plates in the order the pops take them.
Each pop removes the most recent push that hasn't been popped yet. In round 4: C goes, then D (just pushed), then B, then E, then A at the very bottom.

Lessons are interactive and need JavaScript. Turn it on to play them.