Implementing a Stack in Python

A stack is a linear data structure that follows the LIFO principle: Last In, First Out. Think of a stack of plates — you can only add a new plate to the top, and you can only remove the plate that is currently on top. Stacks show up everywhere in software: undo/redo history, the call stack that tracks function calls in every program you run, browser back-button navigation, and parsing expressions like matched parentheses.

In this lesson you will build a stack from scratch using a plain Python list, understand exactly why the operations are fast, and see it used to solve real problems. We build it manually here (rather than reaching for a library) specifically so you understand what a stack actually does under the hood — later lessons on queues and deques will show you when to prefer collections.deque instead.

Overview: How a Stack Works

A stack supports a small, disciplined set of operations, all focused on one end of the structure, called the top:

• push(item) — add item to the top of the stack.
• pop() — remove and return the item currently on top.
• peek() (sometimes called top()) — look at the top item without removing it.
• is_empty() — check whether the stack has any items.
• size() — count how many items are currently on the stack.

Crucially, a stack never lets you touch anything except the top. You cannot reach into the middle or the bottom without first popping everything above it. That restriction is exactly what makes it useful: it models any process where the most recently added thing must be the first thing undone, whether that’s a series of function calls returning in reverse order, or an editor undoing your most recent keystroke first.

In Python, the natural way to implement a stack is with a built-in list, treating the end of the list as the top of the stack. That choice is not arbitrary — it is the reason a well-implemented stack is fast, which the complexity section below explains.

Time and Space Complexity

Python’s list is a dynamic array: a contiguous block of memory that Python automatically grows when it runs out of room. Appending to or popping from the end of a list touches only the last slot, so no other elements need to shift. That is why treating the end of the list as the stack’s top gives every core operation constant time.

Operation	Time Complexity	Why
push	O(1) amortized	Usually just writes to the next free slot. Occasionally the underlying array is full and Python must allocate a larger array and copy existing elements (O(n)) — but this happens rarely enough (doubling growth) that the average cost per push stays O(1).
pop	O(1)	Removing the last element never requires shifting any other elements.
peek	O(1)	Direct index access to the last element, items[-1].
is_empty / size	O(1)	Python lists track their length, so len() is a constant-time lookup, not a count.

Space complexity is O(n), where n is the number of items currently stored, since the stack must hold a reference to every element it contains.

Contrast this with the mistake covered later in this lesson: if you instead treat index 0 as the top (using insert(0, item) and pop(0)), every push and pop becomes O(n), because every other element in the array has to shift over by one slot to keep the list contiguous.

Examples

Example 1: A Stack class built on a list

This wraps a plain list with a clean interface and guards against invalid operations, which is exactly what you’d want from a reusable data structure.

class Stack:
    def __init__(self) -> None:
        self._items: list[int] = []

    def push(self, item: int) -> None:
        self._items.append(item)

    def pop(self) -> int:
        if self.is_empty():
            raise IndexError("pop from empty stack")
        return self._items.pop()

    def peek(self) -> int:
        if self.is_empty():
            raise IndexError("peek from empty stack")
        return self._items[-1]

    def is_empty(self) -> bool:
        return len(self._items) == 0

    def size(self) -> int:
        return len(self._items)

    def __repr__(self) -> str:
        return f"Stack({self._items})"


def main() -> None:
    stack = Stack()
    stack.push(10)
    stack.push(20)
    stack.push(30)
    print(stack)
    print("Top element:", stack.peek())
    print("Popped:", stack.pop())
    print(stack)
    print("Size:", stack.size())
    print("Is empty:", stack.is_empty())


main()

Output:

Stack([10, 20, 30])
Top element: 30
Popped: 30
Stack([10, 20])
Size: 2
Is empty: False

Tracing it: three pushes build the internal list up to [10, 20, 30]. peek() reports 30 without changing anything. pop() removes and returns 30, leaving [10, 20]. The private _items attribute (the leading underscore is a Python convention signaling "internal, don’t touch directly") is what callers manipulate only through the public methods — this encapsulation is what let us add the empty-stack checks safely.

Example 2: Reversing a string with a stack

Pushing every character and then popping them all naturally reverses their order, since the last character pushed is the first one popped.

class Stack:
    def __init__(self) -> None:
        self._items: list[str] = []

    def push(self, item: str) -> None:
        self._items.append(item)

    def pop(self) -> str:
        return self._items.pop()

    def is_empty(self) -> bool:
        return len(self._items) == 0


def reverse_string(text: str) -> str:
    stack = Stack()
    for char in text:
        stack.push(char)

    reversed_chars = []
    while not stack.is_empty():
        reversed_chars.append(stack.pop())

    return "".join(reversed_chars)


def main() -> None:
    word = "python"
    print(reverse_string(word))


main()

Output:

nohtyp

Pushing p, y, t, h, o, n in order leaves the stack holding n on top. Popping repeatedly yields n, o, h, t, y, p, which "".join() combines into "nohtyp". Note the use of "".join() rather than repeated string concatenation (result += char) — strings are immutable in Python, so concatenating in a loop creates a new string object every iteration, degrading to O(n²) for n characters. Building a list and joining once is O(n).

Example 3: Checking balanced parentheses

This is a classic interview problem, and it’s the textbook use case for a stack: every time you see an opening bracket you push it, and every time you see a closing bracket it must match whatever is currently on top.

def is_balanced(expression: str) -> bool:
    matching = {")": "(", "]": "[", "}": "{"}
    stack: list[str] = []

    for char in expression:
        if char in "([{":
            stack.append(char)
        elif char in ")]}":
            if not stack or stack.pop() != matching[char]:
                return False

    return len(stack) == 0


def main() -> None:
    examples = ["(a + b) * ", "{[()]}", "(a + b]", "((a)"]
    for expr in examples:
        print(f"{expr!r} -> {is_balanced(expr)}")


main()

Output:

'(a + b) * ' -> True
'{[()]}' -> True
'(a + b]' -> False
'((a)' -> False

Here a plain list is used directly as the stack, without a wrapper class — a very common shortcut in real code once you understand what’s happening underneath. For "(a + b]", the ( is pushed, then when ] is encountered the code pops ( and compares it against matching["]"] which is "[" — they don’t match, so the function returns False immediately. For "((a)", one ( is left unmatched on the stack at the end, so len(stack) == 0 is False.

How It Works Step by Step

Let’s trace the internal list state operation by operation, using push(5), push(8), push(3), pop(), push(9), pop(), pop():

1. Start: items = []
2. push(5): append 5 → items = [5]
3. push(8): append 8 → items = [5, 8]
4. push(3): append 3 → items = [5, 8, 3]
5. pop(): remove last element → returns 3, items = [5, 8]
6. push(9): append 9 → items = [5, 8, 9]
7. pop(): remove last element → returns 9, items = [5, 8]
8. pop(): remove last element → returns 8, items = [5]

Notice how 3 came back before 8 even though 8 was pushed earlier — that’s LIFO in action. Also notice every step only ever reads or writes the last slot of the underlying array; nothing else in the list ever moves, which is precisely why each of these operations is O(1).

Common Mistakes

Mistake 1: Using insert(0, item) and pop(0)

It’s tempting to think of the "top" of the stack as index 0, since that reads naturally left to right. This produces correct LIFO behavior, but it is silently very slow:

class SlowStack:
    def __init__(self) -> None:
        self._items: list[int] = []

    def push(self, item: int) -> None:
        self._items.insert(0, item)

    def pop(self) -> int:
        return self._items.pop(0)


def main() -> None:
    stack = SlowStack()
    stack.push(1)
    stack.push(2)
    stack.push(3)
    print(stack.pop())


main()

Output:

3

The output is correct — 3 was pushed last and popped first. The bug isn’t in the result, it’s in the performance: insert(0, item) and pop(0) both have to shift every other element over by one position in memory, making every single push and pop O(n) instead of O(1). On a stack with thousands of elements, this turns an algorithm that should run in milliseconds into one that crawls. The fix is to always operate on the end of the list:

def push(self, item: int) -> None:
    self._items.append(item)


def pop(self) -> int:
    return self._items.pop()

Mistake 2: Popping from an empty stack

Calling .pop() on an empty list raises an IndexError and crashes your program if you don’t check first:

stack: list[int] = []
value = stack.pop()  # IndexError: pop from empty list

The fix is to check is_empty() (or simply check truthiness of the list, since an empty list is falsy) before popping, and decide what should happen instead — return None, raise a clearer custom error, or skip the operation:

def safe_pop(stack: list[int]) -> int | None:
    if not stack:
        print("Stack is empty, nothing to pop")
        return None
    return stack.pop()


def main() -> None:
    stack: list[int] = []
    result = safe_pop(stack)
    print("Result:", result)

    stack.append(42)
    result = safe_pop(stack)
    print("Result:", result)


main()

Output:

Stack is empty, nothing to pop
Result: None
Result: 42

The first call finds an empty list, prints a warning, and returns None. After appending 42, the second call finds a non-empty list and pops normally, returning 42.

Best Practices

• Always push and pop from the end of a Python list (append() / pop()), never the front, to keep every operation O(1).
• Wrap the raw list in a small class (as in Example 1) when you want validation, a descriptive error on underflow, or a cleaner API for other code to call.
• If you genuinely need fast operations at both ends (a deque, not a stack), use collections.deque instead of a list — it’s implemented as a doubly linked list of blocks, giving O(1) operations at both ends.
• Prefer an explicit stack (a list) over recursion when processing very deep or unbounded structures, such as traversing a huge tree or graph — Python’s default recursion limit (around 1000 frames) will raise a RecursionError on deep recursive calls, while an explicit stack has no such limit.
• Always guard pop() and peek() against an empty stack; don’t let an unhandled IndexError surface from deep inside your code.
• Reach for a stack whenever a problem has a "most recent first," "undo," or "matching pairs" shape — balanced brackets, expression evaluation, backtracking, and depth-first search all rely on stack (or call-stack) behavior.

Practice Exercises

1. Min Stack: Design a stack that supports push, pop, peek, and a new operation get_min() that returns the smallest element currently in the stack, all in O(1) time. (Hint: keep a second, auxiliary stack that tracks the minimum seen so far at each push.)
2. Evaluate Postfix Expression: Write a function that evaluates a postfix (Reverse Polish Notation) expression such as "3 4 + 2 *" using a stack of numbers, pushing operands and popping two operands whenever you hit an operator. Expected output for that expression is 14.
3. Valid Parentheses with Multiple Types: Extend the is_balanced function from Example 3 to also report the index of the first unmatched closing bracket, instead of just True/False, so a caller could show the user exactly where their expression broke.

Summary

• A stack is a LIFO (Last In, First Out) structure supporting push, pop, peek, is_empty, and size.
• In Python, implement a stack with a list, treating the end of the list as the top — this gives O(1) amortized push and O(1) pop/peek/is_empty/size, all O(n) space for n elements.
• Using the front of the list instead (insert(0, ...) / pop(0)) is a common but costly mistake — it silently degrades every operation to O(n).
• Always guard against popping or peeking an empty stack to avoid an unhandled IndexError.
• Stacks are the natural tool for matching/undo-style problems: balanced brackets, expression evaluation, and depth-first traversal all lean on stack behavior, including the implicit call stack Python itself uses for function calls.