Stack

Prev Next

A stack is a linear data structure that follows the LIFO principle — Last In, First Out. The only element you're ever allowed to touch is the one that was added most recently. Think of a stack of plates: you place new plates on top, and you take plates off the top too — never from the middle. Undo history, the function call stack, expression evaluation, and backtracking algorithms all rely on exactly this "reverse the order you added things" behavior. In Python, you almost never need to write a stack class at all — a plain list already does the job perfectly.

A Plain List Is Already a Stack

Python's built-in list is a dynamic array under the hood, with spare capacity allocated at the end. That means adding or removing from the end of the list never has to shift any other elements — it's exactly the O(1) operation a stack needs. So instead of building a dedicated stack class, idiomatic Python just uses append() to push and pop() (with no argument) to pop, both operating on the end of the list.

Stack operation	Python equivalent	Time
push(x)	stack.append(x)	O(1) amortized
pop()	stack.pop()	O(1)
peek()	stack[-1]	O(1)
isEmpty()	not stack or len(stack) == 0	O(1)

stack = []

stack.append(10)
stack.append(20)
stack.append(30)

print(stack[-1])   # 30 -- last one in, peek without removing
print(stack.pop())  # 30 -- removed and returned
print(stack.pop())  # 20
print(not stack)   # False -- 10 remains

Time complexity: O(1) amortized for append and O(1) for pop, indexing with [-1], and the emptiness check — none of them touch any element other than the last. Space complexity: O(n) for n elements sitting in the list.

Why "amortized"? A Python list over-allocates its backing array so it doesn't have to resize on every single append. When it does run out of room, growing means allocating a bigger array and copying everything over — an O(n) operation — but this only happens occasionally, and the cost spread out over many appends averages out to O(1) per call.

Writing It as a Class (When You Want the Discipline)

You rarely need to hide a list behind a class just to call it a stack, but doing so can be worthwhile when you want to restrict the interface — stop other code from reaching in and popping from the front, or indexing into the middle by mistake. It's a thin wrapper, nothing more.

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

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

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

    def peek(self):
        if self.is_empty():
            raise IndexError("peek at an empty stack")
        return self._data[-1]

    def is_empty(self):
        return len(self._data) == 0

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

Time complexity: O(1) for push, pop, peek, is_empty, and len — every method delegates directly to the underlying list's own O(1) end operations. Space complexity: O(n) for n stored elements, plus a small constant for the wrapper object itself.

The gotcha to avoid: never use stack.insert(0, x) or stack.pop(0) to treat the front of a list as the top — inserting or removing at index 0 forces Python to shift every remaining element down by one slot, making that single operation O(n). Always push and pop from the end of the list, which is exactly where lists are cheap to grow and shrink. This distinction matters even more in the next lesson, where treating the wrong end as "the important end" is the entire gotcha behind queues.

Worked Problem: Balanced Parentheses Checker

A classic use of a stack: given a string containing (){}[], determine whether every opening bracket has a matching closing bracket in the correct order. The idea — push every opening bracket you see onto the stack. When you hit a closing bracket, it must match whatever is currently on top of the stack; if it doesn't (or the stack is empty), the string is unbalanced. At the end, the stack must be empty too — otherwise some opening bracket was never closed.

def is_balanced(s):
    stack = []
    pairs = {')': '(', ']': '[', '}': '{'}

    for ch in s:
        if ch in ('(', '[', '{'):
            stack.append(ch)                          # opening bracket -- remember it
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False              # mismatch or nothing to match against

    return not stack                                   # every opener must have been closed


print(is_balanced("{[()]}"))   # True
print(is_balanced("{[(])}"))   # False -- wrong order
print(is_balanced("((("))     # False -- never closed

Trace on "{[()]}": push {, push [, push (. Next char is ) — pop gives (, which matches. Next is ] — pop gives [, matches. Next is } — pop gives {, matches. Stack is empty at the end, so the string is balanced.

Time complexity: O(n) — one pass over the string, each character pushed or popped at most once. Space complexity: O(n) worst case — a string of all opening brackets pushes every character onto the stack before the loop ends.

Next up: a stack lets you undo the most recent action; a Queue processes things in the order they arrived — first come, first served. See why a plain list is a great stack but a terrible queue, and what fixes that.

Prev Next