Stack

A stack is a last-in, first-out structure. The most recently added item is the first item removed.

Stacks are useful when the algorithm needs to remember unfinished work and return to the most recent item first.

Core Idea

The main operations are push and pop. In Python, a list usually acts as a stack: append pushes and pop removes the most recent item.

This behavior matches nested structure. Function calls, parentheses, depth-first search, and backtracking all have stack-like behavior.

The stack answers the question: “What is the most recent unfinished thing?” That is why it fits nested parentheses, recursive calls, and depth-first exploration.

Function Contracts

is_balanced(text) accepts a string containing parentheses and returns whether every closing parenthesis matches a previous unmatched opening parenthesis.

dfs_order(graph, start) expects an adjacency list where graph[node] lists neighbors and start is a key in graph. It returns the order in which nodes are first visited by an explicit-stack depth-first traversal.

Python Example

stack = []
 
stack.append("open")
stack.append("work")
 
last = stack.pop()

After the pop, last is "work" because it was added most recently.

Step-by-Step Example

Balanced parentheses are a natural stack problem:

def is_balanced(text):
    stack = []
 
    for char in text:
        if char == "(":
            stack.append(char)
        elif char == ")":
            if not stack:
                return False
            stack.pop()
 
    return not stack

An opening parenthesis creates unfinished work. A closing parenthesis must match the most recent unfinished opening parenthesis.

Relationship to Recursion

Recursive calls are managed by a call stack. A depth-first traversal can often be written with an explicit stack instead:

def dfs_order(graph, start):
    visited = set()
    stack = [start]
    order = []
 
    while stack:
        node = stack.pop()
        if node in visited:
            continue
 
        visited.add(node)
        order.append(node)
 
        for neighbor in graph[node]:
            if neighbor not in visited:
                stack.append(neighbor)
 
    return order

This code handles the most recently added unfinished node first, which is the stack behavior.

Complexity

append and pop at the end of a Python list are O(1) amortized. A stack that stores up to n items uses O(n) space.

Step-by-Step Trace

For text = "(())", the first two opening parentheses are pushed. The first closing parenthesis pops the most recent opening one. The second closing parenthesis pops the remaining opening one. The stack is empty at the end, so the string is balanced.

For text = "(()", one opening parenthesis remains in the stack at the end, so the string is not balanced.

Common Confusions

A stack is defined by behavior, not by a specific class. In Python, a plain list is often enough.

Do not use pop(0) for stack behavior. That removes the oldest item, not the newest item, and it is also inefficient for Python lists.

A stack does not give access to the oldest item first. If the algorithm needs first-in, first-out behavior, use a queue.

When To Use It

Use a stack for nested or reversible work: matching parentheses, evaluating expressions, iterative DFS, undo-like behavior, and algorithms that need to postpone choices until later.

A good signal for a stack is that the next item to handle should be the most recent unresolved item.

The Main Point

A stack manages unfinished work in last-in, first-out order. It fits nested structure, undo behavior, and depth-first exploration.