Home › Stacks and Queues - DSA Fundamentals

Stacks and Queues

The pattern: Use LIFO (stack) or FIFO (queue) ordering to process elements in a specific sequence. The monotonic stack variant is especially powerful — it finds the next greater/smaller element for every position in O(n).

Why this matters in interviews: Stacks solve parentheses matching, expression evaluation, monotonic problems (temperatures, histograms), and undo systems. They appear simple but enable elegant O(n) solutions to problems that look O(n²).

When to Recognize It

How It Works

Monotonic Stack: Imagine a stack of plates where you only allow increasing heights. When a new plate arrives that’s shorter than the top, you keep popping taller plates until you find one shorter (or the stack is empty). Each popped plate now knows: “this new plate is my next smaller element.”

flowchart LR
    A["Input: 2 1 4 3"]:::client
    B["Stack maintains decreasing order"]:::service
    C["Pop when new element is larger"]:::data
    D["Popped elements found their next greater"]:::data

    A --> B
    B --> C
    C --> D

    classDef client fill:#4c3a5e,stroke:#818cf8,color:#e2e8f0
    classDef service fill:#1a3a2a,stroke:#4ade80,color:#e2e8f0
    classDef data fill:#3b3520,stroke:#fbbf24,color:#e2e8f0

Key insight: Each element is pushed once and popped once → O(n) total, even though it looks like a nested loop.

Template Code

Code

# Monotonic stack: next greater element for each position
def next_greater(nums):
    n = len(nums)
    result = [-1] * n
    stack = []  # stores indices

    for i in range(n):
        # Pop elements smaller than current
        while stack and nums[stack[-1]] < nums[i]:
            idx = stack.pop()
            result[idx] = nums[i]
        stack.append(i)

    return result

# Valid parentheses
def is_valid(s):
    stack = []
    pairs = {')': '(', '}': '{', ']': '['}

    for char in s:
        if char in pairs:
            if not stack or stack[-1] != pairs[char]:
                return False
            stack.pop()
        else:
            stack.append(char)

    return len(stack) == 0
// Monotonic stack: next greater element
int[] nextGreater(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]) {
            result[stack.pop()] = nums[i];
        }
        stack.push(i);
    }
    return result;
}

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

    for (char c : s.toCharArray()) {
        if (pairs.containsKey(c)) {
            if (stack.isEmpty() || stack.peek() != pairs.get(c)) return false;
            stack.pop();
        } else {
            stack.push(c);
        }
    }
    return stack.isEmpty();
}
// Monotonic stack: next greater element
vector<int> nextGreater(vector<int>& nums) {
    int n = nums.size();
    vector<int> result(n, -1);
    stack<int> stk;

    for (int i = 0; i < n; i++) {
        while (!stk.empty() && nums[stk.top()] < nums[i]) {
            result[stk.top()] = nums[i];
            stk.pop();
        }
        stk.push(i);
    }
    return result;
}

// Valid parentheses
bool isValid(string s) {
    stack<char> stk;
    unordered_map<char, char> pairs = {{')', '('}, {'}', '{'}, {']', '['}};

    for (char c : s) {
        if (pairs.count(c)) {
            if (stk.empty() || stk.top() != pairs[c]) return false;
            stk.pop();
        } else {
            stk.push(c);
        }
    }
    return stk.empty();
}
// Monotonic stack: next greater element
function nextGreater(nums) {
    const n = nums.length;
    const result = new Array(n).fill(-1);
    const stack = [];

    for (let i = 0; i < n; i++) {
        while (stack.length && nums[stack[stack.length - 1]] < nums[i]) {
            result[stack.pop()] = nums[i];
        }
        stack.push(i);
    }
    return result;
}

// Valid parentheses
function isValid(s) {
    const stack = [];
    const pairs = { ')': '(', '}': '{', ']': '[' };

    for (const char of s) {
        if (pairs[char]) {
            if (!stack.length || stack[stack.length - 1] !== pairs[char]) return false;
            stack.pop();
        } else {
            stack.push(char);
        }
    }
    return stack.length === 0;
}

Variations

Largest Rectangle in Histogram

For each bar, find how far it can extend left and right without hitting a shorter bar. Use a monotonic increasing stack — when a shorter bar arrives, pop and calculate area for each popped bar.

Code

def largest_rectangle(heights):
    stack = []  # stores indices of increasing heights
    max_area = 0
    heights.append(0)  # sentinel to flush remaining bars

    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] > h:
            height = heights[stack.pop()]
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)

    heights.pop()  # remove sentinel
    return max_area

Queue Using Two Stacks

Push to one stack (inbox). When you need to pop/peek from the queue, if the other stack (outbox) is empty, pour everything from inbox to outbox (reverses order → FIFO).

Monotonic Decreasing Stack

For “next smaller element” or “stock span,” maintain a decreasing stack instead. Pop when the new element is smaller than the top.

Complexity

Operation Time
Valid parentheses O(n)
Next greater element O(n)
Largest rectangle O(n)
Queue using stacks (amortized) O(1) per operation

Why monotonic stack is O(n): Every element is pushed once and popped at most once. Even though there’s a while loop inside the for loop, the total pops across all iterations is bounded by n.

Common Mistakes

Practice Problems

Key Takeaways