Stacks — LIFO and Real-World Uses

class Stack:
    def __init__(self):
        self.data = []
 
    def push(self, val):
        self.data.append(val)      # O(1)
 
    def pop(self):
        return self.data.pop()     # O(1)
 
    def peek(self):
        return self.data[-1]       # O(1) — look without removing
 
    def is_empty(self):
        return len(self.data) == 0
 
    def size(self):
        return len(self.data)

def is_valid(s):
    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 len(stack) == 0
 
is_valid("()[]{}")  # True
is_valid("([)]")    # False

def eval_rpn(tokens):
    stack = []
    ops = {
        '+': lambda a, b: a + b,
        '-': lambda a, b: a - b,
        '*': lambda a, b: a * b,
        '/': lambda a, b: int(a / b),
    }
    for token in tokens:
        if token in ops:
            b, a = stack.pop(), stack.pop()
            stack.append(ops[token](a, b))
        else:
            stack.append(int(token))
    return stack[0]
 
eval_rpn(["2","1"

def next_greater(arr):
    result = [-1] * len(arr)
    stack = []  # stores indices
 
    for i, val in enumerate(arr):
        while stack and arr[stack[-1]] < val:
            idx = stack.pop()
            result[idx] = val   # val is the next greater for idx
        stack.append(i)
 
    return result
 
next_greater([2, 1, 2, 4, 3])  # [4, 2, 4, -1, -1]

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []  # tracks minimums
 
    def push(self, val):
        self.stack.append(val)
        min_val = min(val, self.min_stack[-1] if self.min_stack else val)
        self.min_stack.append(min_val)
 
    def pop(self):
        self.stack.pop()
        self.min_stack.pop()
 
    def get_min(self):
        return self.min_stack[-1]  # O(1)!