Data structures
Stack Visualiser
Last in, first out. Everything happens at one end.
The stack is empty.
bottom
A stack is last in, first out. Everything happens at one end, which is why both operations are O(1).
- Height
- 0
- Operations run
- 0
class Stack { items = []; push(value) { this.items.push(value); // goes on top } pop() { return this.items.pop(); // comes off the top } peek() { return this.items.at(-1); }}The highlighted line is the one that produced the picture on the left.
What Stack does
A stack only lets you touch one end. You push a value on top and you pop the top value off, and that restriction is the whole value of it: the most recent thing is always the easiest to reach, which is exactly what you want for undo history, bracket matching, and the call stack your own code runs on.
How it works, step by step
- push adds a value above everything already there.
- pop removes and returns the top value. Nothing below it is touched.
- peek reads the top without removing it.
- Every one of those is a single array operation at the end, so all three are O(1).
What to watch for
- Nothing ever moves except the top. No matter how tall the stack gets, a push or a pop costs the same.
- Values come out in the reverse of the order they went in. Push 5, 12, 7 and you get back 7, 12, 5.
- Pop an empty stack and you get undefined rather than an error, which is why real code checks the length first.
Cost
| push | O(1) |
|---|---|
| pop | O(1) |
| peek | O(1) |
| Search | O(n) |
| Extra space | O(n) |
When to reach for it
Whenever the most recently added item is the one you need next: undo and redo, matching brackets, parsing expressions, backtracking through a search, and depth-first traversal. The call stack itself is a stack, which is why deep recursion overflows it.