10. Stacks — LIFO Data Structure

What problem does this solve? You need to reverse the order of operations — the most recently added item should be processed first. Think undo in a text editor, the back button in a browser, or matching parentheses in code.

1. The Stack ADT — Last In, First Out (LIFO)

Mental Model

Interface

2. Array-Based Stack Implementation

How It Works

python
Run Inline
# runnable
class ArrayStack:
    """Stack implementation using Python list (dynamic array)."""
    def __init__(self):
        self._data = []
    def __len__(self):
        return len(self._data)
    def __repr__(self):
        return " → ".join(str(x) for x in reversed(self._data)) + " (top)"
    def is_empty(self):
        return len(self._data) == 0
    def push(self, item):
        """Add item to top of stack. O(1) amortized."""
        self._data.append(item)
    def pop(self):
        """Remove and return top item. O(1) amortized."""
        if self.is_empty():
            raise IndexError("Pop from empty stack")
        return self._data.pop()
    def peek(self):
        """Return top item without removing. O(1)."""
        if self.is_empty():
            raise IndexError("Peek from empty stack")
        return self._data[-1]
# Test
s = ArrayStack()
s.push(10)
s.push(20)
s.push(30)
print(f"Stack: {s}")        # 30 → 20 → 10 (top)
print(f"Peek: {s.peek()}")  # 30
print(f"Pop: {s.pop()}")    # 30
print(f"Stack: {s}")        # 20 → 10 (top)
print(f"Empty: {s.is_empty()}")  # False

Trace of Operations

pseudo
Operation     Stack (top is rightmost)    Returns
push(10)      [10]
push(20)      [10, 20]
push(30)      [10, 20, 30]
peek()        [10, 20, 30]                30
pop()         [10, 20]                    30
pop()         [10]                        20
push(40)      [10, 40]
pop()         [10]                        40

3. Linked List-Based Stack Implementation

How It Works

python
Run Inline
# runnable
class Node:
    def __init__(self, data, next_node=None):
        self.data = data
        self.next = next_node
class LinkedStack:
    """Stack implementation using singly linked list."""
    def __init__(self):
        self._head = None
        self._size = 0
    def __len__(self):
        return self._size
    def __repr__(self):
        nodes = []
        curr = self._head
        while curr:
            nodes.append(str(curr.data))
            curr = curr.next
        return " → ".join(nodes) + " (top)"
    def is_empty(self):
        return self._size == 0
    def push(self, item):
        """Add item to top. O(1)."""
        self._head = Node(item, self._head)
        self._size += 1
    def pop(self):
        """Remove and return top item. O(1)."""
        if self.is_empty():
            raise IndexError("Pop from empty stack")
        data = self._head.data
        self._head = self._head.next
        self._size -= 1
        return data
    def peek(self):
        """Return top item without removing. O(1)."""
        if self.is_empty():
            raise IndexError("Peek from empty stack")
        return self._head.data
# Test
s = LinkedStack()
s.push(10)
s.push(20)
s.push(30)
print(f"Linked stack: {s}")  # 30 → 20 → 10 (top)

4. Classic Stack Applications

Application 1: Balanced Parentheses

python
Run Inline
# runnable
def is_balanced(expr):
    """Check if parentheses, braces, brackets are balanced.
    Uses stack to match opening/closing delimiters.
    """
    matching = {')': '(', '}': '{', ']': '['}
    stack = []
    for char in expr:
        if char in '({[':
            stack.append(char)
        elif char in ')}]':
            if not stack or stack[-1] != matching[char]:
                return False
            stack.pop()
    return len(stack) == 0
# Test
print(is_balanced("()"))           # True
print(is_balanced("()[]{}"))       # True
print(is_balanced("([)]"))         # False
print(is_balanced("((()))"))       # True
print(is_balanced("("))            # False

Application 2: Postfix Expression Evaluation

python
Run Inline
# runnable
def evaluate_postfix(expr):
    """Evaluate postfix (Reverse Polish Notation) expression.
    Example: "3 4 + 2 *" = (3 + 4) * 2 = 14
    """
    stack = []
    operators = {'+': lambda a, b: a + b,
                 '-': lambda a, b: a - b,
                 '*': lambda a, b: a * b,
                 '/': lambda a, b: a / b}
    for token in expr.split():
        if token in operators:
            b = stack.pop()
            a = stack.pop()
            result = operators[token](a, b)
            stack.append(result)
        else:
            stack.append(float(token))
    return stack[0]
print(evaluate_postfix("3 4 + 2 *"))       # 14.0
print(evaluate_postfix("4 5 + 3 * 2 -"))   # (4+5)*3-2 = 25.0
print(evaluate_postfix("2 3 1 * + 9 -"))   # 2+(3*1)-9 = -4.0

Application 3: Infix to Postfix Conversion

python
Run Inline
# runnable
def infix_to_postfix(expr):
    """Convert infix expression to postfix using Shunting Yard algorithm."""
    precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}
    stack = []
    output = []
    for token in expr.split():
        if token.isnumeric():
            output.append(token)
        elif token == '(':
            stack.append(token)
        elif token == ')':
            while stack and stack[-1] != '(':
                output.append(stack.pop())
            stack.pop()  # Remove '('
        else:  # Operator
            while (stack and stack[-1] != '(' and
                   precedence.get(stack[-1], 0) >= precedence.get(token, 0)):
                output.append(stack.pop())
            stack.append(token)
    while stack:
        output.append(stack.pop())
    return ' '.join(output)
print(infix_to_postfix("3 + 4 * 2"))         # 3 4 2 * +
print(infix_to_postfix("( 3 + 4 ) * 2"))     # 3 4 + 2 *
print(evaluate_postfix(infix_to_postfix("( 3 + 4 ) * 2")))  # 14.0

Application 4: DFS (Depth-First Search) — Preview

python
Run Inline
# runnable
def dfs_stack(graph, start):
    """DFS traversal using explicit stack (instead of recursion)."""
    visited = set()
    stack = [start]
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            print(f"Visiting: {vertex}")
            # Add unvisited neighbors (reverse order for original order)
            for neighbor in reversed(graph[vertex]):
                if neighbor not in visited:
                    stack.append(neighbor)
    return visited
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}
print("DFS traversal starting from A:")
dfs_stack(graph, 'A')
# Output: A, C, F, B, E, D (or A, B, D, E, F, C depending on neighbor order)

5. Performance Comparison

6. Common Bugs

python
Run Inline
# BUG 1: Pop from empty stack
s = ArrayStack()
# s.pop()  # IndexError: Pop from empty stack
# FIX: Always check is_empty() before pop
# BUG 2: Not resetting the stack after use
def process(expr):
    stack = []
    for c in expr:
        if c == '(':
            stack.append(c)
        elif c == ')':
            if not stack:  # Missing this check!
                return False
            stack.pop()
    # Forgot to check if stack is empty at end
    return True  # Should be return len(stack) == 0
# BUG 3: Confusing LIFO vs FIFO
# Using a list as a queue by inserting at front:
bad_queue = []
bad_queue.insert(0, 1)  # O(n) — slow!
bad_queue.insert(0, 2)
bad_queue.pop()  # Gets 1 (FIFO), but slow insert!

Practice Questions

python
Run Inline
s = []
for i in range(5):
    s.append(i)
for _ in range(5):
    print(s.pop(), end=' ')

Answers

A1.

pseudo
Token: 5 push → [5]
Token: 1 push → [5, 1]
Token: 2 push → [5, 1, 2]
Token: + pop 2, pop 1 → push 3 → [5, 3]
Token: 4 push → [5, 3, 4]
Token: * pop 4, pop 3 → push 12 → [5, 12]
Token: + pop 12, pop 5 → push 17 → [17]
Token: 3 push → [17, 3]
Token: - pop 3, pop 17 → push 14 → [14]
Result: 14

A2. Final stack has one value: the result of ((a+b)*c)-d.

A3.

python
Run Inline
def reverse_string(s):
    stack = []
    for c in s:
        stack.append(c)
    return ''.join(stack.pop() for _ in range(len(stack)))

A4. Maintain an auxiliary stack that tracks the minimum. On push, push min(x, min_stack[-1]) to min_stack. On pop, pop from both.

A5. 4 3 2 1 0 (reversed order — LIFO).

A6. A B + C D - *

A7. Function calls are naturally LIFO: the last called function returns first. The call stack stores return addresses, local variables, and arguments for each active function call.

A8.

python
Run Inline
class StackWithQueues:
    def __init__(self):
        self.q1, self.q2 = [], []
    def push(self, x):
        self.q2.append(x)
        while self.q1:
            self.q2.append(self.q1.pop(0))
        self.q1, self.q2 = self.q2, self.q1
    def pop(self):
        return self.q1.pop(0) if self.q1 else None

A9. ([)] → False. The closing ) doesn't match the top [, so it returns False. The stack correctly detects this structural issue.

A10. Maintain a stack of "states" (the document's state before each action). On Ctrl+Z, pop the most recent state and restore it. A doubly linked list or two-stack approach (undo stack + redo stack) supports both undo and redo. Join Discord Previous09. Linked Lists — Singly, Doubly, CircularNext11. Queues — FIFO Data Structure