Stacks

A stack is the simplest non-trivial data structure: you can only add to and remove from one end. That single rule (Last-In, First-Out) makes it perfect for everything that has a "do this, then come back to where you were" shape — function calls, undo histories, parsing expressions, depth-first search, matching brackets. Once you see the pattern, you spot it everywhere.

What a Stack Actually Is

A stack stores elements in order and only ever exposes the top. Three operations:

• \push(x)\ — add x on top.
• \pop()\ — remove and return the top.
• \peek()\ — look at the top without removing.

\\\` push(1), push(2), push(3) → bottom [1, 2, 3] top pop() → 3 → bottom [1, 2] top push(4) → bottom [1, 2, 4] top \\\`

That's literally it. Everything you'll do with stacks for the rest of your career is built on those three operations.

Real Analogies (Pick the One That Sticks)

• A stack of plates in a cafeteria — you take the top one, you put new ones on top.
• The call stack of a running program — every function call pushes a frame; every return pops it.
• The Undo button — your last action is the first thing reverted.
• A browser's back button — last visited page is the first you go back to.
• Backtracking in a maze — when you hit a dead end, you undo the most recent decision first.

Daily Operations and Costs

\\\`js class Stack { constructor() { this.data = []; } push(x) { this.data.push(x); } pop() { return this.data.pop(); } peek() { return this.data[this.data.length - 1]; } isEmpty() { return this.data.length === 0; } size() { return this.data.length; } } \\\`

Operation	Time	Notes
---	:---:	---
\push\	O(1) amortised	array may resize
\pop\	O(1)	drop last slot
\peek\	O(1)	read last slot
\isEmpty\	O(1)	check length
search	O(n)	scan

Two implementations both work:

• Array-backed (default everywhere) — fastest in practice because it's cache-friendly. Java \ArrayDeque\, Python \list\, C++ \std::stack\ (over \deque\), JS arrays.
• Linked-list-backed — push/pop on the head. Slightly worse cache performance, but no resize cost; useful when you genuinely don't know the maximum size.

Beginner Mistakes to Skip

1. Popping an empty stack. Always check \isEmpty()\ first or guard the result. Languages handle it differently — Python raises, Java returns null on \peek\, JS returns \undefined\ from \Array.pop()\. 2. Confusing stack with queue. LIFO ≠ FIFO. If processing order matters and you wanted "first added → first served", you wanted a queue. 3. Using \Array.prototype.shift\ thinking it's O(1). \shift\ removes from the *front* and is O(n). \pop\ removes from the *end* and is O(1). Always pop, never shift. 4. Building a stack with a linked list when an array would do. Adds GC pressure and cache misses for no benefit. 5. Forgetting to handle leftover elements. Many monotonic-stack problems have items still in the stack after the loop — those need processing too. 6. Recursing too deep instead of using an explicit stack. Big inputs blow the call stack. When recursion depth could be 10⁵+, convert to a loop with your own stack.

Intermediate: The Call Stack Is a Stack

When you call a function, the runtime pushes a stack frame containing:

• the return address (where to resume),
• the function's parameters,
• its local variables,
• saved registers.

When the function returns, the frame is popped. Recursion = pushing many frames for the same function. Stack overflow is what happens when this stack grows past its allocated memory (typically 1–8 MB).

\\\`js function factorial(n) { if (n <= 1) return 1; return n * factorial(n - 1); } // Calling factorial(4) pushes 4 frames before any returns. \\\`

Iterative versions avoid this. Knowing this is also why "tail-call optimization" matters in some languages — it reuses the current frame instead of pushing a new one.

Intermediate: Parentheses Matching

The "hello world" of stack problems:

\\\`js function isValid(s) { const pair = { ')': '(', ']': '[', '}': '{' }; const st = []; for (const c of s) { if ('([{'.includes(c)) st.push(c); else if (st.pop() !== pair[c]) return false; } return st.length === 0; } \\\`

The pattern generalises: whenever input has nested structure that opens and closes, a stack is the right tool. Same idea handles HTML tag matching, balanced-curly-brace parsing, etc.

Intermediate: Expression Evaluation

Three notations:

Example	Use
Infix	\3 + 4 * 2\	what humans write
Postfix (RPN)	\3 4 2 * +\	what stacks evaluate easily
Prefix (Polish)	\+ 3 * 4 2\	Lisp / classical theory

Evaluating postfix with a stack — push numbers, on operator pop two and push the result:

\\\`text 3 4 2 * + push 3 → [3] push 4 → [3, 4] push 2 → [3, 4, 2]

• → pop 2,4 → push 8 → [3, 8]

+ → pop 8,3 → push 11 → [11] \\\`

To evaluate infix directly, use Dijkstra's Shunting-Yard algorithm — two stacks (operators and operands) and a precedence table. Most production code converts to postfix first because postfix has no precedence to worry about.

Intermediate: Min-Stack in O(1)

Design a stack where \getMin()\ is also O(1). The trick: maintain a second stack of running minima.

\\\`js class MinStack { constructor() { this.s = []; this.m = []; } push(x) { this.s.push(x); this.m.push(this.m.length === 0 ? x : Math.min(x, this.m[this.m.length - 1])); } pop() { this.m.pop(); return this.s.pop(); } top() { return this.s[this.s.length - 1]; } getMin() { return this.m[this.m.length - 1]; } } \\\`

Every push records "the min of *everything from the bottom to me*". Pop removes both in lockstep.

Advanced: The Monotonic Stack

A stack that maintains a sorted order (always increasing or always decreasing as you go bottom-to-top). When the next element would break the order, pop until it fits. This single trick solves a huge family of "next greater / next smaller" problems in O(n).

\\\`js // Next greater element to the right, O(n) function nextGreater(arr) { const n = arr.length, res = new Array(n).fill(-1); const st = []; // stack of indices, values strictly decreasing for (let i = 0; i < n; i++) { while (st.length && arr[st[st.length - 1]] < arr[i]) { res[st.pop()] = arr[i]; } st.push(i); } return res; } \\\`

Every index is pushed once and popped at most once → O(n) total. Same skeleton solves:

• Daily Temperatures (LC 739) — how many days until a warmer day?
• Largest Rectangle in Histogram (LC 84) — the classic hard problem, O(n) with one monotonic stack.
• Stock Span Problem — how many consecutive previous days had price ≤ today's?
• Trapping Rain Water (one of the solutions) — pop bars to fill water above them.

The mental shortcut: when you see "for each element, find the next/previous bigger/smaller one", reach for monotonic stack.

Advanced: DFS Without Recursion

Depth-First Search is naturally recursive — each call pushes a frame. When the input is large (graphs with 10⁶ nodes, deeply nested JSON, huge directories), use an explicit stack:

\\\`js function dfs(start, neighbors) { const visited = new Set([start]); const st = [start]; while (st.length) { const node = st.pop(); process(node); for (const next of neighbors(node)) { if (!visited.has(next)) { visited.add(next); st.push(next); } } } } \\\`

Same algorithm, no risk of blowing the call stack, often faster too.

Advanced: Two Stacks Make a Queue

Classic interview problem. Use \inStack\ for enqueue, \outStack\ for dequeue:

• Enqueue: push to \inStack\ — O(1).
• Dequeue: if \outStack\ empty, pour everything from \inStack\ into \outStack\ (reversing order); pop from \outStack\.

Each element is moved at most twice → amortised O(1) per operation. The reverse problem (queue with two stacks → stack? or stack with two queues?) is also a fun exercise.

Advanced: Stack vs Queue vs Deque

Stack (LIFO)	Queue (FIFO)	Deque (both)
Add	top	rear	either end
Remove	top	front	either end
Use	undo, DFS, parsing	BFS, scheduling	sliding window
In Java	\ArrayDeque\	\ArrayDeque\	\ArrayDeque\
In Python	\list\	\collections.deque\	\collections.deque\
In JS	\Array\	bespoke / lib	bespoke / lib

In Java specifically, prefer \ArrayDeque\ over \Stack\ — \Stack\ is a legacy synchronised class with worse performance.

Practice Path

1. Implement a stack class with \push\, \pop\, \peek\, \isEmpty\, \size\ using a JS array. Test underflow. 2. Solve Valid Parentheses (LC 20). Trace your stack on \"({[]})"\ and \"([)]"\. 3. Implement \MinStack\ (LC 155) with O(1) \getMin\. 4. Solve Daily Temperatures (LC 739) using a monotonic decreasing stack. Trace on \[73, 74, 75, 71, 69, 72, 76, 73]\.