Stack and Queue Problems

Stacks and queues look simple, but they power some of the most elegant interview solutions. The monotonic stack and the monotonic deque in particular turn many O(n²) problems into O(n) — and interviewers love them.

1. Validate parentheses.

Push opening brackets; for each closing bracket, the stack top must be its matching opener. The string is valid if the stack ends empty.

boolean isValid(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        switch (c) {
            case '(' -> stack.push(')');
            case '[' -> stack.push(']');
            case '{' -> stack.push('}');
            default -> { if (stack.isEmpty() || stack.pop() != c) return false; }
        }
    }
    return stack.isEmpty();
}

2. Design a stack that returns the minimum in O(1).

Keep a second stack (or store pairs) holding the minimum so far at each level. Push and pop both stacks together.

class MinStack {
    private final Deque<int[]> stack = new ArrayDeque<>();   // {value, minSoFar}
    void push(int x) {
        int min = stack.isEmpty() ? x : Math.min(x, stack.peek()[1]);
        stack.push(new int[] { x, min });
    }
    void pop() { stack.pop(); }
    int top() { return stack.peek()[0]; }
    int getMin() { return stack.peek()[1]; }
}

3. Find the next greater element for every item.

Monotonic stack: keep indexes of items still waiting for a greater value, in decreasing order. Each new value resolves all smaller waiting items. Every index is pushed and popped once — O(n).

int[] nextGreater(int[] nums) {
    int[] result = new int[nums.length];
    Arrays.fill(result, -1);
    Deque<Integer> stack = new ArrayDeque<>();          // indexes
    for (int i = 0; i < nums.length; i++) {
        while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
            result[stack.pop()] = nums[i];
        }
        stack.push(i);
    }
    return result;
}
// [2, 1, 2, 4, 3] -> [4, 2, 4, -1, -1]

4. How many days until a warmer temperature?

The same monotonic-stack pattern, storing the distance in days instead of the value.

int[] dailyTemperatures(int[] t) {
    int[] wait = new int[t.length];
    Deque<Integer> stack = new ArrayDeque<>();
    for (int i = 0; i < t.length; i++) {
        while (!stack.isEmpty() && t[stack.peek()] < t[i]) {
            int j = stack.pop();
            wait[j] = i - j;
        }
        stack.push(i);
    }
    return wait;
}

5. Implement a queue using two stacks.

Push onto an input stack; pop from an output stack, refilling it from the input stack only when it is empty. Each element moves at most twice, so operations are amortised O(1).

class MyQueue {
    private final Deque<Integer> in = new ArrayDeque<>(), out = new ArrayDeque<>();
    void push(int x) { in.push(x); }
    int pop() { peek(); return out.pop(); }
    int peek() {
        if (out.isEmpty()) while (!in.isEmpty()) out.push(in.pop());
        return out.peek();
    }
    boolean empty() { return in.isEmpty() && out.isEmpty(); }
}

6. Sliding window maximum in O(n).

Monotonic deque: keep indexes in decreasing order of value; drop indexes that leave the window from the front and smaller values from the back. The front is always the window's maximum.

int[] maxSlidingWindow(int[] nums, int k) {
    int[] res = new int[nums.length - k + 1];
    Deque<Integer> dq = new ArrayDeque<>();
    for (int i = 0; i < nums.length; i++) {
        if (!dq.isEmpty() && dq.peekFirst() <= i - k) dq.pollFirst();          // out of window
        while (!dq.isEmpty() && nums[dq.peekLast()] < nums[i]) dq.pollLast();   // smaller ones never matter
        dq.offerLast(i);
        if (i >= k - 1) res[i - k + 1] = nums[dq.peekFirst()];
    }
    return res;
}

7. Evaluate a Reverse Polish Notation expression.

Push numbers; on an operator, pop two operands (the second popped is the left operand), apply it and push the result.

int evalRPN(String[] tokens) {
    Deque<Integer> st = new ArrayDeque<>();
    for (String t : tokens) {
        switch (t) {
            case "+" -> st.push(st.pop() + st.pop());
            case "*" -> st.push(st.pop() * st.pop());
            case "-" -> { int b = st.pop(), a = st.pop(); st.push(a - b); }
            case "/" -> { int b = st.pop(), a = st.pop(); st.push(a / b); }
            default -> st.push(Integer.parseInt(t));
        }
    }
    return st.pop();
}

8. Where are stacks and queues used in real systems?

Stacks: function calls, undo/redo, expression parsing, browser back navigation, DFS. Queues: task scheduling, BFS, print and message queues, rate limiting, buffering between producers and consumers. Priority queues: job schedulers, Dijkstra, top-K problems.