Move it step by step
Instruction list (runs left to right)
- push 3
- push 7
- push 5
- pop
- push 9
- pop
- pop
- pop
- just pushed/enqueued
- value out
- empty slot
- error
- top is the topmost position
Step 1 of 9Instructions run: 0Values inside: 0
Running 8 instructions, one by one, on an empty stack. It holds up to 5 values.
The pseudocode line currently running
- 1push(x)
- 2if full, error (overflow)
- 3move top up by one, and place x there
- 4pop()
- 5if empty, error (nothing to return)
- 6return the value at top, then move top down by one
Change the example
Try predicting
You're on step 1.
What comes out on the next pop?
What you'll learn
- The flow where the last value in is the first one out
- Why taking a value out when it's empty is an error
Prerequisites
- Arrays and indices (numbering that starts at 0)
- How to add to the end of an array, and remove from the end
How a stack works
A stack is a container where you stack values up, and also take them out from the top. The last value pushed in is the first one to come out, so it's called last-in-first-out (LIFO).
Stacking is called push, and taking a value out is called pop. The position of the top value is called top, and it moves by one with every push and pop.
Steps, with an example
- 1For push, check that it isn't full, then place the value one above top
- 2For pop, check that it isn't empty, then return the value at top
- 3After returning it, move top down by one
- 4Treat a pop when empty, and a push when full, as errors
| Instruction | Value out | Contents (bottom to top) |
|---|---|---|
| push 3 | None | [3] |
| push 7 | None | [3, 7] |
| push 5 | None | [3, 7, 5] |
| pop | 5 | [3, 7] |
| push 9 | None | [3, 7, 9] |
| pop | 9 | [3, 7] |
| pop | 7 | [3] |
| pop | 3 | [] |
Cost and complexity
| Operation | Cost | Complexity |
|---|---|---|
| push | 1 step (just place it on top) | O(1) |
| pop | 1 step (just take the top one) | O(1) |
| Looking at the bottom value | n steps (pop everything from the top, in order) | O(n) |
Push and pop only touch the top value, so the cost is the same whether there are 5 values inside or a million.
When to use it
Good fit
- Undoing the most recent action (an undo history)
- Checking that brackets match up
- Keeping track of function calls (the call stack)
Not a good fit
- When you want to process things in the order they arrived (use a queue instead)
- When you need to repeatedly search for a value in the middle (use an array or a dictionary instead)
Code
Pseudocode
- 1push(x)
- 2if full, error (overflow)
- 3move top up by one, and place x there
- 4pop()
- 5if empty, error (nothing to return)
- 6return the value at top, then move top down by one
Working code
▶ Press “Run” to see the result here
Edit the Python or JavaScript and press “Run” to see the result right away. Java is read-only here.
FAQ
- Can a plain Python list work as a stack?
- Yes. Push with append, and take the last item out with pop(), and that's already a stack. You only need to check the count, as shown above, if you want to cap how many it can hold.
- What actually happens if you pop an empty stack in real code?
- A Python list raises IndexError, and Java's ArrayDeque throws an exception. It's safer to check whether it's empty before popping.
