Stack

A stack is a collection where elements are added and removed from the same end — the top. It follows LIFO order — Last In, First Out. The most recently added item is always the first one removed.

Think of a stack like a pile of plates. You can only add a plate to the top, and you can only remove the top plate. To get the bottom plate, you would have to remove every plate above it first.

push(4)        top → [4]
push(7)        top → [7]
                      [4]
push(2)        top → [2]
                      [7]
                      [4]
pop()  → 2     top → [7]
                      [4]

Core operations

Every operation is O(1) — there is no walking or shifting needed. You only ever touch the top.

Implementing a stack in Python

Python's list already works perfectly as a stack:

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

    def push(self, item):
        self.items.append(item)        # add to end = push

    def pop(self):
        if self.is_empty():
            raise IndexError("pop from empty stack")
        return self.items.pop()        # remove from end = pop

    def peek(self):
        if self.is_empty():
            raise IndexError("peek from empty stack")
        return self.items[-1]          # look at last item

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

    def size(self):
        return len(self.items)


s = Stack()
s.push(10)
s.push(20)
s.push(30)
print(s.peek())   # 30
print(s.pop())    # 30
print(s.pop())    # 20
print(s.size())   # 1

Real use cases

Function call stack — every time a function calls another function, the call is pushed onto the call stack. When the function returns, it is popped.

Undo / redo — text editors push every action onto a stack. Undo pops the most recent action.

Browser back button — each page visited is pushed. Back pops the most recent page.

Balanced brackets — checking if (){}[] are properly matched (see valid-parentheses in the exercises section).

Depth-first search — DFS uses a stack (explicit or via recursion) to explore as deep as possible before backtracking.

Expression evaluation — converting and evaluating infix, postfix, and prefix expressions.

Implementing with collections.deque

For production code, collections.deque is often preferred over list for stack operations — it has guaranteed O(1) operations at both ends:

from collections import deque

stack = deque()
stack.append(10)    # push
stack.append(20)
stack.append(30)
print(stack.pop())  # 30 — pop
print(stack[-1])    # 20 — peek

Complexity

Overall space for n elements: O(n)