Why does the stack data structure appear in so many interview problems? Because a surprisingly large number of real-world tasks share one property: the most recently added item is the one you need to deal with next. Undo buttons, browser back navigation, function calls returning to their caller - all of these follow the Last-In-First-Out (LIFO) principle. Once you internalize LIFO as a pattern rather than just a definition, you start recognizing stack problems instantly.

The LIFO Principle

A stack supports three core operations, all in O(1) time:

• Push - add an element to the top.
• Pop - remove and return the element from the top.
• Peek (also called top) - look at the top element without removing it.

That is the entire API. The simplicity is the point. You cannot access the middle of a stack or iterate from the bottom. This constraint is what makes stacks powerful - by limiting what you can do, a stack enforces an ordering guarantee that simplifies your logic.

Mental Models That Stick

The best way to build intuition is to connect stacks to things you already understand:

Stack of plates in a cafeteria. You add a clean plate on top. The next person takes the plate from the top. Nobody reaches into the middle of the stack - it would be unstable and slow. This is exactly how a software stack works. The plate analogy explains why "stack overflow" is a perfect name: too many plates and the whole thing collapses.

Browser back button. Every page you visit gets pushed onto a history stack. Clicking "back" pops the most recent page. You always go back to where you just were, not to some arbitrary earlier page. This is LIFO in action.

Function call stack. When function A calls function B, and B calls function C, the runtime pushes each call onto the call stack. When C finishes, it pops off, and execution returns to B. When B finishes, it pops off, and execution returns to A. This is why infinite recursion causes a stack overflow - the call stack runs out of space because nothing ever pops.

1Call Stack during execution:
2┌─────────┐
3│    C()   │  ← currently executing
4├─────────┤
5│    B()   │  ← waiting for C to return
6├─────────┤
7│    A()   │  ← waiting for B to return
8└─────────┘

Array-Based Implementation

In practice, you almost always implement a stack using a dynamic array (Python list, Java ArrayList, JavaScript array). The end of the array is the "top" of the stack:

1class Stack:
2    def __init__(self):
3        self.data = []
4
5    def push(self, val):
6        self.data.append(val)    # O(1) amortized
7
8    def pop(self):
9        if not self.data:
10            return None
11        return self.data.pop()   # O(1)
12
13    def peek(self):
14        if not self.data:
15            return None
16        return self.data[-1]     # O(1)
17
18    def is_empty(self):
19        return len(self.data) == 0

Why use the end of the array instead of the beginning? Because appending and removing from the end of a dynamic array is O(1) amortized, while inserting or removing at the beginning requires shifting every element - O(n). The choice of which end is the "top" is a performance decision, not an arbitrary one.

When to Reach for a Stack

Recognizing when a problem needs a stack is the most valuable skill. Here are the signals:

• Matching pairs - parentheses, HTML tags, or any open/close pattern. You need to match the most recent unmatched opener, which is the top of the stack.
• Backtracking or undo - undoing the most recent action, like navigating back or reversing a path.
• Maintaining last-seen order - when the current element needs to interact with the most recently seen element that satisfies some condition (monotonic stack problems).
• Nested structure processing - recursive structures like nested brackets 3[a2[bc]] or nested function calls, where you process the innermost level first.

If you see any of these signals in an interview problem, your first instinct should be to consider a stack.

Parentheses matching is the canonical stack problem - it appears in interviews constantly, and more importantly, the pattern it teaches transfers directly to dozens of other problems involving paired or nested structures. If you truly understand why a stack solves bracket matching, you will recognize the same pattern in HTML tag validation, compiler parsing, and nested data structure processing.

Why a Stack Fits This Problem

The core insight is this: when you encounter a closing bracket, you need to check it against the most recently opened unmatched bracket. Not the first one, not a random one - the most recent one. That is exactly what a stack gives you. The top of the stack always holds the most recent unmatched opener.

The Algorithm

The algorithm is straightforward once you see the connection to LIFO:

1. Create an empty stack and a mapping of closing brackets to their corresponding openers.
2. Iterate through each character in the string.
3. If the character is an opening bracket ((, [, {), push it onto the stack.
4. If the character is a closing bracket (), ], }), check the stack:
   • If the stack is empty, there is no matching opener - return false.
   • Pop the top of the stack. If the popped opener does not match the current closer - return false.
5. After processing all characters, if the stack is empty, every opener was matched - return true. If the stack is not empty, there are unmatched openers - return false.

1def is_valid(s: str) -> bool:
2    stack = []
3    match = {')': '(', ']': '[', '}': '{'}
4
5    for char in s:
6        if char in '([{':
7            stack.append(char)
8        elif char in ')]}':
9            if not stack or stack[-1] != match[char]:
10                return False
11            stack.pop()
12
13    return len(stack) == 0

Walking Through an Example

Let us trace through ({[]}) step by step:

Stack is empty at the end, so the string is valid. Notice how the stack naturally handles the nesting: [ was pushed last and popped first when ] arrived, even though ( was pushed first. This is LIFO in action.

Edge Cases That Catch People

Empty input - An empty string has no unmatched brackets, so it is valid. The stack starts empty and stays empty.

Unmatched openers at the end - ([{ pushes three openers but encounters no closers. After processing all characters, the stack is not empty, so return false. Many candidates forget this check and only look for mismatches during iteration.

Close without matching open - ) immediately tries to pop from an empty stack. The empty-stack check catches this. Another variant: (]) pushes (, then encounters ]. The top of the stack is (, which does not match ], so return false even though the stack is not empty.

Only one type of bracket - ((())) works the same way. The algorithm does not special-case the number of bracket types.

Practice Problem

Apply the parentheses matching pattern you just learned.

Expression evaluation is where stacks go from a basic data structure exercise to a tool that solves real engineering problems. Every calculator app, every spreadsheet formula parser, and every programming language compiler uses stack-based expression evaluation. Understanding this pattern also prepares you for interview questions involving operator precedence, nested computations, and postfix notation.

The Problem with Infix Notation

Humans write expressions in infix notation: 3 + 4 * 2. This is easy to read but hard to evaluate programmatically because of operator precedence. You cannot simply evaluate left to right - 3 + 4 * 2 is 11, not 14, because multiplication binds tighter than addition. Parentheses add another layer of complexity: (3 + 4) * 2 is 14.

The solution is to convert infix to postfix notation (also called Reverse Polish Notation), where operators come after their operands: 3 + 4 * 2 becomes 3 4 2 * +. In postfix, there are no parentheses and no precedence rules - you evaluate strictly left to right using a stack.

The Two-Stack Approach

The classic approach uses two stacks: one for operands (numbers) and one for operators. When you encounter:

• A number - push it onto the operand stack.
• An operator - before pushing it onto the operator stack, pop and evaluate any operators already on the stack that have equal or higher precedence. This ensures higher-precedence operators get evaluated first.
• An opening parenthesis - push it onto the operator stack as a marker.
• A closing parenthesis - pop and evaluate operators until you reach the matching opening parenthesis.

The precedence rule is what makes this work. When you see 3 + 4 * 2, pushing + then * is fine because * has higher precedence. But when you see 3 * 4 + 2, before pushing + you must evaluate the pending * because it has higher precedence.

Evaluating Postfix (Reverse Polish Notation)

Postfix evaluation is simpler and is the most common interview variant. The algorithm uses a single stack:

1. Iterate through each token.
2. If the token is a number, push it onto the stack.
3. If the token is an operator, pop two operands from the stack, apply the operator, and push the result back.
4. After processing all tokens, the stack contains exactly one element - the final answer.

1def eval_rpn(tokens: list[str]) -> int:
2    stack = []
3    for token in tokens:
4        if token in '+-*/':
5            b = stack.pop()  # second operand (popped first)
6            a = stack.pop()  # first operand
7            if token == '+':
8                stack.append(a + b)
9            elif token == '-':
10                stack.append(a - b)
11            elif token == '*':
12                stack.append(a * b)
13            elif token == '/':
14                # Truncate toward zero
15                stack.append(int(a / b))
16        else:
17            stack.append(int(token))
18    return stack[0]

Walking Through Postfix Evaluation

Evaluate ["2", "1", "+", "3", "*"] which represents (2 + 1) * 3:

Result: 9. Notice how the stack naturally handles the grouping without parentheses. The + evaluates before * because its operands appear first in the postfix sequence.

The Shunting-Yard Algorithm (Infix to Postfix)

Dijkstra's shunting-yard algorithm converts infix to postfix using an operator stack. The key rules are:

1. Numbers go directly to the output.
2. Operators get pushed to the stack, but first pop any operators with higher or equal precedence to the output.
3. Opening parentheses get pushed to the stack.
4. Closing parentheses pop operators to the output until the matching opening parenthesis.
5. At the end, pop all remaining operators to the output.

Converting 3 + 4 * 2:

• 3 goes to output: [3]
• + pushed to operator stack: stack = [+]
• 4 goes to output: [3, 4]
• * has higher precedence than +, so push without popping: stack = [+, *]
• 2 goes to output: [3, 4, 2]
• End: pop all operators: output = [3, 4, 2, *, +]

Result: 3 4 2 * + - which evaluates to 11.

Operand Order Matters for Subtraction and Division

A critical detail: when you pop two operands for subtraction or division, the first popped value is the second operand. ["4", "2", "-"] means 4 - 2 = 2, not 2 - 4. The stack reverses the order because the second operand was pushed after the first.

Push 4, Push 2
Pop b = 2, Pop a = 4
Result: a - b = 4 - 2 = 2  ✓

Getting this backwards is one of the most common bugs in interview implementations.

Practice Problem

Apply the postfix evaluation pattern you just learned.

The Min Stack problem is a favorite in interviews because it tests whether you can augment a data structure to support an additional operation without sacrificing the performance of existing ones. The challenge is straightforward to state - support push, pop, top, and getMin all in O(1) - but the solution requires a genuine insight about how to track auxiliary information.

The Problem

Design a stack that supports four operations, all in O(1) time:

• push(val) - push an element onto the stack.
• pop() - remove the element on top of the stack.
• top() - get the top element.
• getMin() - retrieve the minimum element in the stack.

The first three operations are standard stack operations. The challenge is getMin. Scanning the entire stack to find the minimum would be O(n). How do you achieve O(1)?

The Key Insight: Parallel Min Tracking

The insight is that the minimum can only change when you push or pop. If you maintain a second stack - a "min stack" - that tracks the current minimum at each level of the main stack, you can always answer getMin by peeking at the min stack.

The rules for the min stack are:

• On push(val): if the min stack is empty or val is less than or equal to the current min, push val onto the min stack too.
• On pop(): if the popped value equals the min stack's top, pop the min stack too.
• getMin(): return the min stack's top.

Why less than or equal and not just less than? Because duplicate minimums need separate tracking. If you push 2, then push another 2, and then pop, the minimum is still 2. If you only pushed to the min stack on strictly-less-than, the second 2 would not be tracked, and after popping it, the min stack would incorrectly show an older value.

Walking Through an Example

Let us trace push 5, 3, 7, 2, 8:

Notice how push(7) does not add to the min stack because 7 is greater than the current min (3). But push(2) does add because 2 is less than or equal to the current min. When we pop 2, the min stack also pops, correctly restoring the minimum to 3.

Implementation

1class MinStack:
2    def __init__(self):
3        self.stack = []
4        self.min_stack = []
5
6    def push(self, val: int) -> None:
7        self.stack.append(val)
8        if not self.min_stack or val <= self.min_stack[-1]:
9            self.min_stack.append(val)
10
11    def pop(self) -> None:
12        val = self.stack.pop()
13        if val == self.min_stack[-1]:
14            self.min_stack.pop()
15
16    def top(self) -> int:
17        return self.stack[-1]
18
19    def get_min(self) -> int:
20        return self.min_stack[-1]

Alternative: Store Pairs

An alternative approach stores (value, current_min) pairs in a single stack. Each push records the minimum at that point in time. This uses slightly more space (every element stores a min) but avoids the logic of deciding when to push/pop the min stack.

1class MinStack:
2    def __init__(self):
3        self.stack = []  # stores (value, current_min)
4
5    def push(self, val: int) -> None:
6        current_min = min(val, self.stack[-1][1]) if self.stack else val
7        self.stack.append((val, current_min))
8
9    def pop(self) -> None:
10        self.stack.pop()
11
12    def top(self) -> int:
13        return self.stack[-1][0]
14
15    def get_min(self) -> int:
16        return self.stack[-1][1]

Both approaches are O(1) for all operations. The pair approach is simpler to implement correctly (no edge cases with duplicate minimums) while the two-stack approach uses less memory when the minimum rarely changes.

Why This Pattern Matters Beyond the Problem

The Min Stack teaches a general principle: you can augment a data structure with auxiliary state to answer queries in O(1), as long as you update the auxiliary state during every mutation. This same idea appears in:

• Max stack - track the maximum instead of the minimum.
• Stack with running sum - track the sum of all elements.
• LRU cache - augment a hash map with a doubly-linked list to track access order.

When an interview asks you to "support operation X in O(1)," think about what auxiliary state you can maintain alongside the primary data structure.

Practice Problem

Apply the parallel tracking pattern you just learned.

The problems in previous sections follow recognizable templates - match brackets, evaluate expressions, track minimums. But stacks are also a general-purpose simulation tool for any problem where the current element needs to modify or interact with previous state. This section covers two classic simulation problems and extracts the general pattern so you can apply it to problems you have never seen before.

Decode String: Nested Repetition

The problem: given an encoded string like 3[a2[bc]], decode it to abcbcabcbcabcbc. The encoding rule is k[encoded_string], where the encoded_string inside the brackets is repeated k times.

Why is this a stack problem? Because the brackets nest. When you encounter the inner 2[bc], you need to resolve it to bcbc before the outer 3[...] can use it. This is the same "process the innermost first" pattern as parentheses matching.

The algorithm:

1. Maintain a stack that stores (current_string, current_multiplier) pairs.
2. When you encounter a digit, build the full number (it could be multi-digit like 12[a]).
3. When you encounter [, push the current string and multiplier onto the stack, then reset both.
4. When you encounter ], pop the previous string and multiplier from the stack. The decoded result is previous_string + current_string * multiplier.
5. When you encounter a letter, append it to the current string.

1def decode_string(s: str) -> str:
2    stack = []
3    current_str = ""
4    current_num = 0
5
6    for char in s:
7        if char.isdigit():
8            current_num = current_num * 10 + int(char)
9        elif char == '[':
10            stack.append((current_str, current_num))
11            current_str = ""
12            current_num = 0
13        elif char == ']':
14            prev_str, num = stack.pop()
15            current_str = prev_str + current_str * num
16        else:
17            current_str += char
18
19    return current_str

Trace through 3[a2[bc]]:

Simplify Unix Path

The problem: given a Unix-style file path like /a/./b/../../c, simplify it to /c.

The rules are:

• . means current directory (do nothing).
• .. means parent directory (go up one level).
• Multiple consecutive slashes are treated as a single slash.
• The result must start with / and have no trailing slash.

Why is this a stack problem? Because .. undoes the most recent directory - it "pops" the last directory you entered. This is the backtracking signal.

1def simplify_path(path: str) -> str:
2    stack = []
3    parts = path.split('/')
4
5    for part in parts:
6        if part == '' or part == '.':
7            continue
8        elif part == '..':
9            if stack:
10                stack.pop()
11        else:
12            stack.append(part)
13
14    return '/' + '/'.join(stack)

Trace through /a/./b/../../c:

• Split: ['', 'a', '.', 'b', '..', '..', 'c']
• '' - skip. 'a' - push. Stack: ['a']
• '.' - skip. 'b' - push. Stack: ['a', 'b']
• '..' - pop 'b'. Stack: ['a']
• '..' - pop 'a'. Stack: []
• 'c' - push. Stack: ['c']
• Result: /c

The General Stack Simulation Pattern

Both problems above follow a common template:

1. Iterate through the input token by token.
2. Accumulate - for most tokens, build up the current state (append to a string, push to the stack).
3. Trigger - certain tokens cause a pop-and-combine operation that resolves accumulated state.

This pattern appears in many other problems: asteroid collision (moving asteroids destroy previous ones), removing duplicate characters, and calculator implementations. The key recognition skill is identifying which tokens accumulate and which tokens trigger.

When Current State Modifies Previous State

The ultimate heuristic for stack-based simulation is this: when the current element needs to modify, undo, or combine with a previous element, use a stack. The stack holds the "previous elements" in the order they were encountered, and the current element can peek at or pop the top to decide what to do.

This is fundamentally different from problems where elements are independent (use a simple loop) or where elements interact with all other elements (use sorting or hash maps). The stack excels specifically at ordered, local interactions where "most recent" is the relevant scope.