Stacks

Stacks — LIFO

# Last In First Out
# push, pop, peek — all O(1)

class Stack:
    def __init__(self): self._data = []
    def push(self, x):  self._data.append(x)
    def pop(self):      return self._data.pop()
    def peek(self):     return self._data[-1]
    def is_empty(self): return len(self._data) == 0
    def __len__(self):  return len(self._data)

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

# Monotonic stack -- next greater element
def next_greater(arr):
    n      = len(arr)
    result = [-1] * n
    stack  = []  # indices
    for i in range(n):
        while stack and arr[stack[-1]] < arr[i]:
            result[stack.pop()] = arr[i]
        stack.append(i)
    return result