Stack

A stack is a LIFO (last-in, first-out) container with two operations: push (add to top) and pop (remove from top). Backed by an array or linked list; Python uses a list for stacks idiomatically.

Complexity

How it works

Maintain a top index. Push appends to the end; pop removes from the end. Because all writes are at one end, both run in O(1). Searching or accessing an element by depth requires scanning the entire stack — O(n).

Python implementation

# A list IS a stack in Python — append/pop are both O(1).
stack = []
stack.append(1)        # push
stack.append(2)
stack.append(3)
print(stack.pop())     # 3
print(stack.pop())     # 2


# Explicit class for clarity:
class Stack:
    def __init__(self):
        self._data = []
    def push(self, x):     # O(1)
        self._data.append(x)
    def pop(self):         # O(1)
        if not self._data:
            raise IndexError("pop from empty stack")
        return self._data.pop()
    def peek(self):        # O(1)
        return self._data[-1]
    def __len__(self):
        return len(self._data)


s = Stack()
s.push("a"); s.push("b")
print(s.peek(), len(s))   # b 2

Trade-offs

• O(1) push and pop — the fastest sequence operations.
• LIFO order is exactly what call stacks, undo histories, and parsers need.
• No random access; lookup is O(n).
• collections.deque is also O(1) at both ends if you ever need a double-ended stack.

← Back to Algorithms