Stack, Queue and Monotonic Stack Problems: The Complete Interview Guide

Stack and queue problems span the full difficulty range. Valid Parentheses is a common first question in online assessments; Largest Rectangle in Histogram is a Hard that still appears in onsite rounds at product companies. What connects them is a single question: in what order do pending items get resolved? If the newest pending item resolves first, you want a stack. If the oldest does, a queue. If both ends matter, a deque.

This guide moves from basic stack usage through the monotonic stack (the pattern most candidates under-practise) to the monotonic deque, with Java and Python code and dry runs for the trickiest problems.

When to Reach for a Stack, Queue or Deque

Stack and Queue APIs in Java, Python and C++

Matching and Parsing Problems With a Stack

Valid Parentheses (LeetCode 20)

public boolean isValid(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if (c == '(') stack.push(')');           // push the EXPECTED closer
        else if (c == '[') stack.push(']');
        else if (c == '{') stack.push('}');
        else if (stack.isEmpty() || stack.pop() != c) return false;
    }
    return stack.isEmpty();                     // leftover openers mean invalid
}

Pushing the expected closing bracket removes the lookup table. The two failure modes to test: a closer with an empty stack (")(") and leftover openers ("(("). If only one bracket type exists, a counter replaces the stack, a simplification interviewers like to hear.

Evaluate Reverse Polish Notation (LeetCode 150)

def eval_rpn(tokens):
    stack = []
    for t in tokens:
        if t in {"+", "-", "*", "/"}:
            b = stack.pop()
            a = stack.pop()              # order matters for - and /
            if t == "+": stack.append(a + b)
            elif t == "-": stack.append(a - b)
            elif t == "*": stack.append(a * b)
            else: stack.append(int(a / b))   # truncate toward zero, like Java/C++
        else:
            stack.append(int(t))
    return stack[-1]

The Python trap: a // b floors, so -7 // 2 is -4, while the problem expects truncation toward zero (-3). int(a / b) gives the right result for the value ranges in this problem.

Asteroid Collision (LeetCode 735)

Positive asteroids move right, negative move left. A collision can only happen when a left-mover meets right-movers already on the stack, and it may destroy several in a row.

def asteroid_collision(asteroids):
    stack = []
    for a in asteroids:
        alive = True
        while alive and a < 0 and stack and stack[-1] > 0:
            if stack[-1] < -a:
                stack.pop()              # top explodes, keep checking
            elif stack[-1] == -a:
                stack.pop()              # both explode
                alive = False
            else:
                alive = False            # incoming explodes
        if alive:
            stack.append(a)
    return stack

Other members: Decode String (see the string patterns guide), Simplify Path (split on "/", push names, pop on ".."), Backspace String Compare (stack, or two pointers from the end for O(1) space), and Minimum Remove to Make Valid Parentheses (stack of indices of unmatched openers).

Design Problems: Min Stack, Queue via Stacks, Stack via Queues

Min Stack (LeetCode 155)

All operations, including getMin, in O(1). Store with each value the minimum at the time it was pushed; popping restores the previous minimum for free.

class MinStack {
    private final Deque<int[]> stack = new ArrayDeque<>();    // {value, minSoFar}

    public void push(int val) {
        int min = stack.isEmpty() ? val : Math.min(val, stack.peek()[1]);
        stack.push(new int[]{val, min});
    }
    public void pop()    { stack.pop(); }
    public int top()     { return stack.peek()[0]; }
    public int getMin()  { return stack.peek()[1]; }
}

Space optimisation follow-up: use a second stack that only receives a value when it is <= the current minimum (the = matters for duplicates), and pop it only when the popped value equals its top. A further trick stores encoded differences to use a single stack of longs, but it is rarely expected.

Implement Queue Using Stacks (LeetCode 232)

Push into an in stack. To dequeue, if out is empty, pour everything from in into out (which reverses the order), then pop from out.

class MyQueue:
    def __init__(self):
        self.inbox, self.outbox = [], []

    def push(self, x):
        self.inbox.append(x)

    def _shift(self):
        if not self.outbox:
            while self.inbox:
                self.outbox.append(self.inbox.pop())

    def pop(self):
        self._shift()
        return self.outbox.pop()

    def peek(self):
        self._shift()
        return self.outbox[-1]

    def empty(self):
        return not self.inbox and not self.outbox

Amortised analysis is the real question here: each element is moved from inbox to outbox at most once, so n operations cost O(n) total, O(1) amortised, even though a single pop can cost O(n). The reverse problem, Stack Using Queues (225), makes push O(n): enqueue the new item, then rotate the previous n - 1 items behind it so the newest is at the front.

The Monotonic Stack Template

The brute force for "next greater element of every item" scans right from each index: O(n²). The insight: items waiting for their answer form a decreasing sequence. If a smaller item sits below a larger one on the stack, the smaller would already have been answered by the larger. So the waiting items can be kept on a stack in decreasing order, and a new element resolves every waiting item smaller than itself.

Two rules of thumb: store indices, not values (you usually need distances or positions, and you can always look up the value), and decide strict vs non-strict comparison deliberately when duplicates exist. Complexity is O(n) because every index is pushed once and popped at most once.

Next Greater Element Family: Daily Temperatures, Stock Span, Circular Arrays

Daily Temperatures (LeetCode 739)

public int[] dailyTemperatures(int[] t) {
    int[] ans = new int[t.length];
    Deque<Integer> stack = new ArrayDeque<>();       // indices, temperatures decreasing
    for (int i = 0; i < t.length; i++) {
        while (!stack.isEmpty() && t[stack.peek()] < t[i]) {
            int j = stack.pop();
            ans[j] = i - j;                          // days waited
        }
        stack.push(i);
    }
    return ans;                                      // unresolved indices stay 0
}

Dry run on [73, 74, 75, 71, 69, 72, 76, 73]:

Result: [1, 1, 4, 2, 1, 1, 0, 0].

Next Greater Element II (circular array, 503)

Iterate i from 0 to 2n - 1 and use nums[i % n]; only push indices during the first pass. The second pass lets elements near the end find answers that wrap around.

Online Stock Span (901)

Span = number of consecutive days up to today with price at most today's. Keep a stack of (price, span); when a new price arrives, pop every entry with price <= it and add their spans to today's. This is "previous greater" computed online.

class StockSpanner:
    def __init__(self):
        self.stack = []                 # (price, span), prices strictly decreasing

    def next(self, price):
        span = 1
        while self.stack and self.stack[-1][0] <= price:
            span += self.stack.pop()[1]
        self.stack.append((price, span))
        return span

Largest Rectangle in Histogram (LeetCode 84)

For each bar, the largest rectangle that uses that bar's full height extends left and right until the first bar that is shorter. So the answer is max over bars of height × (nextSmaller - prevSmaller - 1): a nearest-smaller problem.

The one-pass version keeps an increasing stack. When the current bar is shorter than the top, the top bar's right boundary is the current index, and its left boundary is the element below it on the stack. A sentinel bar of height 0 at the end flushes everything.

def largest_rectangle_area(heights):
    hs = heights + [0]                  # sentinel flushes the stack at the end
    stack, best = [], 0                 # indices, heights increasing
    for i, h in enumerate(hs):
        while stack and hs[stack[-1]] >= h:
            height = hs[stack.pop()]
            left = stack[-1] if stack else -1      # previous smaller index
            best = max(best, height * (i - left - 1))
        stack.append(i)
    return best

public int largestRectangleArea(int[] heights) {
    int n = heights.length, best = 0;
    Deque<Integer> stack = new ArrayDeque<>();
    for (int i = 0; i <= n; i++) {
        int h = (i == n) ? 0 : heights[i];
        while (!stack.isEmpty() && heights[stack.peek()] >= h) {
            int height = heights[stack.pop()];
            int left = stack.isEmpty() ? -1 : stack.peek();
            best = Math.max(best, height * (i - left - 1));
        }
        stack.push(i);
    }
    return best;
}

Dry run on [2, 1, 5, 6, 2, 3]: at i = 1, bar 2 pops (width 1, area 2). At i = 4 (height 2), bar 6 pops (left = index 2, width 1, area 6), then bar 5 pops (left = index 1, width 2, area 10). At the sentinel, bar 3 gives 3, bar 2 gives 2 × 4 = 8, bar 1 gives 1 × 6 = 6. Answer 10.

Using >= when popping means equal bars are popped early with a too-small width, but the last of the equal bars computes the full width, so the maximum is still correct. Maximal Rectangle (85) applies this per row of a binary matrix, treating each row as a histogram of consecutive 1s above it: O(rows × cols).

The Contribution Technique: Sum of Subarray Minimums

"Sum of min(subarray) over all subarrays" (LeetCode 907) looks like O(n²) at best. Flip it: for each element, count how many subarrays have it as their minimum. If there are L choices for the left end and R for the right end, it contributes arr[i] × L × R.

L = distance to the previous smaller element, R = distance to the next smaller element. With duplicates, make one side strict and the other non-strict, so a subarray with two equal minimums is counted exactly once.

def sum_subarray_mins(arr):
    MOD = 10**9 + 7
    n = len(arr)
    left, right, st = [0] * n, [0] * n, []
    for i in range(n):                         # previous strictly smaller
        while st and arr[st[-1]] > arr[i]:
            st.pop()
        left[i] = i - (st[-1] if st else -1)
        st.append(i)
    st = []
    for i in range(n - 1, -1, -1):             # next smaller-or-equal
        while st and arr[st[-1]] >= arr[i]:
            st.pop()
        right[i] = (st[-1] if st else n) - i
        st.append(i)
    return sum(a * l * r for a, l, r in zip(arr, left, right)) % MOD

For [3, 1, 2, 4]: contributions are 3·1·1 + 1·2·3 + 2·1·2 + 4·1·1 = 3 + 6 + 4 + 4 = 17. The same idea solves Sum of Subarray Ranges (2104: sum of maximums minus sum of minimums). Trapping Rain Water also has a stack solution, where each pop fills a "pool" bounded by the current bar and the new top; the two-pointer solution is in Trapping Rain Water explained.

Greedy Monotonic Stack: Remove K Digits and Friends

To make the smallest possible number by removing k digits (LeetCode 402), a larger digit followed by a smaller one should be removed: the earlier position has more weight. Keep an increasing stack and pop while the top is larger than the incoming digit and removals remain.

public String removeKdigits(String num, int k) {
    StringBuilder st = new StringBuilder();          // used as a stack of chars
    for (char c : num.toCharArray()) {
        while (k > 0 && st.length() > 0 && st.charAt(st.length() - 1) > c) {
            st.deleteCharAt(st.length() - 1);
            k--;
        }
        st.append(c);
    }
    st.setLength(st.length() - k);                   // remaining removals come off the end
    int i = 0;
    while (i < st.length() - 1 && st.charAt(i) == '0') i++;   // strip leading zeros
    String res = st.substring(i);
    return res.isEmpty() ? "0" : res;
}

Example: "1432219", k = 3 gives "1219". Edge cases interviewers test: "10200", k = 1 gives "200" (leading zeros stripped), and "10", k = 2 gives "0". Remove Duplicate Letters (316) adds two conditions to the pop: the top must appear again later, and the incoming letter must not already be in the stack.

Monotonic Deque: Sliding Window Maximum

For the maximum of every window of size k (LeetCode 239), a heap gives O(n log n). A deque of indices with decreasing values gives O(n): the front is always the current maximum, expired indices leave from the front, and smaller values leave from the back because they can never be a maximum while the newer, larger value is in the window.

public int[] maxSlidingWindow(int[] nums, int k) {
    Deque<Integer> dq = new ArrayDeque<>();          // indices, values decreasing
    int[] res = new int[nums.length - k + 1];
    for (int i = 0; i < nums.length; i++) {
        if (!dq.isEmpty() && dq.peekFirst() <= i - k) dq.pollFirst();     // expired
        while (!dq.isEmpty() && nums[dq.peekLast()] < nums[i]) dq.pollLast(); // dominated
        dq.offerLast(i);
        if (i >= k - 1) res[i - k + 1] = nums[dq.peekFirst()];
    }
    return res;
}

from collections import deque

def max_sliding_window(nums, k):
    dq, res = deque(), []
    for i, x in enumerate(nums):
        if dq and dq[0] <= i - k:
            dq.popleft()
        while dq and nums[dq[-1]] < x:
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            res.append(nums[dq[0]])
    return res

For [1, 3, -1, -3, 5, 3, 6, 7], k = 3, the output is [3, 3, 5, 5, 6, 7]. A full walkthrough is in Sliding Window Maximum explained. The same deque, applied to prefix sums, solves Shortest Subarray with Sum at Least K (862) when negatives are present, and it also optimises some DP transitions ("max of the last k dp values").

Plain queues: BFS

Ordinary FIFO queues mostly appear in breadth-first search: shortest paths in unweighted graphs, level-order tree traversal, and multi-source spreading such as Rotting Oranges. Those are covered in graph BFS and DFS problems.

Stack and Queue Practice List

Interview Tips for Stack and Monotonic Stack Questions

1. Start with the brute force and the waste. "For each element I scan right until I find a bigger one: O(n²). Elements I pass over keep getting rescanned."
2. State the invariant. "The stack holds indices still waiting for a greater element, in decreasing order of value." This sentence is what interviewers listen for.
3. Say when answers are produced. "An element gets its answer at the moment it is popped." For the histogram, "the popped bar's rectangle is bounded by the current index and the new top".
4. Justify O(n). Each index is pushed once and popped at most once; the nested while does not make it quadratic.
5. Handle the leftovers. Elements still on the stack at the end have no next greater/smaller element; use a sentinel or a default value.
6. Check duplicates. Ask whether "greater" means strictly greater, and pick < or <= on purpose.

Frequently Asked Questions

Pranjal Jain

Ex-Microsoft SDE · IIT Kanpur · Founder of Prepflix. Helps engineers crack startup and product company interviews across India.