Stack & Queue Problems

Mastering Stack and Queue problems involves understanding how to manage "waiting" data effectively.

1. Valid Parentheses

Use a stack to ensure every opening bracket has a matching closing bracket in the correct order.

2. Implement Queue using Stacks

A classic architectural problem that tests your understanding of data flow.

3. Implement Stack using Queues

Simulating a stack (LIFO) using a queue (FIFO) requires rotating the elements so the last-in element is always at the front.

4. Monotonic Stack

A stack where elements are always in increasing or decreasing order. It's the standard way to solve "Next Greater Element" problems in $O(n)$ time.

def nextGreaterElement(nums):
    res = [-1] * len(nums)
    stack = [] # Stores indices
    
    for i in range(len(nums)):
        # While current element is greater than element at stack top
        while stack and nums[i] > nums[stack[-1]]:
            idx = stack.pop()
            res[idx] = nums[i]
        stack.append(i)
    return res

# [2, 1, 2, 4, 3] -> [4, 2, 4, -1, -1]

5. Sliding Window Maximum

Find the maximum element in every sliding window of size $k$.

Key Patterns

• Matching Pairs: Uses a Stack.
• Level Order Processing: Uses a Queue (for Trees/Graphs).
• History/Undo: Uses a Stack.
• Buffering/Scheduling: Uses a Queue.
• Reversing: Stacks naturally reverse order.