Stacks

Overview

A stack is a Last-In, First-Out (LIFO) collection: the most recently added item is the first one removed. The core operations are push (add to top), pop (remove from top), and peek (look at top), all O(1). Python lists work well as stacks because append and pop operate on the end in amortized O(1) time.

Syntax / Usage

Use a list, treating the end as the top of the stack.

stack = []

stack.append("a")   # push -> O(1)
stack.append("b")
stack.append("c")

top = stack[-1]     # peek -> O(1) -> "c"
item = stack.pop()  # pop  -> O(1) -> "c"

print(len(stack) == 0)  # is the stack empty?

Examples

Check for balanced parentheses using a stack:

def is_balanced(text):
    stack = []
    pairs = {")": "(", "]": "[", "}": "{"}
    for ch in text:
        if ch in "([{":
            stack.append(ch)      # push open bracket
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack

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

Reverse a string by pushing then popping each character:

def reverse(text):
    stack = list(text)          # push all chars
    out = ""
    while stack:
        out += stack.pop()      # pop in reverse order
    return out

print(reverse("stack"))  # "kcats"

Common Mistakes

• Popping from an empty stack, raising IndexError
• Using pop(0) to remove from the bottom, which is O(n), not LIFO
• Confusing stack (LIFO) behavior with queue (FIFO) behavior
• Forgetting to check if stack: before pop or peek
• Relying on the stack to preserve insertion order for iteration

See Also

data-structures-arrays data-structures-queues data-structures-linked-lists