Stacks & Queues

Concept

Stack = Last In First Out (push/pop at the top). Used for undo, matching brackets and recursion simulation.

Queue = First In First Out. Used in BFS and scheduling. In Python use collections.deque for O(1) on both ends.

Monotonic stack keeps elements in increasing or decreasing order to answer “next greater element” in O(n).

Complexity

Code (Python)

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

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

Remember

• Matching / nesting → stack.
• Level-by-level processing → queue.
• “Next greater / smaller” → monotonic stack.