Stack — Explained with Examples

A stack is a LIFO (Last-In-First-Out) data structure where elements are added and removed from the top, like a stack of plates.

Stacks support three primary operations: push (add to top), pop (remove from top), and peek/top (view top without removing). All operations are O(1). Stacks can be implemented with arrays or linked lists. The call stack is a real-world stack that tracks function calls — each call pushes a frame, each return pops it.

Think of a stack like a pile of cafeteria trays. You add clean trays to the top, and the first tray you grab is the one most recently added. You never pull from the bottom — that would be inefficient and messy.

Stacks are fundamental in expression evaluation (matching parentheses, postfix notation), depth-first search, undo/redo systems, and backtracking algorithms like maze solving.

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

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

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

    def peek(self):
        if not self.is_empty():
            return self.items[-1]

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

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

# Parentheses matching
def is_balanced(expression):
    stack = Stack()
    pairs = {')': '(', ']': '[', '}': '{'}
    for char in expression:
        if char in '([{':
            stack.push(char)
        elif char in ')]}':
            if stack.is_empty() or stack.pop() != pairs[char]:
                return False
    return stack.is_empty()

print(is_balanced("([])"))     # True
print(is_balanced("([)]"))     # False

The call stack is why infinite recursion causes stack overflow — each call consumes memory, and eventually the call stack limit is reached.

Queue, Linked List, DFS, Recursion

Queue vs Stack