iwantcoding.com
🔥 Daily 👥 Rooms 🏆 Top Log in Sign up

Stacks

By · Reviewed & last updated · Part of Data Structures & Algorithms

A stack is LIFO — push to the top, pop from the top. Conceptually trivial, but the patterns it unlocks (balanced parens, monotonic stacks, DFS, expression eval) carry a huge fraction of interview problems.

Classic stack problems

EXAMPLE
// 1) Balanced brackets — O(n)
function balanced(s) {
    const stack = [];
    const pair  = { ')':'(', ']':'[', '}':'{' };
    for (const c of s) {
        if ('([{'.includes(c)) stack.push(c);
        else if (')]}'.includes(c)) {
            if (stack.pop() !== pair[c]) return false;
        }
    }
    return stack.length === 0;
}

// 2) Monotonic decreasing stack — next greater element
function nextGreater(nums) {
    const res   = Array(nums.length).fill(-1);
    const stack = [];
    for (let i = 0; i < nums.length; i++) {
        while (stack.length && nums[stack.at(-1)] < nums[i]) {
            res[stack.pop()] = nums[i];
        }
        stack.push(i);
    }
    return res;
}

// 3) Iterative DFS — when recursion would blow the stack
function dfs(root) {
    const stack = [root];
    const order = [];
    while (stack.length) {
        const n = stack.pop();
        if (!n) continue;
        order.push(n.val);
        stack.push(n.right, n.left);  // left popped first
    }
    return order;
}

// 4) Reverse Polish notation evaluator
function rpn(tokens) {
    const st = [];
    const op = { '+': (a,b)=>a+b, '-': (a,b)=>a-b, '*': (a,b)=>a*b, '/': (a,b)=>(a/b)|0 };
    for (const t of tokens) {
        if (t in op) { const b = st.pop(), a = st.pop(); st.push(op[t](a, b)); }
        else st.push(+t);
    }
    return st[0];
}

Why it matters

Monotonic stacks (always increasing or always decreasing) crack a huge family of array problems — next greater, largest rectangle, daily temperatures. Pattern-match for them.

Tip: Tweak the snippet with Try it Yourself », then sit the quiz at the bottom of the page.

Example

Example
// LIFO. Use array push/pop.
const stack = [];
stack.push(1);
stack.push(2);
stack.pop();   // 2
stack.at(-1);  // peek
Try it Yourself »

Discussion

Loading…