Data Structures
  • Understand LIFO (Last In, First Out) principle with push/pop in O(1)
  • Implement stacks with arrays or linked lists
  • Apply stacks to undo/redo, balanced parentheses, DFS, expression evaluation

Introduction to Stacks

You're writing a text editor. Users type, make mistakes, hit undo. Each undo reverses the last action.

How do you track actions? An array works, but removing from the end is clumsy. You need the most recent action first.

Enter stacks. Last In, First Out (LIFO). Add actions to the top. Undo pops from the top. Simple.

What's a Stack?

A stack is like a stack of plates. You add plates on top. You take plates from the top.

LIFO: Last thing you put in is the first thing you take out.

stack = []

stack.append('Action 1')  # Push
stack.append('Action 2')
stack.append('Action 3')

# Stack now: ['Action 1', 'Action 2', 'Action 3']
# Top is Action 3

action = stack.pop()  # Pop from top
print(action)  # 'Action 3'

# Stack now: ['Action 1', 'Action 2']

Two operations:

  • push(x): Add x to top
  • pop(): Remove and return top element

Both O(1).

Implementation: Array

Use a dynamic array. Top is the last element.

class Stack:
    def __init__(self):
        self.items = []
    
    def push(self, item):
        self.items.append(item)
    
    def pop(self):
        if self.is_empty():
            raise Exception("Stack is empty")
        return self.items.pop()
    
    def peek(self):
        if self.is_empty():
            return None
        return self.items[-1]
    
    def is_empty(self):
        return len(self.items) == 0
    
    def size(self):
        return len(self.items)

peek() looks at top without removing. Useful for checking what's next.

Implementation: Linked List

Use a singly linked list. Top is the head.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class Stack:
    def __init__(self):
        self.top = None
        self.size = 0
    
    def push(self, item):
        new_node = Node(item)
        new_node.next = self.top
        self.top = new_node
        self.size += 1
    
    def pop(self):
        if self.is_empty():
            raise Exception("Stack is empty")
        data = self.top.data
        self.top = self.top.next
        self.size -= 1
        return data
    
    def peek(self):
        if self.is_empty():
            return None
        return self.top.data
    
    def is_empty(self):
        return self.top is None

Push: create node, point it to current top, make it new top. O(1).

Pop: store top's data, move top to next node. O(1).

Why Stacks?

Undo/Redo: Each action is pushed. Undo pops. Redo uses another stack.

undo_stack = Stack()
redo_stack = Stack()

def do_action(action):
    execute(action)
    undo_stack.push(action)
    redo_stack = Stack()  # Clear redo

def undo():
    if not undo_stack.is_empty():
        action = undo_stack.pop()
        reverse(action)
        redo_stack.push(action)

def redo():
    if not redo_stack.is_empty():
        action = redo_stack.pop()
        execute(action)
        undo_stack.push(action)

Function calls: Call stack. When you call a function, it's pushed. When it returns, it's popped.

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

# Call factorial(3)
# Stack: [factorial(3)]
# Calls factorial(2)
# Stack: [factorial(3), factorial(2)]
# Calls factorial(1)
# Stack: [factorial(3), factorial(2), factorial(1)]
# Calls factorial(0)
# Stack: [factorial(3), factorial(2), factorial(1), factorial(0)]
# Returns 1, pops factorial(0)
# Stack: [factorial(3), factorial(2), factorial(1)]
# Returns 1 * 1, pops factorial(1)
# Stack: [factorial(3), factorial(2)]
# Returns 2 * 1, pops factorial(2)
# Stack: [factorial(3)]
# Returns 3 * 2, pops factorial(3)
# Stack: []
# Final: 6

Balanced parentheses: Check if (), {}, [] are balanced.

def is_balanced(s):
    stack = Stack()
    pairs = {'(': ')', '{': '}', '[': ']'}
    
    for char in s:
        if char in pairs:
            stack.push(char)
        elif char in pairs.values():
            if stack.is_empty():
                return False
            if pairs[stack.pop()] != char:
                return False
    
    return stack.is_empty()

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

Push opening brackets. When you see closing, pop and check match. If stack is empty at end, balanced.

Reversing

Stacks reverse order.

def reverse_string(s):
    stack = Stack()
    for char in s:
        stack.push(char)
    
    result = ""
    while not stack.is_empty():
        result += stack.pop()
    
    return result

print(reverse_string("hello"))  # "olleh"

Push all chars. Pop all chars. LIFO gives reverse order.

Depth-First Search (DFS)

Explore a graph depth-first using a stack.

def dfs(graph, start):
    visited = set()
    stack = Stack()
    stack.push(start)
    
    while not stack.is_empty():
        node = stack.pop()
        
        if node not in visited:
            print(node)
            visited.add(node)
            
            for neighbor in reversed(graph[node]):
                if neighbor not in visited:
                    stack.push(neighbor)

graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': [],
    'F': []
}

dfs(graph, 'A')  # A, C, F, B, E, D (or similar order)

Iterative DFS with a stack instead of recursion.

Expression Evaluation

Evaluate postfix expressions (Reverse Polish Notation).

Infix: 3 + 4 * 2
Postfix: 3 4 2 * +

def eval_postfix(expr):
    stack = Stack()
    tokens = expr.split()
    
    for token in tokens:
        if token.isdigit():
            stack.push(int(token))
        else:
            b = stack.pop()
            a = stack.pop()
            
            if token == '+':
                stack.push(a + b)
            elif token == '-':
                stack.push(a - b)
            elif token == '*':
                stack.push(a * b)
            elif token == '/':
                stack.push(a // b)
    
    return stack.pop()

print(eval_postfix("3 4 2 * +"))  # 11
print(eval_postfix("5 1 2 + 4 * + 3 -"))  # 14

Push operands. When you see operator, pop two operands, apply operator, push result.

When to Use Stacks

Need to reverse order: Stacks naturally reverse.

Nested structures: Parentheses, HTML tags, function calls.

Backtracking: Explore one path, backtrack to try another. Stack tracks choices.

Undo functionality: Store actions, pop to undo.

Arrays vs Linked Lists for Stacks

Array:

  • Simple, fast access
  • Might need resizing (occasional O(n) when full)
  • Better cache locality

Linked List:

  • No resizing needed
  • Slightly more memory (pointers)
  • Constant O(1) always

For most cases, arrays work great. Python's list uses dynamic arrays with good amortization.

Common Mistakes

Popping empty stack: Always check is_empty() before pop().

# Wrong
result = stack.pop()  # Might crash if empty

# Right
if not stack.is_empty():
    result = stack.pop()

Forgetting peek vs pop: peek() doesn't remove. pop() does.

The Beauty

Stacks are simple. Push and pop. LIFO.

But they solve real problems:

  • Undo/redo
  • Function call management
  • Expression parsing
  • Depth-first search
  • Backtracking

Understanding stacks means understanding when you need to reverse order or track nested structures.

Master stacks, and you'll recognize LIFO patterns everywhere.