Python Stacks

A stack is one of the simplest yet most useful data structures in programming: a collection where items can only be added or removed from one end, called the top. This behavior is called LIFO (Last-In, First-Out), and it mirrors everyday things like a stack of plates or a web browser’s back button. Python has no dedicated Stack type, but its built-in list, the collections.deque class, and queue.LifoQueue all give you stack behavior with different trade-offs, and this lesson covers all three in depth.

Overview: How Stacks Work

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

• push — add an item to the top of the stack.
• pop — remove and return the item at the top of the stack.
• peek (or top) — look at the top item without removing it.
• is_empty — check whether the stack has any items left.

The defining rule is that you never touch anything except the top. The most recently pushed item is always the first one popped — contrast this with a queue, which is FIFO (First-In, First-Out) and only allows access at opposite ends.

In Python, a list is a dynamic array: internally it holds a pointer to a contiguous block of memory, and CPython over-allocates that block so it has room to grow. Adding or removing an item at the end of a list (via append() or pop() with no argument) only touches that one over-allocated slot, so it runs in O(1) amortized time. If you instead try to add or remove at index 0 (the front), every other element has to be shifted over by one position in memory, which is O(n). This is exactly why a Python list makes an excellent stack (operate on the end) but a poor queue (operating on the front is slow) — and it is the root of the most common stack mistake, covered later.

collections.deque (“deck”, short for double-ended queue) is implemented differently: as a doubly linked list of fixed-size blocks. This gives it O(1) performance at both ends, so it works equally well as a stack or a queue, and the Python documentation explicitly recommends it when you need fast appends and pops from either side.

Syntax

There is no stack keyword; you build stack behavior out of existing types. The three common approaches:

# 1. Plain list (most common, fastest for single-threaded code)
stack = []
stack.append(item)    # push
top_item = stack.pop() # pop (removes and returns the last item)
top_item = stack[-1]   # peek (does not remove)
is_empty = len(stack) == 0

# 2. collections.deque (O(1) at both ends, slightly more overhead)
from collections import deque
stack = deque()
stack.append(item)
top_item = stack.pop()
top_item = stack[-1]

# 3. queue.LifoQueue (thread-safe, for use across multiple threads)
from queue import LifoQueue
stack = LifoQueue()
stack.put(item)
top_item = stack.get()

Type	Push	Pop	Peek	Thread-safe?	Best for
list	append(x)	pop()	lst[-1]	No	General-purpose, fastest
collections.deque	append(x)	pop()	dq[-1]	No	Stack that may also need front access
queue.LifoQueue	put(x)	get()	not built-in	Yes	Producer/consumer across threads

Examples

Example 1: A stack of plates using a plain list

stack = []
stack.append("plate1")
stack.append("plate2")
stack.append("plate3")
print(stack)

top = stack.pop()
print(f"Removed: {top}")
print(stack)

print(f"Current top (peek): {stack[-1]}")
print(f"Stack size: {len(stack)}")
print(f"Is empty: {len(stack) == 0}")

Output:

['plate1', 'plate2', 'plate3']
Removed: plate3
['plate1', 'plate2']
Current top (peek): plate2
Stack size: 2
Is empty: False

Each append() places a new plate on top. pop() with no argument removes the last element — the one most recently added — which is exactly LIFO order. stack[-1] reads the top without removing it.

Example 2: Checking balanced brackets

A classic real-world use of a stack is validating that brackets in an expression are properly nested — used in compilers, code editors, and JSON/HTML parsers.

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

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

    return len(stack) == 0


tests = ["(a+b)*[c-d]", "{[()]}", "([)]", "(a+b"]

for expr in tests:
    print(f"{expr}: {is_balanced(expr)}")

Output:

(a+b)*[c-d]: True
{[()]}: True
([)]: False
(a+b: False

Every opening bracket is pushed. When a closing bracket appears, it must match the bracket most recently pushed (the top of the stack) — if the stack is empty, or the popped bracket doesn’t match, the expression is invalid. At the end, a non-empty stack means some opening brackets were never closed.

Example 3: A reusable Stack class with undo history

For larger programs, wrapping the raw list or deque in a small class prevents accidental misuse (like indexing into the middle of the stack) and gives you a clean, documented interface.

from collections import deque


class Stack:
    def __init__(self):
        self._items = deque()

    def push(self, item):
        self._items.append(item)

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

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

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

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

    def __repr__(self):
        return f"Stack({list(self._items)})"


history = Stack()
for action in ["open_file", "bold_text", "insert_image"]:
    history.push(action)
    print(f"Did: {action} -> {history}")

print(f"\nUndo: {history.pop()}")
print(f"Undo: {history.pop()}")
print(f"Remaining history: {history}")
print(f"Actions left: {len(history)}")

Output:

Did: open_file -> Stack(['open_file'])
Did: bold_text -> Stack(['open_file', 'bold_text'])
Did: insert_image -> Stack(['open_file', 'bold_text', 'insert_image'])

Undo: insert_image
Undo: bold_text
Remaining history: Stack(['open_file'])
Actions left: 1

This is exactly how an application’s undo feature works: every action is pushed onto a history stack, and undoing pops the most recent action first. Wrapping deque in a class also means pop() raises a clear, custom-ish error instead of silently returning the wrong thing if the stack is empty.

Under the Hood

Understanding the internals helps you choose the right tool:

• List growth: CPython lists over-allocate extra capacity whenever they grow, so most append() calls just write into already-reserved memory — O(1) amortized. Occasionally the list must be resized and every element copied to a new, larger block, but this happens rarely enough that the average cost stays O(1).
• List shrink: pop() (from the end) simply decrements the length and returns the last item — no memory is moved.
• deque blocks: a deque is a doubly linked list of small fixed-size arrays (“blocks”). Pushing or popping from either end only touches the block at that end, which is why both ends are O(1) — unlike a list, there is no shifting cost even at the front.
• LifoQueue locking: queue.LifoQueue wraps a list with a threading.Lock (and condition variables) so multiple threads can safely push and pop at once. That safety costs real overhead per call, so it’s only worth using when threads genuinely share the stack.

Common Mistakes

Mistake 1: Using insert(0, x) / pop(0) as a “stack”

It’s tempting to treat the front of a list as the top of the stack, but every insert or pop at index 0 forces Python to shift every remaining element down by one slot — O(n) instead of O(1).

# Inefficient: index-0 operations shift every other element
stack = []
stack.insert(0, "a")
stack.insert(0, "b")
stack.insert(0, "c")
print(stack)
print(stack.pop(0))

Output:

['c', 'b', 'a']
c

This works, but on a stack with thousands of items it is dramatically slower than the correct approach. Always treat the end of the list as the top:

stack = []
stack.append("a")
stack.append("b")
stack.append("c")
print(stack)
print(stack.pop())

Mistake 2: Popping an empty stack without checking

Calling pop() on an empty list raises an IndexError and will crash your program if you don’t anticipate it.

stack = []
try:
    stack.pop()
except IndexError as e:
    print(f"Error: {e}")

Output:

Error: pop from empty list

In real code, either check if stack: (or is_empty() on a custom class) before popping, or wrap the call in a try/except IndexError block, depending on whether an empty stack is an expected condition or a genuine bug.

Best Practices

• Use a plain list for single-threaded stacks — it’s the simplest and fastest option in CPython.
• Reach for collections.deque only when you specifically need guaranteed O(1) behavior at both ends, or may also use it as a queue.
• Never use insert(0, x) / pop(0) to simulate a stack; always operate on the end of the list with append() / pop().
• Check is_empty() (or catch IndexError) before popping, so an empty stack is a handled case, not a crash.
• Use queue.LifoQueue only when multiple threads genuinely share the stack; its locking adds overhead you don’t need otherwise.
• Wrap raw list/deque logic in a small class (like the Stack example above) so callers can’t accidentally index into the middle of the stack and break the LIFO discipline.
• Name stack variables after their purpose (undo_stack, call_stack, bracket_stack) so the LIFO intent is obvious to future readers.

Practice Exercises

• Exercise 1: Write a function reverse_string(s) that reverses a string by pushing every character onto a stack (a list) and then popping them back off, without using slicing like s[::-1]. For "hello" it should return "olleh".
• Exercise 2: Write a function is_html_balanced(tags) that takes a list of tag strings like ["<div>", "<p>", "</p>", "</div>"] and returns True if every opening tag has a matching closing tag in the correct order, using a stack the same way the bracket checker did.
• Exercise 3: Implement a MinStack class with push(x), pop(), and get_min() methods, where get_min() runs in O(1) time. Hint: keep a second internal stack that tracks the minimum value seen at each level alongside the main stack.

Summary

• A stack is a LIFO (Last-In, First-Out) structure supporting push, pop, peek, and is_empty.
• A plain Python list makes an efficient stack when you operate on the end with append() and pop() — both are O(1) amortized.
• collections.deque offers guaranteed O(1) operations at both ends and is preferred when you also need front access.
• queue.LifoQueue adds thread-safety via locking, useful only when multiple threads share the stack.
• Never use insert(0, x) / pop(0) to simulate a stack — that’s O(n) and defeats the purpose.
• Real-world uses include undo/redo history, balanced-bracket checking, expression evaluation, and function call tracking.