Learn DSA Part 6: Stack and Queue - Monotonic Stack, Deque and Interview Problems

Stacks and queues are simple containers, but they power some of the most elegant interview solutions: matching brackets, evaluating expressions, "next greater element" problems, sliding window maximums and every breadth-first search. The real skill is recognising when a problem secretly needs one.

This is Part 6 of the Learn DSA series. We cover how stacks and queues work, which classes to use in C++ and Java, the monotonic stack and deque patterns, and the classic design questions. Code is in C++ and Java.

1. Stack: last in, first out

A stack works like a pile of plates: you add (push) and remove (pop) only at the top, so the last item in is the first out (LIFO). Push, pop and peek are all O(1).

Stacks appear whenever you need to remember something and come back to it in reverse order: the function call stack, undo history, browser back button, matching opening and closing brackets, and converting recursion into iteration (iterative DFS).

2. Queue and deque: first in, first out

A queue is a line at a ticket counter: add at the back (enqueue) and remove from the front (dequeue), so the first in is the first out (FIFO). Both operations are O(1). A deque (double-ended queue) allows O(1) insertion and removal at both ends.

Queues are the backbone of breadth-first search (Parts 9 and 11), task scheduling and buffering. Internally they are usually a circular array or a linked list.

3. Pattern 1: matching and parsing with a stack

When something must be "closed" in the reverse order it was "opened", use a stack. Push every opening bracket; on a closing bracket, the top of the stack must be its matching opener.

// Valid Parentheses: (), [], {}. O(n) time, O(n) space
bool isValid(const string& s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') { st.push(c); continue; }
        if (st.empty()) return false;
        char t = st.top(); st.pop();
        if ((c == ')' && t != '(') || (c == ']' && t != '[') ||
            (c == '}' && t != '{')) return false;
    }
    return st.empty();
}

// Valid Parentheses: (), [], {}. O(n) time, O(n) space
static boolean isValid(String s) {
    Deque<Character> st = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '[' || c == '{') { st.push(c); continue; }
        if (st.isEmpty()) return false;
        char t = st.pop();
        if ((c == ')' && t != '(') || (c == ']' && t != '[') ||
            (c == '}' && t != '{')) return false;
    }
    return st.isEmpty();
}

The same idea evaluates Reverse Polish Notation (push numbers, pop two on an operator), decodes strings like 3[a2[c]], simplifies Unix paths and handles asteroid collisions.

4. Pattern 2: monotonic stack for "next greater" problems

A monotonic stack keeps its elements in increasing or decreasing order. It answers questions like "for each element, what is the next greater element to its right?" in O(n) instead of O(n^2). Keep indices of elements still waiting for an answer; when a bigger value arrives, it is the answer for every smaller value it pops.

// Next greater element to the right (-1 if none). O(n)
vector<int> nextGreater(const vector<int>& a) {
    int n = a.size();
    vector<int> ans(n, -1);
    stack<int> st;                          // indices waiting for an answer
    for (int i = 0; i < n; i++) {
        while (!st.empty() && a[st.top()] < a[i]) {
            ans[st.top()] = a[i];
            st.pop();
        }
        st.push(i);
    }
    return ans;
}

// Next greater element to the right (-1 if none). O(n)
static int[] nextGreater(int[] a) {
    int n = a.length;
    int[] ans = new int[n];
    Arrays.fill(ans, -1);
    Deque<Integer> st = new ArrayDeque<>();  // indices waiting for an answer
    for (int i = 0; i < n; i++) {
        while (!st.isEmpty() && a[st.peek()] < a[i]) ans[st.pop()] = a[i];
        st.push(i);
    }
    return ans;
}

Each index is pushed once and popped at most once, so the whole loop is O(n). Variants solve Daily Temperatures, Online Stock Span, Next Smaller Element and the hard Largest Rectangle in Histogram (where each bar's width is found from its previous and next smaller bars).

5. Pattern 3: monotonic deque for sliding window maximum

To get the maximum of every window of size k, keep a deque of indices whose values are in decreasing order. Remove from the back any index whose value is smaller than the incoming one (it can never be a maximum again), and remove from the front any index that has left the window. The front is always the current window's maximum.

// Maximum of every window of size k. O(n)
vector<int> maxSlidingWindow(const vector<int>& a, int k) {
    deque<int> dq;                          // indices, values decreasing
    vector<int> res;
    for (int i = 0; i < (int)a.size(); i++) {
        while (!dq.empty() && dq.front() <= i - k) dq.pop_front(); // left window
        while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back(); // never max
        dq.push_back(i);
        if (i >= k - 1) res.push_back(a[dq.front()]);
    }
    return res;
}

// Maximum of every window of size k. O(n)
static int[] maxSlidingWindow(int[] a, int k) {
    Deque<Integer> dq = new ArrayDeque<>();  // indices, values decreasing
    int[] res = new int[a.length - k + 1];
    for (int i = 0; i < a.length; i++) {
        while (!dq.isEmpty() && dq.peekFirst() <= i - k) dq.pollFirst();
        while (!dq.isEmpty() && a[dq.peekLast()] <= a[i]) dq.pollLast();
        dq.offerLast(i);
        if (i >= k - 1) res[i - k + 1] = a[dq.peekFirst()];
    }
    return res;
}

This turns an O(n x k) brute force into O(n), and is a common follow-up to the sliding window techniques in Part 4.

6. Classic design questions

• Min Stack (getMin in O(1)): push pairs of (value, minimum so far), or keep a second stack of minimums.
• Queue using two stacks: push into an "in" stack; to dequeue, if the "out" stack is empty, move everything from "in" to "out", then pop from "out". Each element moves at most twice, so operations are amortized O(1).
• Stack using queues: after each push, rotate the queue so the newest element is at the front. Push becomes O(n) and pop O(1).
• Circular queue: a fixed array with head and tail indices that wrap around using modulo.

Practice problems

These are classic LeetCode-style problems, listed from easy to hard. For each one, decide first whether you need a plain stack, a monotonic stack or a deque.

1. Valid Parentheses (easy)
2. Implement Queue using Stacks (easy)
3. Next Greater Element I (easy)
4. Min Stack (medium)
5. Evaluate Reverse Polish Notation (medium)
6. Daily Temperatures (medium)
7. Online Stock Span (medium)
8. Decode String (medium)
9. Asteroid Collision (medium)
10. Design Circular Queue (medium)
11. Sliding Window Maximum (hard)
12. Largest Rectangle in Histogram (hard)
13. Basic Calculator (hard)