Stacks

A stack exposes the most recently pushed item first: last in, first out. Its minimal operations are push, pop, peek, and an emptiness check.

stack: list[str] = []
stack.append("first")
stack.append("second")
top = stack[-1]
removed = stack.pop()

Using the end of a dynamic array gives amortized $O(1)$ push/pop and $O(1)$ peek. A linked implementation can provide worst-case $O(1)$ endpoint updates but adds one allocation and link per element.

Invariant

Only the top is directly removable. Restricting access communicates unfinished work: the top often represents the most recent open delimiter, active search state, pending operator, or undoable action.

Common uses

• iterative depth-first search and backtracking;
• expression parsing and delimiter matching;
• undo histories and nested scopes;
• simulating recursion when explicit control over state is useful.

The language runtime call stack is related but also stores return addresses, locals, and execution metadata; it is not merely a user-level value stack.

Failure and capacity

Popping an empty stack is underflow and should have an explicit contract. A bounded stack can also overflow; a dynamic implementation instead faces memory allocation failure or policy limits.

Do not use front insertion/removal on a dynamic array to model a stack; it adds unnecessary shifts.

Worked example: nested delimiters

def balanced(text: str) -> bool:
    opening: list[str] = []
    pairs = {")": "(", "]": "[", "}": "{"}
    for char in text:
        if char in "([{":
            opening.append(char)
        elif char in pairs:
            if not opening or opening.pop() != pairs[char]:
                return False
    return not opening

assert balanced("a * (b + [c])")
assert balanced("")
assert not balanced("([)]")
assert not balanced(")(")
assert not balanced("((")

After each accepted character, the stack contains exactly the unmatched opening delimiters, in encounter order. A closing delimiter must match the top, not merely some earlier opener: ([)] has equal counts but crosses nesting boundaries. An empty stack at the end means no opener is left unfinished. The algorithm uses $O(n)$ time for $n$ characters and $O(d)$ extra space for maximum nesting depth $d$.

This checks delimiter nesting only. It ignores other characters but does not understand quoted strings or comments, so it is not a programming-language parser. In the first stack snippet, both top and removed are "second", while the remaining stack is ["first"]. On an empty Python list, both stack[-1] and stack.pop() raise IndexError.

With a suitable growth and shrink policy, a resizing array offers amortized $O(1)$ pop rather than universally worst-case $O(1)$; peek remains $O(1)$. Linked endpoint bounds count link changes, not a guaranteed wall-clock allocation time.

In the USF array-stack animation, push three values, then pop them one at a time. Watch the top index move while the lower elements stay in place; the display makes the LIFO restriction visible.

Source

• Open Data Structures: Stack Interface

My reading · Opened notes are remembered in this browser.