Stacks & Queues: 8 Practice Problems with Solutions

Stacks and queues are simple, but they unlock a surprising number of interview problems once you spot the patterns. Two patterns matter most: the monotonic stack (keep the stack sorted and pop while the new element violates the order — used for “next greater,” “previous smaller,” and histogram problems) and the monotonic deque (the queue equivalent, used for sliding-window extremes). The problems below walk through both, plus the classic implementations.

1. Valid Parentheses

Problem. Given a string containing only (), [], and {}, return True if every opener is matched by the correct closer in the correct order.

Examples. "()[]{}" → True. "([)]" → False. "{[]}" → True.

Approach. Push every opener. On every closer, pop and check it matches. At the end the stack must be empty.

def is_valid(s):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for c in s:
        if c in "([{":
            stack.append(c)
        elif c in pairs:
            if not stack or stack.pop() != pairs[c]:
                return False
    return not stack

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

O(n) time, O(n) space.

2. Min Stack

Problem. Design a stack that supports push, pop, top, and get_min — all in O(1).

Approach. Keep a parallel stack of minimums. Each entry is the minimum among everything currently in the stack at or below that level.

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

    def push(self, x):
        self.stack.append(x)
        if not self.mins or x <= self.mins[-1]:
            self.mins.append(x)
        else:
            self.mins.append(self.mins[-1])

    def pop(self):
        self.mins.pop()
        return self.stack.pop()

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

    def get_min(self):
        return self.mins[-1]

s = MinStack()
for x in [3, 5, 2, 1, 4]:
    s.push(x)
print(s.get_min())    # 1
s.pop(); s.pop()
print(s.get_min())    # 2

O(1) per operation. O(n) extra memory for the min stack — a fair price.

3. Daily Temperatures

Problem. Given an array temps, return an array answer where answer[i] is the number of days until a warmer day. If no warmer day exists, answer[i] = 0.

Example. [73, 74, 75, 71, 69, 72, 76, 73] → [1, 1, 4, 2, 1, 1, 0, 0].

Approach — monotonic decreasing stack. Walk left to right. Keep a stack of indices whose answer hasn’t been decided yet, in decreasing-temperature order. When today is warmer than the top of the stack, pop and write the answer.

i=0  push 0      stack (indices): [0]            temps at indices: [73]
i=1  74 > 73, pop 0 (answer[0]=1), push 1        stack: [1]               [74]
i=2  75 > 74, pop 1 (answer[1]=1), push 2        stack: [2]               [75]
i=3  71 < 75, push 3                              stack: [2,3]            [75,71]
i=4  69 < 71, push 4                              stack: [2,3,4]          [75,71,69]
i=5  72 > 69, pop 4 (ans[4]=1)
72 > 71, pop 3 (ans[3]=2), push 5            stack: [2,5]            [75,72]
i=6  76 > 72, pop 5 (ans[5]=1)
76 > 75, pop 2 (ans[2]=4), push 6            stack: [6]              [76]

def daily_temperatures(temps):
    answer = [0] * len(temps)
    stack = []   # indices, monotonic decreasing temperatures
    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:
            j = stack.pop()
            answer[j] = i - j
        stack.append(i)
    return answer

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

O(n) time — each index is pushed and popped at most once. O(n) space.

4. Largest Rectangle in Histogram

Problem. Given an array of bar heights, find the area of the largest rectangle that fits within the histogram.

Example. [2, 1, 5, 6, 2, 3] → 10 (the rectangle of width 2 across heights [5, 6]).

Approach — monotonic increasing stack of indices. For each bar, we want the nearest shorter bar on the left and right. A monotonic stack gives us both for free: when we pop a bar, the current index is the first shorter bar to its right, and the new top of the stack is the first shorter bar to its left.

def largest_rectangle(heights):
    stack = []      # indices, heights monotonically increasing
    best = 0
    heights = heights + [0]   # sentinel forces all bars to be popped
    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] > h:
            top = stack.pop()
            left = stack[-1] if stack else -1
            width = i - left - 1
            best = max(best, heights[top] * width)
        stack.append(i)
    return best

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

O(n) time, O(n) space. The sentinel 0 at the end forces every remaining bar to be popped and measured.

5. Implement Queue using Stacks

Problem. Implement a FIFO queue using only stack operations (push, pop, peek, empty).

Approach — two stacks, in and out. Push to in. When out is empty and we need to pop/peek, drain in into out — this reverses the order, so the front of the queue ends up on top of out. Amortised O(1) per operation: each item is moved at most twice.

class MyQueue:
    def __init__(self):
        self.in_stack = []
        self.out_stack = []

    def enqueue(self, x):
        self.in_stack.append(x)

    def _shift(self):
        if not self.out_stack:
            while self.in_stack:
                self.out_stack.append(self.in_stack.pop())

    def dequeue(self):
        self._shift()
        return self.out_stack.pop()

    def peek(self):
        self._shift()
        return self.out_stack[-1]

    def empty(self):
        return not self.in_stack and not self.out_stack

q = MyQueue()
for x in [1, 2, 3]:
    q.enqueue(x)
print(q.dequeue(), q.dequeue(), q.dequeue())    # 1 2 3

6. Implement Stack using Queues

Problem. Implement a LIFO stack using only queue operations.

Approach — single queue with rotation on push. Enqueue the new element, then rotate the queue so the new element is at the front. pop and top then read from the front. push is O(n); pop/top are O(1).

from collections import deque

class MyStack:
    def __init__(self):
        self.q = deque()

    def push(self, x):
        self.q.append(x)
        for _ in range(len(self.q) - 1):
            self.q.append(self.q.popleft())

    def pop(self):
        return self.q.popleft()

    def top(self):
        return self.q[0]

    def empty(self):
        return not self.q

s = MyStack()
for x in [1, 2, 3]:
    s.push(x)
print(s.pop(), s.pop(), s.pop())    # 3 2 1

7. Sliding Window Maximum

Problem. Given an array nums and a window size k, return the maximum in each window of size k.

Example. nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3 → [3, 3, 5, 5, 6, 7].

Approach — monotonic deque of indices. Maintain a deque whose indices have decreasing values. The front is always the max in the current window.

For each new index i:

1. Pop from the back while the new value is >= the back’s value (they can never be the answer again).
2. Append i at the back.
3. Pop from the front if its index is outside the window (i - k + 1 is the window start).
4. Once i >= k - 1, the front is the answer for this window.

nums: [1, 3, -1, -3, 5, 3, 6, 7],  k=3
i=0  push 0                          deque: [0]                      values:[1]
i=1  3 > 1, pop 0; push 1            deque: [1]                      values:[3]
i=2  -1 < 3, push 2                  deque: [1, 2]                   values:[3,-1]
window done → answer 3
i=3  -3 < -1, push 3                 deque: [1, 2, 3]                values:[3,-1,-3]
answer 3
i=4  5 > -3, pop 3; 5 > -1, pop 2;
5 > 3, pop 1; push 4            deque: [4]                      values:[5]
answer 5
i=5  3 < 5, push 5                   deque: [4, 5]                   values:[5,3]
answer 5
i=6  6 > 3, pop 5; 6 > 5, pop 4;
push 6                          deque: [6]                      values:[6]
answer 6
i=7  7 > 6, pop 6; push 7            deque: [7]                      values:[7]
answer 7

from collections import deque

def max_sliding_window(nums, k):
    dq = deque()    # indices, nums monotonically decreasing
    result = []
    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] <= x:
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

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

O(n) time — each index is added and removed at most once. O(k) space.

8. Next Greater Element

Problem. For each element of nums, find the next strictly greater element to its right. If none exists, return -1 for that position.

Example. [2, 1, 2, 4, 3] → [4, 2, 4, -1, -1].

Approach. Same monotonic stack as Daily Temperatures, but we store the value rather than the distance.

def next_greater(nums):
    result = [-1] * len(nums)
    stack = []   # indices, nums monotonically decreasing
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:
            result[stack.pop()] = x
        stack.append(i)
    return result

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

O(n) time, O(n) space. The “circular” variant (LeetCode 503, where the array wraps around) just walks the indices twice — same skeleton.

The two patterns to remember

Almost every problem above falls into one of two shapes:

Monotonic stack — for each element, find the nearest larger/smaller element on one side. Pattern: walk the array, pop while the new element violates the desired order, write the answer for each popped index, then push the new index. O(n) total because each index is pushed and popped at most once.

Monotonic deque — same idea, but you also need to evict items that have left the window. The front of the deque is always the answer for the current window.

When you see “next greater,” “previous smaller,” “trap water,” “histogram,” “stock span,” reach for the stack. When you see “max/min in a sliding window of size k,” reach for the deque.

More practice

Without solutions:

1. Trapping Rain Water — given an elevation map, compute how much water it can trap.
2. Asteroid Collision — simulate asteroids moving left/right; equal-mass collisions destroy both.
3. Decode String — "3[a2[c]]" → "accaccacc". Stack of (multiplier, partial string).
4. Basic Calculator — evaluate an expression with + - * / and parentheses.
5. Online Stock Span — for each day’s price, how many consecutive prior days had price ≤ today’s?
6. LRU Cache — using collections.OrderedDict or a doubly linked list plus a hashmap.
7. First Unique Character in a String — count and queue (we previewed this in the intro post).
8. Number of Recent Calls — a queue keeps only timestamps within the last 3000 ms.

If you can finish four or five of these comfortably, the pattern is yours.

Recap

You now know:

• Stack matches parentheses by pushing openers and checking on closers
• A parallel “mins” stack keeps get_min O(1)
• Monotonic decreasing stacks solve “next greater” and “daily temperatures”
• Monotonic increasing stacks solve “largest rectangle in histogram”
• A queue can be built from two stacks; a stack can be built from one queue
• A monotonic deque solves sliding-window max/min in O(n)
• The two patterns — monotonic stack, monotonic deque — cover most of the interview catalog

Next steps

You now have the major linear structures: arrays, linked lists, stacks, and queues. The natural next step is trees — hierarchical data, BFS/DFS in earnest, and a host of new operations. After that, the recursion fundamentals and dynamic programming posts will tie everything together.

Questions or feedback? Email codeloomdevv@gmail.com.