Stack & Queue

"Min stack, queue by stacks, circular deque, sliding window max (deque)."

Deep Dive Tutorial

Stack and queue are the two most fundamental linear data structures after arrays. Stack is LIFO — last in, first out. Queue is FIFO — first in, first out. Most "bracket matching," "expression parsing," "next greater element," and "valid sequence" problems are stack problems. BFS and level-order traversal use queues. Sliding window min/max use a monotonic deque.

Signal in Problem	Structure	Pattern
"Valid/balanced parentheses"	Stack	Push open, pop on close, check match
"Next greater/smaller element"	Monotonic stack	Maintain decreasing/increasing stack
"Evaluate expression"	Stack	Operand/operator stacks or postfix eval
"Level order / BFS"	Queue	Enqueue neighbors, process level by level
"Sliding window min/max"	Monotonic deque	Pop from back when new > back (max deque)
"Nearest smaller to left/right"	Monotonic stack	Process left→right, maintain ascending stack
"Implement queue using stacks"	Two stacks	Inbox stack + outbox stack (lazy transfer)

Stack Pattern: Bracket Matching Template

Universal bracket matching template

// Valid parentheses: push open brackets, pop+check on close brackets
var isValid = function(s) {
    const stack = [];
    const match = { ')': '(', ']': '[', '}': '{' };
    for (const c of s) {
        if ('([{'.includes(c)) stack.push(c);
        else if (stack.pop() !== match[c]) return false;
    }
    return stack.length === 0;
};

// Min add to make valid — count unmatched open/close
var minAddToMakeValid = function(s) {
    let open = 0, close = 0;
    for (const c of s) {
        if (c === '(') open++;
        else if (open > 0) open--;  // matched
        else close++;               // unmatched close
    }
    return open + close;
};

Monotonic Stack Template

lightbulb

Monotonic stack stays sorted (increasing or decreasing). When you push a new element, pop everything that violates the order. The popped elements' "answer" is the new element (it was the next greater/smaller for them).

- Next Greater Element: maintain decreasing stack (pop when new > top)
- Next Smaller Element: maintain increasing stack (pop when new < top)
- Previous Greater: same idea but process left→right; stack gives you what's "still waiting" to the left

Next Greater Element — O(n) with monotonic stack

// For each element, find the next element to the right that is greater
// Brute force: O(n²). Monotonic stack: O(n)
function nextGreaterElement(nums) {
    const result = new Array(nums.length).fill(-1);
    const stack = [];  // indices of elements waiting for their "next greater"
    for (let i = 0; i < nums.length; i++) {
        // pop all elements smaller than nums[i] — nums[i] is their answer
        while (stack.length && nums[stack.at(-1)] < nums[i]) {
            result[stack.pop()] = nums[i];
        }
        stack.push(i);
    }
    // remaining elements in stack have no next greater → -1 (already set)
    return result;
}

// Circular variant: run two passes (or use modulo)
function nextGreaterCircular(nums) {
    const n = nums.length;
    const result = new Array(n).fill(-1);
    const stack = [];
    for (let i = 0; i < 2 * n; i++) {
        while (stack.length && nums[stack.at(-1)] < nums[i % n])
            result[stack.pop()] = nums[i % n];
        if (i < n) stack.push(i);
    }
    return result;
}

Monotonic Deque for Sliding Window

Sliding window maximum — O(n) with deque

// For each window of size k, find the maximum
// Brute force: O(n*k). Deque: O(n)
var maxSlidingWindow = function(nums, k) {
    const deque = [];  // stores indices, front = max of current window
    const result = [];
    for (let i = 0; i < nums.length; i++) {
        // remove elements outside window
        while (deque.length && deque[0] < i - k + 1) deque.shift();
        // remove smaller elements from back (they can never be the max)
        while (deque.length && nums[deque.at(-1)] < nums[i]) deque.pop();
        deque.push(i);
        // window is fully formed when i >= k-1
        if (i >= k - 1) result.push(nums[deque[0]]);
    }
    return result;
};

Worked Problems

Easy

Medium

Medium

Next Greater Element I

Easy

Solve ↗

Largest Rectangle in Histogram

Hard

Solve ↗

Sliding Window Maximum

Hard

Solve ↗

Trapping Rain Water

Hard

Solve ↗

Evaluate Reverse Polish Notation

Medium

Solve ↗

Decode String

Medium

Solve ↗

brain

Stack pattern decision guide:
- "Matching pairs (brackets, tags)" → push open, pop+check on close
- "Next greater/smaller" → monotonic stack, pop when condition breaks
- "Largest rectangle / area under histogram" → monotonic stack with area calculation on pop
- "Expression evaluation" → two stacks (numbers + operators) or postfix evaluation
- "Sliding window max/min" → monotonic deque (front = answer, pop from back when new element is better)
- "Nested structure (decode string, mini interpreter)" → stack saves state at each nesting level

← All Patterns