LIFO structure for bracket matching, expression evaluation, and next-greater problems.
A stack (LIFO) is fundamental for problems requiring "undo", "nearest boundary", or "deferred processing". It powers expression evaluation, bracket matching, and DFS without recursion.
Push/Pop O(1)
O(n) in the worst case
Learn the core patterns in this topic. Each block explains when to use the pattern, the intuition behind it, and a compact code example.
Use this when the problem requires validating that opening and closing delimiters are properly paired and nested
Push every opening bracket onto the stack, and on each closing bracket check whether the top of the stack holds the matching opener. If not, the sequence is invalid. An empty stack at the end confirms all brackets were matched.
Problem Valid Parentheses. Maintain a map of closing to opening brackets and compare each closing bracket against the stack top.
// Bracket matching — Valid Parentheses
function isValid(s) {
const stack = [];
const pairs = { ")": "(", "]": "[", "}": "{" };
for (const ch of s) {
if ("([{".includes(ch)) stack.push(ch);
else if (stack.pop() !== pairs[ch]) return false;
}
return stack.length === 0;
}Use this when you need O(1) minimum retrieval from a stack in addition to normal push and pop
Maintain a second stack that tracks the minimum at every level: when you push a value, also push the new running minimum onto the secondary stack. When you pop, pop from both. The top of the secondary stack is always the current minimum.
Problem Min Stack. At every push, record the current minimum so getMin never needs to scan the whole stack.
// Min Stack — O(1) getMin using parallel min-tracking stack
class MinStack {
constructor() { this.stack = []; this.minStack = []; }
push(val) {
this.stack.push(val);
const min = this.minStack.length ? Math.min(val, this.minStack.at(-1)) : val;
this.minStack.push(min);
}
pop() { this.stack.pop(); this.minStack.pop(); }
top() { return this.stack.at(-1); }
getMin() { return this.minStack.at(-1); }
}Use this when the problem presents a postfix or reverse-polish-notation expression and asks for the result
Push operands onto the stack; on seeing an operator, pop the top two operands, apply the operator, and push the result back. This matches the evaluation order precisely.
Problem Evaluate Reverse Polish Notation. Pop b and a in that order, apply op(a, b), and push the result.
// Expression evaluation — Evaluate Reverse Polish Notation
function evalRPN(tokens) {
const stack = [];
for (const t of tokens) {
if ("+-*/".includes(t)) {
const b = stack.pop(), a = stack.pop();
if (t === "+") stack.push(a + b);
else if (t === "-") stack.push(a - b);
else if (t === "*") stack.push(a * b);
else stack.push(Math.trunc(a / b));
} else {
stack.push(Number(t));
}
}
return stack[0];
}Use this when you want depth-first traversal of a graph or tree but prefer iteration over recursion to avoid call-stack overflow on large inputs
Push the starting node, then in a loop pop the top, process it, and push its unvisited neighbors. The stack naturally provides LIFO ordering which mirrors recursive DFS.
Problem All Paths From Source to Target. Push paths instead of individual nodes to track the full path as you go.
// Iterative DFS — All Paths From Source to Target
function allPathsSourceTarget(graph) {
const paths = [];
const stack = [[0, [0]]];
while (stack.length) {
const [node, path] = stack.pop();
if (node === graph.length - 1) { paths.push(path); continue; }
for (const next of graph[node])
stack.push([next, [...path, next]]);
}
return paths;
}Use this when the problem involves strings or expressions with nested or repeated structure that must be reconstructed in LIFO order
Push context (counts, accumulated strings) when entering a nested level and pop when leaving it to combine with the outer level.
Problem Decode String. Push the current string and repetition count before each open bracket, then pop and multiply when the close bracket is reached.
// Nested structure decoding — Decode String
function decodeString(s) {
const stack = [];
let curr = "", k = 0;
for (const ch of s) {
if (!isNaN(ch) && ch !== " ") {
k = k * 10 + Number(ch);
} else if (ch === "[") {
stack.push([curr, k]); curr = ""; k = 0;
} else if (ch === "]") {
const [prev, rep] = stack.pop();
curr = prev + curr.repeat(rep);
} else {
curr += ch;
}
}
return curr;
}Use this as the canonical hard stack problem where the stack tracks indices of bars in increasing height order
When a shorter bar is encountered, pop and compute the area of each taller bar that can no longer extend further right. The answer is the maximum area found during all pops.
Problem Largest Rectangle in Histogram. Pop index idx when a shorter bar arrives; the width is determined by the current position and the new stack top.
// Largest Rectangle in Histogram — monotonic increasing stack
function largestRectangleArea(heights) {
const stack = [];
let max = 0;
heights = [...heights, 0]; // sentinel to flush stack
for (let i = 0; i < heights.length; i++) {
while (stack.length && heights[i] < heights[stack.at(-1)]) {
const h = heights[stack.pop()];
const w = stack.length ? i - stack.at(-1) - 1 : i;
max = Math.max(max, h * w);
}
stack.push(i);
}
return max;
}