Python

Stack Using a Python List

The most direct way to use a stack in Python is a plain list. The append() method pushes an element onto the top, and pop() removes and returns the top element. Both operate on the end of the list, which is O(1) amortized.

stack = []

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

top = stack[-1]       # peek: 30
value = stack.pop()   # pop: 30
print(stack)          # [10, 20]

Because list operations at the end are fast and avoid the overhead of a custom class, a bare list is the idiomatic stack in Python. Avoid insert(0, ...) or pop(0), which are O(n) and break stack semantics by using the wrong end. Review push, pop, and peek

Stack Using collections.deque

The collections.deque is a double-ended queue that supports fast appends and pops on either end. Its append() and pop() methods work identically to a list for stack use, but a deque is a better choice when you also need fast access on the left side.

from collections import deque

stack = deque()
stack.append(10)
stack.append(20)

top = stack[-1]       # peek
value = stack.pop()   # pop

A deque maintains a doubly linked list of blocks internally, so no resizing is needed. This makes append and pop O(1) worst case rather than the amortized O(1) of a list. How linked structures avoid resizing

List vs Deque Performance

For a pure stack, a list is usually the right tool. Appending to a list is extremely fast thanks to exponential resizing, and lists have lower memory overhead than deques, which store pointers in a doubly linked structure.

A deque wins when you need to add or remove from both ends, such as a queue or a sliding window. For LIFO-only use, the constant-factor differences are tiny, so choose the simpler list unless profiling shows otherwise.

One practical difference: a list supports random access like stack[i], while a deque supports it too but only in O(1) amortized time on the ends. If you never need indexing, both work fine as a stack. Understand the time complexities

CPython Interpreter Stack

When you run Python, a program called CPython interprets your source and executes bytecode. Internally, CPython maintains several stacks to make this work.

The evaluation stack holds intermediate values while bytecode instructions execute. The frame stack tracks active function calls, pushing a new frame when a function is called and popping it when it returns. Block stacks track control-flow constructs like loops and exceptions. And the call stack is what grows when you call a function recursively.

These internal stacks all follow LIFO, exactly like the stack data structure you use in your own code. Understanding them clarifies why Python reports RecursionError when you go too deep. How the call stack drives function execution

sys.getrecursionlimit() and Stack Depth

Python limits how deep the call stack can grow to protect the underlying C stack used by CPython. The default recursion limit is 1000 and can be inspected or changed with the sys module.

import sys

print(sys.getrecursionlimit())   # 1000

sys.setrecursionlimit(2000)      # raise it (use with care)
print(sys.getrecursionlimit())   # 2000

Raising the limit can let deep recursion run further, but it risks crashing the interpreter if the C stack overflows. Prefer converting deep recursion to an explicit stack or an iterative loop instead. Related Python stack patterns

Common Python Stack Patterns

Balanced Parentheses

A list stack naturally validates matching brackets:

def is_balanced(s):
    stack = []
    pairs = {")": "(", "]": "[", "}": "{"}
    for ch in s:
        if ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
        else:
            stack.append(ch)
    return not stack

Undo History

Push actions as they happen and pop to undo:

history = []

def execute(action):
    action.apply()
    history.append(action)

def undo():
    if history:
        history.pop().revert()

Iterative DFS

Replace recursion with an explicit stack for graph traversal:

def dfs(start):
    stack = [start]
    visited = set()
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        stack.extend(neighbors(node))

Complete Python Stack Class with Type Hints

Here is a clean, typed Stack class you can drop into any project:

from collections.abc import Iterator
from typing import Generic, TypeVar

T = TypeVar("T")

class Stack(Generic[T]):
    def __init__(self) -> None:
        self._data: list[T] = []

    def push(self, item: T) -> None:
        self._data.append(item)

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

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

    def is_empty(self) -> bool:
        return not self._data

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

    def __iter__(self) -> Iterator[T]:
        return reversed(self._data)

stack: Stack[int] = Stack()
stack.push(1)
stack.push(2)
print(stack.peek())      # 2
print(list(stack))       # [2, 1]

Generic type hints make the stack reusable and self-documenting. How the stack stores its elements in memory

Key Takeaway

In Python the list is the idiomatic stack: append and pop on the end give you LIFO in O(1) amortized time. Use deque when you also need fast operations on the other end. And remember that CPython itself is built on stacks, which is why deep recursion eventually raises RecursionError.

Explore all EasyStack guides

Frequently Asked Questions

Should I use a list or a deque for a stack in Python?

For a stack, a list is usually the best choice. appending and popping from the end of a list are O(1) amortized operations, and lists have the lowest memory overhead. A deque also works and is efficient, but for pure LIFO stack usage a list is simpler and slightly faster because deques add a small pointer overhead.

Does Python have a built-in Stack class?

No. Python has no dedicated Stack class, but list.append() and list.pop() already implement LIFO behavior. For a clearer API you can wrap those methods in a small class, or use collections.deque. There is no separate Stack type like Java's java.util.Stack.

What is sys.getrecursionlimit() and how does it relate to the stack?

sys.getrecursionlimit() returns the maximum depth of the Python interpreter stack, how many nested function calls are allowed, with a default of 1000. Exceeding it raises RecursionError. This protects the C stack that CPython runs on from being exhausted by deep recursion.