Previous Topic

What Is a Stack?

A stack is a linear data structure that enforces Last-In, First-Out (LIFO) ordering: the most recently added item is the first one removed. Think of a stack of plates—add to the top, remove from the top.

Core Operations

• push(x): Add item x to the top.
• pop(): Remove and return the top item.
• peek() or top(): Return (without removing) the top item.
• is_empty(): Check whether the stack has no elements.
• size(): Number of elements in the stack.

Time complexity for push/pop/peek is typically O(1); size can be O(1) if tracked, or O(n) if computed on demand.

Implementations

Array (Dynamic Array)–Based

• Pros: Excellent cache locality, O(1) amortized push, simple implementation.
• Cons: May need resizing; a fixed-capacity array risks overflow.

Linked List–Based

• Pros: Conceptually unbounded until memory is exhausted; push/pop are O(1).
• Cons: Extra memory per node; less cache-friendly.

Underflow occurs when popping an empty stack; always check emptiness or handle exceptions.

Common Use Cases

• Function call stack: Manages active function calls and local variables; recursion builds nested stack frames.
• Depth-first search (DFS): Iterative DFS uses a stack to traverse graphs/trees.
• Parsing and expression evaluation: Convert/evaluate infix/postfix; algorithms like shunting-yard use stacks.
• Balanced parentheses: Check matching brackets with a stack.
• Undo/redo and navigation: Back/forward operations in editors and browsers.
• Backtracking: Systematically explore and revert choices.

Example: Minimal Stack in Python (Dynamic Array)

class Stack:
    def __init__(self):
        self._data = []

    def push(self, x):
        self._data.append(x)

    def pop(self):
        if not self._data:
            raise IndexError("pop from empty stack")
        return self._data.pop()

    def peek(self):
        if not self._data:
            raise IndexError("peek from empty stack")
        return self._data[-1]

    def is_empty(self):
        return not self._data

    def size(self):
        return len(self._data)

Example: Balanced Parentheses

def is_balanced(s):
    pairs = {')': '(', ']': '[', '}': '{'}
    st = []
    for ch in s:
        if ch in '([{':
            st.append(ch)
        elif ch in ')]}':
            if not st or st.pop() != pairs[ch]:
                return False
    return not st

# is_balanced("(a+[b*c]-{d/e})") == True
# is_balanced("(]") == False

Example: Iterative DFS with a Stack

def dfs_iterative(graph, start):
    visited = set()
    order = []
    stack = [start]
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        order.append(node)
        # Push neighbors (reverse to mimic recursive order if desired)
        for nei in reversed(graph.get(node, [])):
            if nei not in visited:
                stack.append(nei)
    return order

Call Stack vs. Stack Data Structure

The call stack in a runtime system stores stack frames for active function calls (return addresses, locals). It is an application of the stack abstraction. Deep or infinite recursion can cause a stack overflow.

Variants and Design Considerations

• Bounded vs. unbounded: Fixed-capacity stacks may overflow; dynamic arrays grow as needed.
• Thread safety: Concurrent stacks need synchronization (locks) or lock-free algorithms.
• Min-stack: Maintain an auxiliary stack to support O(1) getMin().
• Monotonic stack: Maintains increasing/decreasing order to solve range-maximum/minimum or next-greater-element problems.
• Two stacks to make a queue: Amortized O(1) enqueue/dequeue by transferring elements between stacks.

Gotchas

• Check for underflow before pop() or peek().
• For array stacks, watch capacity and resizing costs (amortized O(1)).
• Beware unbounded growth if pushes outnumber pops (memory use).
• In recursion-heavy code, consider converting to an explicit stack to avoid call stack overflow.

Next Topic