Last in, first out. Only the top is reachable — and that single restriction is exactly what makes stacks perfect for undo history, bracket matching, and the call stack behind every recursive function.
Controls
The Stack
step 0
bottom
Insight
A stack allows exactly three operations, all at the same end: push (add to top), pop (remove top), peek (look at top).
Where stacks are used
• The call stack for function calls
• Undo / redo history
• Browser back button
• Bracket & syntax matching
• Depth-first search
• Expression evaluation
size0
top–
Complexity
Push / Pop / PeekO(1)
SearchO(n)
SpaceO(n)
Stacks (LIFO)
One end, three operations, and a surprising amount of the computing world built on top.
Quick Context
A stack is a collection where you may only touch one end — the top. The last thing you put in is the first thing you take out, which is why it is called LIFO: Last In, First Out. Think of a stack of plates.
Three Operations, All O(1)
push(x) — put x on top.
pop() — remove and return the top item.
peek() — read the top without removing it.
All three are O(1) because they never touch the rest of the structure. That guarantee is the reason stacks are used in performance-critical places like the call stack.
Note what you cannot do: reach the middle. Searching a stack is O(n) and requires popping everything above what you want. The restriction is the feature — it makes the structure simple and fast.
The Call Stack Is a Stack
Every time a function is called, the computer pushes a stack frame holding its local variables and where to return. When the function finishes, that frame is popped and execution resumes exactly where it left off.
This is why recursion works at all — each recursive call gets its own frame. It is also why infinite recursion produces a stack overflow: frames pile up until the memory reserved for the stack runs out.
Bracket Matching: The Classic Application
Switch to bracket mode and step through. The rule is beautifully simple:
See an opening bracket → push it.
See a closing bracket → pop and check it matches. If it does not, the expression is invalid.
At the end, the stack must be empty — anything left over is an unclosed bracket.
A stack is exactly right here because brackets nest: the most recently opened one must always close first. Every code editor that highlights a missing brace runs this algorithm.
Interactive Exploration Guide
Push A, B, C then pop. C comes back first — LIFO in one action.
Try to reach the bottom item. You cannot, without popping everything above it. That is the trade-off for O(1) access to the top.
Pop from an empty stack. The lab reports stack underflow — a real error class you will meet.
Switch to bracket matching with the valid expression and step through. Watch the stack grow on openers and shrink on closers, finishing empty.
Now run the mismatched one. The algorithm stops the moment a closer disagrees with the top of the stack — it does not need to read the rest.
Key Takeaway
A stack restricts you to one end, and that restriction buys O(1) push, pop and peek. It models anything where the most recent item must be handled first: nested brackets, function calls, undo history, and depth-first traversal.
Cheat sheet
Stacks (LIFO)
Last in, first out. Only the top is reachable — and that single restriction is exactly what makes stacks perfect for undo history, bracket matching, and the call stack behind every recursive function.