Stacks and Queues

Stack (LIFO)

Last in, first out. Use a Python list: append to push, pop to pop (both O(1)).

balanced_brackets.py

def is_balanced(s: str) -> bool:
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in s:
        if ch in "([{":
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack

Queue (FIFO)

First in, first out. Use collections.deque, because list.pop(0) is O(n).

queue.py

from collections import deque

q = deque()
q.append("a")      # enqueue
q.append("b")
print(q.popleft()) # dequeue -> "a"

Monotonic stack

Keep the stack in sorted order to answer "next greater element" style questions in O(n).

next_greater.py

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