After this lesson, you will be able to: Implement a stack, understand LIFO ordering, recognize the call stack as a real example, and use a stack to evaluate expressions and check balanced parentheses.
A stack is a list with one rule: you only add and remove from the same end. That single constraint makes it perfect for anything that needs to undo, backtrack, or remember 'where was I.'
A stack supports two main operations: push (add to the top) and pop (remove from the top). The last thing you pushed is the first thing you pop, like a stack of plates. Both operations are O(1). You never reach into the middle. This restriction is a feature: it models any situation where the most recent thing must be handled first.
A dynamic array already behaves like a stack from one end.
# Python: a list is a stack (push = append, pop = pop)stack = []stack.append(1) # pushstack.append(2)top = stack.pop() # pop -> 2 (last in, first out)peek = stack[-1] # look without removing -> 1# JavaScript: an array is a stackconst stack = [];stack.push(1);stack.push(2);const top = stack.pop(); // 2const peek = stack[stack.length - 1]; // 1
When function A calls function B which calls function C, the computer pushes a frame for each call onto the call stack. When C returns, its frame is popped and control goes back to B. This is literally a stack. A stack overflow error means you pushed too many frames (usually infinite recursion with no base case). Understanding that the call stack is a stack is the bridge to understanding recursion in the Algorithms sub-track.
Given a string of brackets, return true if every opener has a matching closer in the right order.
1. Create an empty stack and a map: ')' -> '(', ']' -> '[', '}' -> '{'.
2. Walk each character. If it is an opener, push it.
3. If it is a closer, pop the stack and check it matches; if the stack was empty or the top did not match, return false.
4. At the end, the string is balanced only if the stack is empty.
5. Test: "([]{})" -> true, "([)]" -> false, "(((" -> false.
A stack you keep in sorted (increasing or decreasing) order. It turns many 'next greater / previous smaller' problems from O(n squared) into O(n).
# Problem: for each day's temperature, how many days until a warmer one?# (LeetCode 739, Daily Temperatures.) Brute force is O(n^2); a monotonic# stack does it in O(n) by keeping indices of days still waiting for a warmer day.def daily_temperatures(temps):answer = [0] * len(temps)stack = [] # holds INDICES, kept in decreasing temperature orderfor i, t in enumerate(temps):# while today is warmer than the day on top of the stack, we've# found that day's answer: pop it and record the gap.while stack and temps[stack[-1]] < t:prev = stack.pop()answer[prev] = i - prevstack.append(i)return answer# daily_temperatures([73,74,75,71,69,72,76,73]) -> [1,1,4,2,1,1,0,0]# Each index is pushed and popped at most once, so the whole pass is O(n).
The signal is a problem asking for the next (or previous) element that is greater or smaller than each element: 'next greater element,' 'largest rectangle in a histogram,' 'daily temperatures,' 'trapping rain water,' 'stock span.' If you find yourself writing a nested loop that scans forward or backward from each position looking for the first bigger/smaller value, a monotonic stack almost always collapses it to a single O(n) pass. Decide up front whether you want increasing or decreasing order, and whether you push values or indices (indices when you need distances).
Popping from an empty stack without checking (guard for empty first). Using the wrong end of a list as the top, turning O(1) pop into O(n) (in Python, pop from the end, never pop(0)). Forgetting the final 'is the stack empty?' check in the balanced-parentheses pattern, which lets unclosed openers slip through. With a monotonic stack, storing values when you actually need indices (or vice versa), and using the wrong comparison (`<` vs `<=`) so equal elements are handled incorrectly. Reaching for recursion when an explicit stack would avoid a stack-overflow on deep inputs.
Sign in and purchase access to unlock this lesson.