Stack

A stack is a LIFO (last-in, first-out) container with two operations: push (add to top) and pop (remove from top). Backed by an array or linked list; Python uses a list for stacks idiomatically.

1. Complexity

2. How it works

Maintain a top index. Push appends to the end; pop removes from the end. Because all writes are at one end, both run in O(1). Searching or accessing an element by depth requires scanning the entire stack — O(n).

3. Python implementation

# A list IS a stack in Python — append/pop are both O(1).
stack = []
stack.append(1)        # push
stack.append(2)
stack.append(3)
print(stack.pop())     # 3
print(stack.pop())     # 2


# Explicit class for clarity:
class Stack:
    def __init__(self):
        self._data = []
    def push(self, x):     # O(1)
        self._data.append(x)
    def pop(self):         # O(1)
        if not self._data:
            raise IndexError("pop from empty stack")
        return self._data.pop()
    def peek(self):        # O(1)
        return self._data[-1]
    def __len__(self):
        return len(self._data)


s = Stack()
s.push("a"); s.push("b")
print(s.peek(), len(s))   # b 2

4. Trade-offs

• O(1) push and pop — the fastest sequence operations.
• LIFO order is exactly what call stacks, undo histories, and parsers need.
• No random access; lookup is O(n).
• collections.deque is also O(1) at both ends if you ever need a double-ended stack.

5. Step-by-step trace

Every operation in the trace touches only the rightmost cell, the top. That is why push and pop are O(1) on a dynamic array: appending to the end needs no shifting, and Python's list over-allocates capacity so that a resize happens only occasionally, making append O(1) amortised. Peeking at the top is stack[-1]. Reading the element five positions below the top is possible with a Python list but is not part of the stack abstraction; a pure stack only exposes the top.

6. Where stacks appear

The program call stack is the most important example: each function call pushes a frame with its arguments and local variables, and returning pops it. Recursion is therefore implicit stack use, and any recursive algorithm (DFS, tree traversal, quicksort) can be rewritten with an explicit stack. Editors keep undo history as a stack of actions. Parsers and compilers use stacks to match nested brackets, evaluate postfix expressions, and implement the shunting-yard algorithm for operator precedence. Browsers model the back button as a stack of visited pages.

A further family of problems uses a monotonic stack: a stack whose contents are kept in increasing or decreasing order by popping anything that would break the order before pushing. It answers "next greater element", "largest rectangle in a histogram" and "daily temperatures" style questions in O(n), because every element is pushed once and popped at most once. The amortised argument is the same one used for dynamic-array append: an individual step may pop many items, but the total number of pops can never exceed the number of pushes.

def next_greater(nums):
    res, stack = [-1] * len(nums), []   # stack holds indexes
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:
            res[stack.pop()] = x
        stack.append(i)
    return res

print(next_greater([2, 1, 2, 4, 3]))  # [4, 2, 4, -1, -1]

Stacks also act as the bridge between recursion and iteration. Any recursive function can be converted by pushing what would have been the arguments of the recursive call and looping until the stack is empty. The conversion is worthwhile when recursion depth may exceed the interpreter limit or when you need to pause and resume a traversal, as generators and iterators over trees do.

7. Worked example: balanced brackets

def balanced(s: str) -> bool:
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for ch in s:
        if ch in '([{':
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack

print(balanced("{[()()]}"))   # True
print(balanced("([)]"))       # False
print(balanced("(("))         # False

Each opening bracket is pushed; each closing bracket must match whatever was opened most recently. The input is balanced only if every close matched and the stack is empty at the end. The algorithm is O(n) time and O(n) space in the worst case (all openers).

8. Choosing an implementation

9. Pitfalls

• Popping an empty list raises IndexError; check if stack: first or catch the exception.
• Using list.pop(0) or insert(0, x) turns it into an O(n) operation; keep the top at the end.
• Unbounded recursion is an unbounded stack: deep input can overflow the call stack where an explicit stack on the heap would not.

A subtler issue is confusing a stack with a queue when translating an algorithm. Swapping a stack for a FIFO queue in a graph search changes DFS into BFS, and the code still runs and still visits every node, so the bug only shows up as wrong output order or a non-shortest path. Name the variable for its discipline (stack or queue) and use append/pop versus append/popleft consistently.

10. Related topics

• Queue
• Array
• Singly Linked List
• Depth-first search

← Back to Algorithms

Featured Videos