Data Structures

Stacks

A stack is a Last-In, First-Out (LIFO) data structure. Think of a stack of plates — you always add and remove from the top. The last plate placed is the first plate removed.

What Is a Stack?

Text

Push 10 → [10]
Push 20 → [10, 20]
Push 30 → [10, 20, 30]   ← top
Pop    → returns 30      → [10, 20]
Peek   → returns 20 (no removal)

Only two core operations:

Push — add an element to the top.
Pop — remove and return the top element.

Both are O(1).

Python List as Stack

Python’s list already behaves like a stack. append() pushes to the top; pop() removes from the top — both O(1) amortized.

Python

stack = []

# Push
stack.append(10)   # [10]
stack.append(20)   # [10, 20]
stack.append(30)   # [10, 20, 30]

# Peek (look at top without removing)
top = stack[-1]    # 30

# Pop
stack.pop()        # returns 30 → [10, 20]
stack.pop()        # returns 20 → [10]

# Check empty
if not stack:
    print("Stack is empty")

Stack Class

Python

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

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

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

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

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

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

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

s = Stack()
s.push(1); s.push(2); s.push(3)
print(s)         # Stack([1, 2, 3])
print(s.peek())  # 3
print(s.pop())   # 3
print(len(s))    # 2

Use Cases

Use Case	Why a Stack?
Browser back button	Pages visited are pushed; back pops the last page
Undo/redo	Actions pushed; undo pops the last action
Call stack	Function calls pushed; return pops back to caller
Expression evaluation	Operands/operators pushed and popped in LIFO order
DFS (iterative)	Nodes pushed to explore depth-first

Bracket Matching

A classic stack problem: given a string, determine if all brackets are correctly matched and nested.

Python

def is_balanced(s):
    stack = []
    pairs = {')': '(', ']': '[', '}': '{'}

    for ch in s:
        if ch in '([{':
            stack.append(ch)        # push opening bracket
        elif ch in ')]}':
            if not stack or stack[-1] != pairs[ch]:
                return False        # unmatched closing bracket
            stack.pop()             # matched pair → pop opener

    return len(stack) == 0          # stack empty = all matched

print(is_balanced("({[]})"))   # True
print(is_balanced("([)]"))     # False — wrong nesting order
print(is_balanced("{["))       # False — unclosed brackets