Stacks
Last in, first out.
A stack is like a pile of plates. You put a plate on top, and you take a plate from the top. The last one in is the first one out. Your browser's back button, and undo in an editor, both work like a stack.

- A pile of plates
- Last in, first out
- Back button, undo
A list as a stack
A Python list makes a perfect stack. Append pushes onto the top, and pop removes from the top. Both are O of one, because they work at the end of the list. The last item, at index minus one, lets you peek without removing. Run it. The pages come back in reverse order, just like pressing back.
history = []
history.append("home")
history.append("search")
history.append("product")
print("top:", history[-1])
while history:
print("back to", history.pop())top: product back to product back to search back to home
Stack operations
Every stack has the same small set of operations. Push adds to the top. Pop removes the top. Peek looks at the top. And is empty checks whether anything is left. All of them are O of one. Never add or remove from the front of a list for a stack, because that's O of N.
| key | value |
|---|---|
| push | append(x) |
| pop | pop() |
| peek | stack[-1] |
| is empty | not stack |
Summary
A stack is last in, first out. With a Python list, append and pop at the end are both O of one. Next, a classic stack problem. Balanced brackets.
Key takeaways- Last in, first out
- append / pop
- Undo and back buttons