12 Stack and Queue Problems That Cover Every Interview Pattern

Stack and queue problems show up in roughly a third of coding interviews. Not because companies have a thing for LIFO and FIFO, but because the patterns underneath them (monotonic invariants, BFS traversal, amortized design) appear constantly, dressed up in different problem statements.

A lot of engineers show up to interviews knowing Valid Parentheses and basic BFS and not much else. That's enough to handle the easy variants. When the interviewer asks you to find the largest rectangle in a histogram or the maximum value across every sliding window, "I know what a stack is" stops being sufficient.

These 12 problems span every major stack and queue pattern: six of each. Solve all 12 and you have working templates for dozens more.

When you prepped for two weeks on the basics and the interviewer wants to talk about monotonic invariants.

What Did I See Last?

A stack gives you one thing: the most recently pushed element. That single constraint is why stacks appear in bracket matching, expression evaluation, nearest-neighbor queries, and recursive structure parsing. All of those problems ask "what did I see last?"

1. Valid Parentheses (LeetCode 20)

The pattern: bracket matching.

Push opening brackets. On a closing bracket, check whether the top matches. If it doesn't, invalid. If the stack is non-empty at the end, invalid.

This is the simplest stack problem in any interview pool. Its value is the template it teaches: push, check-and-pop, final-state check. That template scales directly to HTML tag validation, expression balancing, and nested structure checks.

def isValid(s: str) -> bool:
    stack = []
    pairs = {')': '(', ']': '[', '}': '{'}
    for c in s:
        if c in '([{':
            stack.append(c)
        elif not stack or stack[-1] != pairs[c]:
            return False
        else:
            stack.pop()
    return not stack

Difficulty: Easy. Time: O(n). Space: O(n).

2. Min Stack (LeetCode 155)

The pattern: synchronized auxiliary stack.

Design a stack supporting push, pop, top, and getMin: all in O(1). The insight is to maintain two stacks in lockstep. The main stack holds values. The min stack holds the running minimum at each depth. Pop both together.

This feels over-engineered until you try to solve it without the second stack.

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, val: int) -> None:
        self.stack.append(val)
        min_val = min(val, self.min_stack[-1] if self.min_stack else val)
        self.min_stack.append(min_val)

    def pop(self) -> None:
        self.stack.pop()
        self.min_stack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.min_stack[-1]

Difficulty: Medium. Time: O(1) all ops. Space: O(n).

3. Evaluate Reverse Polish Notation (LeetCode 150)

The pattern: computational stack.

Push operands. On an operator, pop two values, apply the operator, push the result. The bug most people introduce: Python floor division (//) truncates toward negative infinity, but the problem wants truncation toward zero. Use int(a / b) instead.

That trap catches approximately everyone the first time.

def evalRPN(tokens: list[str]) -> int:
    stack = []
    ops = {'+', '-', '*', '/'}
    for token in tokens:
        if token not in ops:
            stack.append(int(token))
        else:
            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))
    return stack[0]

Difficulty: Medium. Time: O(n). Space: O(n).

4. Decode String (LeetCode 394)

The pattern: recursive structure with a stack.

3[a2[c]] should return "accaccacc". The structure is nested, and a stack is the iterative substitute for recursive calls. Push the in-progress string and current count when you see [. Pop and expand when you see ].

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

Difficulty: Medium. Time: O(n * max_depth). Space: O(n).

5. Daily Temperatures (LeetCode 739)

The pattern: monotonic stack for next-greater-element.

For each day, how many days until a warmer temperature? Maintain a stack of indices in non-increasing order of temperature. When a new day is warmer than the top, pop and record the index difference. Every element is pushed once and popped once, so total work is O(n) regardless of the input shape.

def dailyTemperatures(temperatures: list[int]) -> list[int]:
    result = [0] * len(temperatures)
    stack = []  # indices
    for i, temp in enumerate(temperatures):
        while stack and temperatures[stack[-1]] < temp:
            j = stack.pop()
            result[j] = i - j
        stack.append(i)
    return result

Difficulty: Medium. Time: O(n). Space: O(n).

This is the canonical next-greater-element template. Learn it and you recognize Next Greater Element I and II, Stock Span, and Asteroid Collision immediately.

When you present this in an interview, the interviewer will look at your while loop nested inside a for loop and ask you to reconsider the time complexity. You are correct. The amortized argument: each element enters the stack once and leaves once, so the while loop does at most n total pops across the entire run, not n pops per outer iteration.

When the interviewer spots the while-inside-for and says "wait, isn't this O(n²)?"

6. Largest Rectangle in Histogram (LeetCode 84)

The pattern: boundary detection via monotonic stack.

For each bar, the largest rectangle that uses it as its shortest bar extends to the nearest shorter bar on each side. Use a monotonic increasing stack. When the current bar is shorter than the top, you've found the right boundary; the new stack top gives the left boundary.

def largestRectangleArea(heights: list[int]) -> int:
    stack = []  # indices, monotonically increasing by height
    max_area = 0
    heights = heights + [0]  # sentinel flushes 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)
    return max_area

Difficulty: Hard. Time: O(n). Space: O(n).

This is the hardest pure stack problem in most interview pools. The [0] sentinel at the end flushes every remaining bar off the stack on the final iteration, so you don't need a separate cleanup pass. Understand why the width formula works and you get Maximal Rectangle (LeetCode 85) for free.

What Did I See First?

Queues are for ordering by arrival. BFS, sliding windows, level-order traversal, and topological sort are all queue problems in disguise. The pattern: "reach the next layer" means a queue is doing the work.

7. Implement Queue using Stacks (LeetCode 232)

The pattern: amortized design.

Two stacks: inbox and outbox. Push to inbox. On a pop, if outbox is empty, pour all of inbox into outbox, reversing the order. Then pop from outbox. Each element moves from inbox to outbox at most once, giving O(1) amortized per operation.

This is the data structures equivalent of figuring out you can reverse a bag of marbles by pouring it into a second bag. Obvious in hindsight. Satisfying every time.

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

    def push(self, x: int) -> None:
        self.inbox.append(x)

    def pop(self) -> int:
        self.peek()
        return self.outbox.pop()

    def peek(self) -> int:
        if not self.outbox:
            while self.inbox:
                self.outbox.append(self.inbox.pop())
        return self.outbox[-1]

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

Difficulty: Easy. Time: O(1) amortized. Space: O(n).

8. Binary Tree Level Order Traversal (LeetCode 102)

The pattern: BFS with a size snapshot.

Use a queue and process exactly len(queue) nodes per level before moving to the next. That snapshot of the queue's current size is what separates levels. Every "process one layer at a time" problem, including right side view, zigzag traversal, and minimum depth, uses this exact structure.

from collections import deque

def levelOrder(root):
    if not root:
        return []
    result = []
    queue = deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)
    return result

Difficulty: Medium. Time: O(n). Space: O(n).

9. Rotting Oranges (LeetCode 994)

The pattern: multi-source BFS.

Add all rotten oranges to the queue before the loop begins. This single initialization is the entire trick. It guarantees each fresh orange is reached by its nearest rotten source simultaneously, not one source at a time. Shortest-distance problems from multiple starting points all use this initialization pattern.

from collections import deque

def orangesRotting(grid: list[list[int]]) -> int:
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c, 0))
            elif grid[r][c] == 1:
                fresh += 1
    if fresh == 0:
        return 0
    minutes = 0
    while queue:
        r, c, t = queue.popleft()
        for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                grid[nr][nc] = 2
                fresh -= 1
                minutes = t + 1
                queue.append((nr, nc, t + 1))
    return minutes if fresh == 0 else -1

Difficulty: Medium. Time: O(mn). Space: O(mn).

10. Course Schedule (LeetCode 207)

The pattern: topological sort / Kahn's algorithm.

Can you complete all courses given prerequisites? Kahn's BFS answer: start from every node with in-degree zero, process it, reduce its neighbors' in-degrees, and enqueue any that reach zero. If every node gets processed, no cycle exists.

from collections import deque

def canFinish(numCourses: int, prerequisites: list[list[int]]) -> bool:
    graph = [[] for _ in range(numCourses)]
    indegree = [0] * numCourses
    for a, b in prerequisites:
        graph[b].append(a)
        indegree[a] += 1
    queue = deque(i for i in range(numCourses) if indegree[i] == 0)
    processed = 0
    while queue:
        node = queue.popleft()
        processed += 1
        for neighbor in graph[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)
    return processed == numCourses

If processed == numCourses, no node was stuck behind a cycle. Nodes inside a cycle never reach in-degree zero because they all depend on each other. They wait forever and never get processed. The count check catches this without you ever explicitly identifying the cycle.

Difficulty: Medium. Time: O(V+E). Space: O(V+E).

11. Task Scheduler (LeetCode 621)

The pattern: heap plus cooldown queue.

Always schedule the most frequent remaining task. Use a max-heap of frequencies and a queue for cooldown tracking. The queue holds tasks not yet eligible, keyed by the time they become available again.

import heapq
from collections import Counter, deque

def leastInterval(tasks: list[str], n: int) -> int:
    counts = Counter(tasks)
    heap = [-c for c in counts.values()]
    heapq.heapify(heap)
    queue = deque()  # (neg_count, available_time)
    time = 0
    while heap or queue:
        time += 1
        if heap:
            count = heapq.heappop(heap) + 1
            if count < 0:
                queue.append((count, time + n))
        if queue and queue[0][1] == time:
            heapq.heappush(heap, queue.popleft()[0])
    return time

Difficulty: Medium. Time: O(n log k) where k is distinct task count. Space: O(k).

12. Sliding Window Maximum (LeetCode 239)

The pattern: monotonic deque.

Return the maximum in each k-sized window as it slides. Brute force is O(nk). The deque makes it O(n).

Maintain a deque of indices in decreasing order of value. The front is always the current maximum. Before appending, evict from the back any index with a smaller value. An element at the back that's smaller than the incoming element is dead. It can never be the maximum of any future window while the new element is present, so drop it immediately. Evict from the front any index that has slid out of range.

from collections import deque

def maxSlidingWindow(nums: list[int], k: int) -> list[int]:
    result = []
    dq = deque()  # indices, decreasing by value
    for i, num in enumerate(nums):
        while dq and nums[dq[-1]] < num:
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

Every element enters and leaves the deque at most once, so total work is O(n) regardless of k. This is the hardest pure queue problem in most interview pools, and the amortized argument is exactly the same as Daily Temperatures.

Difficulty: Hard. Time: O(n). Space: O(k).

Twelve Stack and Queue Interview Problems, Every Pattern

Problem	Pattern	Difficulty
Valid Parentheses	Bracket matching	Easy
Implement Queue using Stacks	Amortized design	Easy
Min Stack	Auxiliary tracking	Medium
Evaluate RPN	Computational stack	Medium
Decode String	Nested structure parsing	Medium
Daily Temperatures	Monotonic stack, next-greater	Medium
Binary Tree Level Order	BFS with layer snapshot	Medium
Rotting Oranges	Multi-source BFS	Medium
Course Schedule	Topological BFS, Kahn's	Medium
Task Scheduler	Heap plus cooldown queue	Medium
Largest Rectangle in Histogram	Monotonic stack, boundaries	Hard
Sliding Window Maximum	Monotonic deque	Hard

Two easy, eight medium, two hard. That's close to what real interview pools look like, where medium problems make up roughly 60% of coding rounds.

The Patterns, Distilled

• Stack = "what did I see most recently?" Queue = "what did I see first?" That distinction drives every pattern here.
• Monotonic stacks solve any "nearest larger/smaller element" problem in O(n). Recognize the question shape before reaching for an O(n log n) approach.
• BFS uses a queue. Level-order BFS uses a snapshot of len(queue) at the start of each level to avoid mixing layers.
• Multi-source BFS loads all starting nodes before the loop. That single change converts single-source distance to multi-source distance.
• The monotonic deque is the sliding-window-maximum pattern specifically. Recognize it from the phrase "maximum in each window of size k."
• The amortized argument for Daily Temperatures and Sliding Window Maximum is the same: each element enters and exits the structure once. Total work is O(n).

If you want to practice these under real interview conditions (timed, with a voice-based interviewer asking follow-ups and probing your complexity reasoning), SpaceComplexity runs rubric-scored mock interviews that mirror what interviewers actually write in their feedback.

The stack and queue patterns don't require memorizing 50 problems. They require understanding why each structure enforces a specific ordering constraint, then recognizing when a problem matches. Solve these 12 with that framing and most variations become recognizable before you touch the keyboard. See the stack pattern breakdown, queue problem guide, and monotonic stack deep dive for deeper coverage.

Further Reading

• LeetCode Stack Tag: complete list of stack-tagged problems sorted by frequency
• LeetCode Queue/Stack Explore Card: official structured learning path for both structures
• GeeksforGeeks: Top Stack Interview Problems: annotated problem set with pattern labels
• Wikipedia: Monotone Stack: formal treatment of the monotonic stack invariant
• Wikipedia: Topological Sorting: Kahn's algorithm and DFS-based approaches compared