Stacks & Queues

Stack Fundamentals

LIFO — Last In, First Out

%%{init: {'theme': 'base', 'themeVariables': {'fontSize': '13px', 'fontFamily': 'Inter, -apple-system, sans-serif'}, 'flowchart': {'nodeSpacing': 30, 'rankSpacing': 50, 'padding': 12, 'curve': 'basis'}, 'sequence': {'actorMargin': 60, 'messageMargin': 40}, 'class': {'padding': 12}}}%%
flowchart LR
    subgraph Stack["Stack (top → bottom)"]
        direction TB
        A["5 ← top"] --> B["3"] --> C["8"] --> D["1 ← bottom"]
    end
    Push["push(5)"] -.-> A
    Pop["pop() → 5"] -.-> A

    style A fill:#DCFCE7,stroke:#16A34A,color:#14532D
    style B fill:#DBEAFE,stroke:#2563EB,color:#1E3A5F
    style C fill:#DBEAFE,stroke:#2563EB,color:#1E3A5F
    style D fill:#DBEAFE,stroke:#2563EB,color:#1E3A5F

The Right Way to Use Stacks in Java

// CORRECT — use Deque interface with ArrayDeque
Deque<Integer> stack = new ArrayDeque<>();
stack.push(5);      // pushes to top
stack.pop();        // removes and returns top
stack.peek();       // returns top without removing
stack.isEmpty();    // check before pop/peek

Stack Operations — Complexity

Monotonic Stack Deep Dive

This is the single most valuable stack pattern for FAANG interviews. It converts O(n^2) brute-force "next greater/smaller" problems into elegant O(n) solutions.

The Core Insight

Two Variants

%%{init: {'theme': 'base', 'themeVariables': {'fontSize': '13px', 'fontFamily': 'Inter, -apple-system, sans-serif'}, 'flowchart': {'nodeSpacing': 30, 'rankSpacing': 50, 'padding': 12, 'curve': 'basis'}, 'sequence': {'actorMargin': 60, 'messageMargin': 40}, 'class': {'padding': 12}}}%%
flowchart LR
    subgraph MI["Monotonic Increasing (bottom→top)"]
        direction TB
        M1["3"] --> M2["5"] --> M3["7"]
    end
    subgraph MD["Monotonic Decreasing (bottom→top)"]
        direction TB
        D1["9"] --> D2["6"] --> D3["2"]
    end

    MI ---|"Finds: Next Smaller"| NS["Pop when current < top"]
    MD ---|"Finds: Next Greater"| NG["Pop when current > top"]

    style M1 fill:#DBEAFE,stroke:#2563EB,color:#1E3A5F
    style M2 fill:#DBEAFE,stroke:#2563EB,color:#1E3A5F
    style M3 fill:#DCFCE7,stroke:#16A34A,color:#14532D
    style D1 fill:#DBEAFE,stroke:#2563EB,color:#1E3A5F
    style D2 fill:#DBEAFE,stroke:#2563EB,color:#1E3A5F
    style D3 fill:#DCFCE7,stroke:#16A34A,color:#14532D

Template: Next Greater Element (Monotonic Decreasing Stack)

/**
 * For each element, find the next element to the right that is GREATER.
 * Stack maintains decreasing order (bottom to top).
 * When current > top, current is the "next greater" for top.
 */
public int[] nextGreaterElement(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    Arrays.fill(result, -1); // default: no next greater
    Deque<Integer> stack = new ArrayDeque<>(); // stores INDICES

    for (int i = 0; i < n; i++) {
        // Pop all elements smaller than current — current is their answer
        while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
            int idx = stack.pop();
            result[idx] = nums[i];
        }
        stack.push(i);
    }
    return result;
}

Template: Next Smaller Element (Monotonic Increasing Stack)

/**
 * For each element, find the next element to the right that is SMALLER.
 * Stack maintains increasing order (bottom to top).
 * When current < top, current is the "next smaller" for top.
 */
public int[] nextSmallerElement(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    Arrays.fill(result, -1);
    Deque<Integer> stack = new ArrayDeque<>();

    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && nums[stack.peek()] > nums[i]) {
            int idx = stack.pop();
            result[idx] = nums[i];
        }
        stack.push(i);
    }
    return result;
}

Visual Walkthrough: Daily Temperatures (LC #739)

Given temperatures = [73, 74, 75, 71, 69, 72, 76, 73], find how many days until a warmer temperature.

This is "next greater element" but we return the distance instead of the value.

public int[] dailyTemperatures(int[] temperatures) {
    int n = temperatures.length;
    int[] result = new int[n];
    Deque<Integer> stack = new ArrayDeque<>();

    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]) {
            int idx = stack.pop();
            result[idx] = i - idx;
        }
        stack.push(i);
    }
    return result;
}

Queue & Deque

Queue = BFS

Queues are the backbone of BFS (Breadth-First Search). Every BFS traversal uses a queue to process nodes level by level. For full BFS details, see the Graphs page.

Queue<Integer> queue = new LinkedList<>();  // or new ArrayDeque<>()
queue.offer(startNode);   // enqueue
queue.poll();             // dequeue (returns null if empty)
queue.peek();             // front element without removing

Monotonic Deque — Sliding Window Maximum/Minimum

The monotonic deque pattern solves the "maximum/minimum in a sliding window" problem in O(n) total time. Without it, you need O(n * k) with brute force or O(n log k) with a heap.

The insight: Maintain a deque where elements are in decreasing order. The front always holds the current window's maximum. When sliding the window, remove elements that fall outside, and remove from the back any elements smaller than the new element (they can never be the maximum while the new element exists in the window).

/**
 * Template: Sliding Window Maximum using Monotonic Deque
 * Deque stores INDICES, maintains decreasing order of values.
 */
public int[] maxSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    int[] result = new int[n - k + 1];
    Deque<Integer> deque = new ArrayDeque<>(); // stores indices

    for (int i = 0; i < n; i++) {
        // Remove elements outside the window
        while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
            deque.pollFirst();
        }
        // Remove elements smaller than current (they'll never be max)
        while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
            deque.pollLast();
        }
        deque.offerLast(i);

        // Window is fully formed starting at i >= k-1
        if (i >= k - 1) {
            result[i - k + 1] = nums[deque.peekFirst()];
        }
    }
    return result;
}

Priority Queue (Brief)

A Priority Queue (min-heap/max-heap) is covered in detail on the Heaps & Greedy page. Key point: use PriorityQueue when you need the min/max across the entire dataset, use monotonic deque when you need min/max within a sliding window.

Solved Walkthroughs

Problem 1: Valid Parentheses (LC #20) — Easy

Brute force: Repeatedly remove innermost pairs (), {}, [] until string is empty or no more removals possible. O(n^2).

Insight: A stack naturally handles nesting. Push opening brackets; when you see a closing bracket, the top of the stack must be its matching opener.

The map-based approach (cleaner than if-else chains):

public boolean isValid(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    Map<Character, Character> map = Map.of(
        ')', '(',
        '}', '{',
        ']', '['
    );

    for (char c : s.toCharArray()) {
        if (map.containsKey(c)) {
            // Closing bracket — check match
            if (stack.isEmpty() || stack.pop() != map.get(c)) {
                return false;
            }
        } else {
            // Opening bracket — push
            stack.push(c);
        }
    }
    return stack.isEmpty();
}

Complexity: O(n) time, O(n) space.

Problem 2: Largest Rectangle in Histogram (LC #84) — Hard

This is the hardest monotonic stack problem and a FAANG favorite. If you understand this, every other monotonic stack problem becomes manageable.

Brute force: For each bar, expand left and right to find how far it can extend. O(n^2).

Insight: For each bar, we need to know the "nearest shorter bar on the left" and "nearest shorter bar on the right." The rectangle using bar i as the shortest has width = rightBoundary - leftBoundary - 1 and height = heights[i].

A monotonic increasing stack gives us both boundaries in a single pass.

Step-by-step for heights = [2, 1, 5, 6, 2, 3]:

%%{init: {'theme': 'base', 'themeVariables': {'fontSize': '13px', 'fontFamily': 'Inter, -apple-system, sans-serif'}, 'flowchart': {'nodeSpacing': 30, 'rankSpacing': 50, 'padding': 12, 'curve': 'basis'}, 'sequence': {'actorMargin': 60, 'messageMargin': 40}, 'class': {'padding': 12}}}%%
flowchart LR
    subgraph Histogram
        direction LR
        B0["2"] ~~~ B1["1"] ~~~ B2["5"] ~~~ B3["6"] ~~~ B4["2"] ~~~ B5["3"]
    end
    subgraph Answer["Largest Rectangle = 10"]
        direction LR
        R["heights[2..3] × width 2-5 = 5×2 or heights[2..4]..."]
    end

    style B2 fill:#DCFCE7,stroke:#16A34A,color:#14532D
    style B3 fill:#DCFCE7,stroke:#16A34A,color:#14532D
    style Answer fill:#FEF3C7,stroke:#D97706,color:#78350F

public int largestRectangleArea(int[] heights) {
    int n = heights.length;
    int maxArea = 0;
    Deque<Integer> stack = new ArrayDeque<>(); // monotonic increasing

    for (int i = 0; i <= n; i++) {
        // Use 0 as sentinel for the final flush
        int currentHeight = (i == n) ? 0 : heights[i];

        while (!stack.isEmpty() && heights[stack.peek()] > currentHeight) {
            int height = heights[stack.pop()];
            // Width: from current left boundary to i
            int width = stack.isEmpty() ? i : i - stack.peek() - 1;
            maxArea = Math.max(maxArea, height * width);
        }
        stack.push(i);
    }
    return maxArea;
}

Complexity: O(n) time (each bar pushed/popped at most once), O(n) space.

Problem 3: Sliding Window Maximum (LC #239) — Hard

Brute force: For each window, scan all k elements. O(n * k).

Heap approach: Use a max-heap, lazily remove expired elements. O(n log k).

Optimal — Monotonic Deque: O(n) total.

Insight: We maintain a deque of indices in decreasing order of their values. The front of the deque is always the maximum of the current window. When we slide the window:

1. Remove the front if it's outside the window.
2. Remove elements from the back that are smaller than the incoming element (they can never be the answer while the new element is in the window).
3. Add the new element to the back.

public int[] maxSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    int[] result = new int[n - k + 1];
    Deque<Integer> deque = new ArrayDeque<>();

    for (int i = 0; i < n; i++) {
        // Remove indices outside the window
        while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
            deque.pollFirst();
        }
        // Remove smaller elements from back (they're useless)
        while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
            deque.pollLast();
        }
        deque.offerLast(i);

        if (i >= k - 1) {
            result[i - k + 1] = nums[deque.peekFirst()];
        }
    }
    return result;
}

Complexity: O(n) time, O(k) space.

Stack-Based Patterns Table

Common Mistakes

Practice Problems

Tier 1 — Must Solve (High frequency, builds intuition)

Tier 2 — Solidify the Pattern

Tier 3 — Advanced (Hard problems for strong candidates)

Quick Reference Card

// === STACK (LIFO) ===
Deque<Integer> stack = new ArrayDeque<>();
stack.push(x);          // add to top
stack.pop();            // remove from top (throws if empty)
stack.peek();           // view top (throws if empty)
stack.isEmpty();        // always check before pop/peek

// === QUEUE (FIFO) ===
Queue<Integer> queue = new ArrayDeque<>();
queue.offer(x);         // add to back
queue.poll();           // remove from front (null if empty)
queue.peek();           // view front (null if empty)

// === DEQUE (double-ended) ===
Deque<Integer> deque = new ArrayDeque<>();
deque.offerFirst(x);   // add to front
deque.offerLast(x);    // add to back
deque.pollFirst();     // remove from front
deque.pollLast();      // remove from back
deque.peekFirst();     // view front
deque.peekLast();      // view back

Was this helpful?

Yes Needs more

Thanks for your feedback!

Discussion

Markdown supported Post

Sign in to join the discussion Sign In

Loading comments...