Computer Science › Data Structures

Stack

A last-in, first-out collection.

Also known as: LIFO, stack data structure, call stack

A stack is a collection where the last item added is the first one removed (LIFO: last in, first out). Like a pile of plates, you add to the top and take from the top.

stack = []
stack.append("a")        # push
stack.append("b")
stack[-1]                # peek the top → "b"
stack.pop()              # pop → "b"

Operations: push, pop, peek, is empty. All take constant time when built on a dynamic array or a linked list.

Where stacks appear

• The call stack: each function call pushes a frame, and returning pops it. That’s why runaway recursion causes a stack overflow (recursion).
• Undo and redo: each action is pushed, and undo pops the latest.
• Browser back button: history behaves like a stack.
• Matching brackets and parsing: push on (, pop on ).
• Depth-first search: a stack (or recursion) holds the nodes still to visit.
• Evaluating expressions and compilers.

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

Don’t confuse

• The data structure (LIFO) and stack memory, the region where function frames live, compared with the heap (stack vs heap).
• Stack vs queue: last-out first, versus first-out first.

A stack trace is the list of active calls, printed when an error occurs (stack trace).