Stack and Queue Patterns: Monotonic Stack, Min Stack, and Queue Tricks

Stacks and queues are simple data structures, but the patterns built on them solve a surprising range of LeetCode problems. Monotonic stacks turn O(n^2) brute force into O(n). Min stacks add constant-time minimum retrieval. Queue-with-stacks appears in system design interviews. This guide covers every major pattern.

Pattern 1: Monotonic Stack

A monotonic stack maintains elements in strictly increasing or decreasing order. When a new element breaks the order, you pop elements until the invariant is restored. This is the key technique for “next greater element” and “next smaller element” problems.

Process 2: stack=[2]
Process 1: stack=[2, 1]         (1 < 2, push)
Process 5: pop 1 (next greater of 1 is 5)
         pop 2 (next greater of 2 is 5)
         stack=[5]
Process 6: pop 5 (next greater of 5 is 6)
         stack=[6]
Process 2: stack=[6, 2]         (2 < 6, push)
Process 3: pop 2 (next greater of 2 is 3)
         stack=[6, 3]

Next Greater Element (LC 496)

def nextGreaterElement(nums1: list[int], nums2: list[int]) -> list[int]:
    # Build a map: for each element in nums2, what is the next greater?
    next_greater = {}
    stack = []
    
    for num in nums2:
        while stack and stack[-1] < num:
            next_greater[stack.pop()] = num
        stack.append(num)
    
    return [next_greater.get(num, -1) for num in nums1]

print(nextGreaterElement([4, 1, 2], [1, 3, 4, 2]))
# [-1, 3, -1]

Daily Temperatures (LC 739)

For each day, find how many days until a warmer temperature.

def dailyTemperatures(temperatures: list[int]) -> list[int]:
    n = len(temperatures)
    result = [0] * n
    stack = []  # stack of indices
    
    for i in range(n):
        while stack and temperatures[i] > temperatures[stack[-1]]:
            prev_idx = stack.pop()
            result[prev_idx] = i - prev_idx
        stack.append(i)
    
    return result

print(dailyTemperatures([73, 74, 75, 71, 69, 72, 76, 73]))
# [1, 1, 4, 2, 1, 1, 0, 0]

// Java version
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[i] > temperatures[stack.peek()]) {
            int prevIdx = stack.pop();
            result[prevIdx] = i - prevIdx;
        }
        stack.push(i);
    }
    return result;
}

Largest Rectangle in Histogram (LC 84)

One of the hardest stack problems. Find the largest rectangle that fits under the histogram bars.

def largestRectangleArea(heights: list[int]) -> int:
    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

print(largestRectangleArea([2, 1, 5, 6, 2, 3]))  # 10

Trapping Rain Water (LC 42)

def trap(height: list[int]) -> int:
    stack = []
    water = 0
    
    for i, h in enumerate(height):
        while stack and h > height[stack[-1]]:
            bottom = height[stack.pop()]
            if not stack:
                break
            width = i - stack[-1] - 1
            bounded_height = min(h, height[stack[-1]]) - bottom
            water += width * bounded_height
        stack.append(i)
    
    return water

# Two pointer approach (more intuitive)
def trap_two_pointer(height: list[int]) -> int:
    left, right = 0, len(height) - 1
    left_max, right_max = 0, 0
    water = 0
    
    while left < right:
        if height[left] < height[right]:
            left_max = max(left_max, height[left])
            water += left_max - height[left]
            left += 1
        else:
            right_max = max(right_max, height[right])
            water += right_max - height[right]
            right -= 1
    
    return water

print(trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))  # 6

Pattern 2: Min Stack (LC 155)

Design a stack that supports push, pop, top, and retrieving the minimum element in O(1).

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []  # parallel stack tracking minimums
    
    def push(self, val: int) -> None:
        self.stack.append(val)
        # Push to min_stack if empty or val <= current min
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)
    
    def pop(self) -> None:
        val = self.stack.pop()
        if val == self.min_stack[-1]:
            self.min_stack.pop()
    
    def top(self) -> int:
        return self.stack[-1]
    
    def getMin(self) -> int:
        return self.min_stack[-1]

# Usage
ms = MinStack()
ms.push(-2)
ms.push(0)
ms.push(-3)
print(ms.getMin())  # -3
ms.pop()
print(ms.top())     # 0
print(ms.getMin())  # -2

// Java version
class MinStack {
    private Deque<Integer> stack = new ArrayDeque<>();
    private Deque<Integer> minStack = new ArrayDeque<>();
    
    public void push(int val) {
        stack.push(val);
        if (minStack.isEmpty() || val <= minStack.peek())
            minStack.push(val);
    }
    
    public void pop() {
        int val = stack.pop();
        if (val == minStack.peek()) minStack.pop();
    }
    
    public int top() { return stack.peek(); }
    public int getMin() { return minStack.peek(); }
}

Pattern 3: Queue Using Two Stacks (LC 232)

class MyQueue:
    def __init__(self):
        self.in_stack = []   # for push
        self.out_stack = []  # for pop/peek
    
    def push(self, x: int) -> None:
        self.in_stack.append(x)
    
    def pop(self) -> int:
        self.peek()  # ensure out_stack has elements
        return self.out_stack.pop()
    
    def peek(self) -> int:
        if not self.out_stack:
            # Transfer all from in_stack to out_stack (reverses order)
            while self.in_stack:
                self.out_stack.append(self.in_stack.pop())
        return self.out_stack[-1]
    
    def empty(self) -> bool:
        return not self.in_stack and not self.out_stack

q = MyQueue()
q.push(1)
q.push(2)
print(q.peek())   # 1
print(q.pop())    # 1
print(q.empty())  # False

Amortized O(1) per operation: each element is moved from in_stack to out_stack exactly once.

Pattern 4: Parentheses and Expression Problems

Valid Parentheses (LC 20)

def isValid(s: str) -> bool:
    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

print(isValid("()[]{}"))   # True
print(isValid("([)]"))     # False
print(isValid("{[]}"))     # True

Evaluate Reverse Polish Notation (LC 150)

def evalRPN(tokens: list[str]) -> int:
    stack = []
    
    for token in tokens:
        if token in {'+', '-', '*', '/'}:
            b, a = stack.pop(), stack.pop()
            if token == '+': stack.append(a + b)
            elif token == '-': stack.append(a - b)
            elif token == '*': stack.append(a * b)
            else: stack.append(int(a / b))  # truncate toward zero
        else:
            stack.append(int(token))
    
    return stack[0]

print(evalRPN(["2","1","+","3","*"]))  # 9: ((2+1)*3)
print(evalRPN(["4","13","5","/","+"]))  # 6: (4+(13/5))

Decode String (LC 394)

def decodeString(s: str) -> str:
    stack = []
    current_str = ""
    current_num = 0
    
    for char in s:
        if char.isdigit():
            current_num = current_num * 10 + int(char)
        elif char == '[':
            stack.append((current_str, current_num))
            current_str = ""
            current_num = 0
        elif char == ']':
            prev_str, num = stack.pop()
            current_str = prev_str + current_str * num
        else:
            current_str += char
    
    return current_str

print(decodeString("3[a]2[bc]"))      # "aaabcbc"
print(decodeString("3[a2[c]]"))       # "accaccacc"
print(decodeString("2[abc]3[cd]ef"))  # "abcabccdcdcdef"

Pattern 5: Monotonic Queue (Sliding Window Maximum)

Sliding Window Maximum (LC 239)

from collections import deque

def maxSlidingWindow(nums: list[int], k: int) -> list[int]:
    dq = deque()  # stores indices, front = max
    result = []
    
    for i in range(len(nums)):
        # Remove elements outside the window
        while dq and dq[0] < i - k + 1:
            dq.popleft()
        
        # Remove smaller elements (they can never be the max)
        while dq and nums[dq[-1]] < nums[i]:
            dq.pop()
        
        dq.append(i)
        
        # Window is full, record the max
        if i >= k - 1:
            result.append(nums[dq[0]])
    
    return result

print(maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3))
# [3, 3, 5, 5, 6, 7]

Quick Reference

Key Takeaways

Monotonic stacks solve “next greater/smaller element” problems in O(n) by maintaining a sorted invariant and popping elements when it breaks. Min stack uses a parallel stack to track the running minimum. Queue from two stacks achieves amortized O(1) by lazily transferring elements. For expression and parenthesis problems, use a stack to track the nesting context. The sliding window maximum uses a monotonic deque to maintain the window’s max efficiently. In all these patterns, the stack or queue serves as a structured memory of past elements that lets you avoid re-scanning.