Stack & Queue · 01 / 04

StackStacks

push / pop / peek, the call stack, bracket matching.

Used for: Undo, bracket checking, expression evaluation, DFS

Time complexityO(1)

Space complexityO(n)

DifficultyIntro

PrerequisitesArrays and dynamic arrays

01Why it exists

Bracket checking and Ctrl+Z in an editor

Brackets in code have to come in pairs, and the most recently opened one must be the first to close. Undo works the same way: the last action taken is the first one reversed.

Why this fitsA stack only lets things in and out at one end, which makes it last-in, first-out by construction. Push on an opening bracket, pop and compare on a closing one; push every action, pop on undo. The structure itself states the rule.

How a function call remembers where to return

A calls B, B calls C. When C finishes, which line of B does it return to, and when B finishes, which line of A? With recursion the same function may be dozens of levels deep.

Why this fitsThe call stack: every call pushes a frame, every return pops one. The call stack you met in the recursion lesson is exactly this structure. DFS using a stack while BFS uses a queue is the same idea again.

How a calculator works out 3 + 4 × 2

Expressions have precedence and parentheses, so evaluating strictly left to right gives the wrong answer. Compilers, spreadsheets and calculators all have to get this right.

Why this fitsConvert the expression to postfix (reverse Polish) notation and a single stack evaluates it left to right in one pass: push numbers, and on an operator pop two, compute, and push the result back.

Reach for it when you see:Last in first out, the most recent one first, matching pairs, undo, nested structure, evaluating expressions, the iterative form of DFS.

02The core idea

A stack has only three operations: push puts something on top, pop takes the top off, and peek looks at the top. It is last in, first out (LIFO): whatever went in most recently comes out first. All three are O(1). It is simple enough to build from the end of an array, where adding and removing are O(1) — which is exactly what a Python list and C++'s std::stack do.

The value of a stack is not how fast its operations are, it is that it remembers the order. For any problem where the most recently opened thing must close first, or where you need to retrace your steps back out, the structure is already half the answer: matching brackets, nested tags, function calls, .. in a path, undo/redo, and the iterative form of DFS.

A common extension is to store a little more on each level. A Min Stack records "the minimum up to here" next to every element, so after a pop the minimum is simply whatever the level below recorded — no recomputation needed. The monotonic stack in the next lesson instead attaches a condition to when you should pop, which collapses an O(n²) problem down to O(n).

03The algorithm

1Check whether the problem has a most recent one first structure: nesting, pairing, backtracking, or needing to remember the path you took.
2Decide what goes on the stack: characters, indices, or a (value, extra information) pair. Storing indices is usually more flexible than storing values.
3Scan the input left to right. Push on an "open"; on a "close", first check that the stack is not empty, then compare against the top and pop.
4After the scan, check that the stack is empty: anything left over usually means something was never closed.
5Verify with three inputs: empty input, closes with no opens, and opens with no closes.

04Interactive demo

Pick a string and step through the bracket matching: opening brackets are pushed, closing ones are compared against the top and popped. Note which step catches each of the three invalid cases.

Input string

([{}])

Stack (top → bottom)

empty

Step 0/7The stack starts empty. Read the characters left to right: push every opening bracket, and match every closing bracket against the top.

05Code

The basic operations, bracket matching, evaluating postfix notation, and a Min Stack that stores one extra minimum per level. In C++, remember that pop() returns nothing, so read top() first.

# A Python list is a stack: append to push, pop to remove, [-1] to peek — all O(1)
stack = []
stack.append(1)
stack.append(2)
stack[-1]          # 2 (peek)
stack.pop()        # 2
len(stack) == 0    # is it empty?


# Matching brackets (LeetCode 20)
def is_valid(s):
    pair = {")": "(", "]": "[", "}": "{"}
    stack = []
    for c in s:
        if c in pair:                          # a closing bracket
            if not stack or stack[-1] != pair[c]:
                return False
            stack.pop()
        else:                                  # an opening bracket
            stack.append(c)
    return not stack                           # everything paired up exactly


# Evaluating postfix notation (LeetCode 150): "2 1 + 3 *" → (2+1)*3 = 9
def eval_rpn(tokens):
    stack = []
    for t in tokens:
        if t in "+-*/":
            b, a = stack.pop(), stack.pop()    # mind the order: the first pop is the right operand
            if t == "+": stack.append(a + b)
            elif t == "-": stack.append(a - b)
            elif t == "*": stack.append(a * b)
            else: stack.append(int(a / b))     # truncate towards zero
        else:
            stack.append(int(t))
    return stack[0]


# Min Stack (LeetCode 155): store the minimum so far alongside each value
class MinStack:
    def __init__(self):
        self.stack = []        # (value, minimum at that point)

    def push(self, x):
        cur_min = min(x, self.stack[-1][1]) if self.stack else x
        self.stack.append((x, cur_min))

    def pop(self):
        self.stack.pop()

    def top(self):
        return self.stack[-1][0]

    def get_min(self):
        return self.stack[-1][1]

06Practice

LeetCode 20Valid ParenthesesEasy
LeetCode 155Min StackMedium
LeetCode 150Evaluate Reverse Polish NotationMedium
LeetCode 71Simplify PathMedium
LeetCode 394Decode String (nested)Medium
LeetCode 224Basic CalculatorHard

Previous—NextQueue & Deque