Stacks: LIFO and the Bracket Trick

Цели урока

• Understand the LIFO (Last In, First Out) principle
• Implement a stack on an array and a linked list
• Solve the balanced brackets problem
• Understand the role of the call stack in recursion

Предварительные знания

• Linked lists and their operations

• Linked Lists

2006. Firefox 2.0 shipped Undo for closed tabs. Behind the scenes: a stack of URLs. Today Chrome keeps a navigation stack per tab, VS Code keeps an edit stack per file, Node.js keeps a call stack per async context. One structure, thousands of applications.

• **VS Code Undo/Redo** - stack of edits, Ctrl+Z pops the last change
• **Browser navigation** - back/forward buttons are two stacks of history
• **TypeScript compiler** - checks generic type nesting order via a stack
• **React reconciler** - the Fiber algorithm traverses the component tree via an explicit stack

The call stack and the birth of structured programming

In 1960, ALGOL-60 became the first language with nested procedures and local variables. Storing call contexts demanded a systematic solution, and the call stack emerged as a mandatory runtime component. Edsger Dijkstra worked on ALGOL-60 and formalized the activation record. Sixty years later, V8, CPython, and the JVM still run the same model.

LIFO - Last In, First Out

Every browser Back click pops the last URL off a history stack. Every nested generic resolution in the TypeScript compiler walks a stack. Chrome DevTools dumps the call stack on every error. LIFO sits underneath all of it.

**LIFO** (Last In, First Out) defines a stack: the most recent push is the next pop.

Operations: push, pop, peek

A stack exposes **3 core operations**, all O(1). Three operations form the entire API. V8 rides this same simplicity through millions of function calls per second.

• **push(x)** - place an element on top
• **pop()** - remove and return the top element
• **peek() / top()** - view the top element without removing it

**pop() on an empty stack** is an error! In Node.js this can crash a process with an unhandled exception. Always check isEmpty() before popping.

Implementation: Array or List?

Two implementations cover every case. Both deliver O(1) on all operations. The split shows up in constants and cache behavior. V8 picks array-backed - CPU cache locality makes top-of-stack access dramatically faster.

**Which to choose?** Array: simpler, better cache locality, but may need resizing. List: stable O(1) without resize, but more memory per node (pointer overhead).

Problem: Balanced Brackets

Classic problem: confirm all brackets are **balanced**. The TypeScript compiler runs this check on every file. ESLint runs it too. O(n), single pass. The weapon of choice is a stack.

**Algorithm using a stack:**

1. Opening bracket encountered - push onto the stack
2. Closing bracket encountered - pop and check for match
3. At the end, the stack must be empty

Call Stack - The Function Call Stack

When one function calls another, where does the context go? Onto the **call stack**. Every Node.js process, every Python interpreter, every JVM thread carries its own. A Sentry stack trace is a snapshot of that stack the instant the error fired.

**Stack Overflow** is exactly that - the stack runs out of room. Python defaults to ~1000 frames. Node.js holds around 15,000. Deep recursion without tail-call optimization is a one-way ticket to a crash.

**Debugging**: a stack trace in Sentry/Datadog shows exactly the call stack at the moment of the error - the path from the entry point to the failure.

Implement a function that reverses a string using a stack: ```python def reverse_string(s): # Use a stack to reverse the string pass # reverse_string("hello") -> "olleh" ```

def reverse_string(s): stack = [] # Push all characters onto the stack for char in s: stack.append(char) # Pop them in reverse order result = [] while stack: result.append(stack.pop()) return ''.join(result)

Evaluate an expression in Reverse Polish Notation (RPN): ```python def eval_rpn(tokens): # tokens = ["2", "1", "+", "3", "*"] -> (2+1)*3 = 9 # tokens = ["4", "13", "5", "/", "+"] -> 4+(13/5) = 6 pass ```

def eval_rpn(tokens): stack = [] for token in tokens: if token in '+-*/': b = stack.pop() # Second operand a = stack.pop() # First operand if token == '+': stack.append(a + b) elif token == '-': stack.append(a - b) elif token == '*': stack.append(a * b) elif token == '/': stack.append(int(a / b)) else: stack.append(int(token)) return stack[0]

Implement MinStack - a stack with O(1) getMin(): ```python class MinStack: def __init__(self): pass def push(self, val): pass def pop(self): pass def top(self): pass def getMin(self): # O(1)! pass ```

class MinStack: def __init__(self): self.stack = [] # Main stack self.min_stack = [] # Stack of minimums def push(self, val): self.stack.append(val) # Push to min_stack only if val <= current minimum if not self.min_stack or val <= self.min_stack[-1]: self.min_stack.append(val) def pop(self): val = self.stack.pop() # If removing the current minimum, remove from min_stack too if val == self.min_stack[-1]: self.min_stack.pop() return val def top(self): return self.stack[-1] def getMin(self): return self.min_stack[-1]

Related Topics

The stack is the foundation for many algorithms:

• Queues — FIFO - the opposite principle (First In, First Out)
• DFS — Depth-first search uses a stack
• Backtracking — Any recursion can be rewritten with an explicit stack

Key Ideas

• **LIFO**: last in, first out
• **Operations**: push, pop, peek - all O(1)
• **Implementation**: array (better cache) or linked list (stable O(1))
• **Applications**: undo, brackets, call stack, DFS, backtracking
• **Stack Overflow**: overflow on deep recursion without tail-call optimization

Вопросы для размышления

• Why is a stack ideal for checking balanced brackets?
• How would Redo (redo an action) be implemented alongside Undo?
• Can a queue be implemented using two stacks?

Связанные уроки

• ds-02-linked-lists — Linked stack is built on top of nodes from the lists lesson
• ds-04-queues — Queue is the opposite principle, implementable via two stacks
• alg-13-dfs — DFS traverses a graph using an explicit stack or the call stack
• alg-03-amortized — Amortization explains O(1) for array-based stack with resize
• alg-22-backtracking — Backtracking is an explicit stack of search states
• ds-05-deque — Deque generalizes a stack - push/pop from both ends
• comp-12-lr-parsing