STACK AND QUEUE
===============

--- STACK ---
LIFO — Last In First Out. Think of a stack of plates.
Operations: push (add), pop (remove top), peek (view top). All O(1).

Uses: undo/redo, function call stack, expression evaluation, DFS, balanced brackets.

# Stack using Python list
class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self.items.pop()

    def peek(self):
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self.items[-1]

    def is_empty(self):
        return len(self.items) == 0

    def size(self):
        return len(self.items)

s = Stack()
s.push(10)
s.push(20)
s.push(30)
print(s.peek())  # 30
print(s.pop())   # 30
print(s.size())  # 2

--- Balanced Brackets using Stack ---
Check if brackets (, ), {, }, [, ] are balanced.

def is_balanced(expr):
    stack = []
    pairs = {')': '(', '}': '{', ']': '['}
    for ch in expr:
        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

print(is_balanced("({[]})"))   # True
print(is_balanced("({[})"))    # False
print(is_balanced("((()))"))   # True

--- Next Greater Element using Stack ---
For each element, find the next element greater than it.
Time: O(n). Space: O(n).

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

print(next_greater([4, 5, 2, 25]))  # [5, 25, 25, -1]

--- Evaluate Postfix Expression ---
Postfix: operands come before operator (e.g. "2 3 +" = 5).

def evaluate_postfix(expression):
    stack = []
    for token in expression.split():
        if token.lstrip('-').isdigit():
            stack.append(int(token))
        else:
            b = stack.pop()
            a = stack.pop()
            if token == '+': stack.append(a + b)
            elif token == '-': stack.append(a - b)
            elif token == '*': stack.append(a * b)
            elif token == '/': stack.append(int(a / b))
    return stack[0]

print(evaluate_postfix("2 3 1 * + 9 -"))  # Output: -4

--- Min Stack ---
Stack that supports getMin() in O(1).

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, val):
        self.stack.append(val)
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)

    def pop(self):
        val = self.stack.pop()
        if val == self.min_stack[-1]:
            self.min_stack.pop()

    def get_min(self):
        return self.min_stack[-1]

ms = MinStack()
ms.push(5); ms.push(3); ms.push(7); ms.push(2)
print(ms.get_min())  # 2
ms.pop()
print(ms.get_min())  # 3

--- QUEUE ---
FIFO — First In First Out. Think of a line at a ticket counter.
Operations: enqueue (add rear), dequeue (remove front), peek. All O(1).

Uses: BFS, scheduling, print queues, sliding window.

from collections import deque

class Queue:
    def __init__(self):
        self.items = deque()

    def enqueue(self, item):
        self.items.append(item)

    def dequeue(self):
        if self.is_empty():
            raise IndexError("Queue is empty")
        return self.items.popleft()

    def peek(self):
        return self.items[0]

    def is_empty(self):
        return len(self.items) == 0

    def size(self):
        return len(self.items)

q = Queue()
q.enqueue(10)
q.enqueue(20)
q.enqueue(30)
print(q.dequeue())  # 10
print(q.peek())     # 20

--- Circular Queue ---
Fixed-size queue where rear wraps around to front.

class CircularQueue:
    def __init__(self, capacity):
        self.queue = [None] * capacity
        self.front = self.rear = -1
        self.capacity = capacity
        self.size = 0

    def enqueue(self, item):
        if self.size == self.capacity:
            raise OverflowError("Queue is full")
        self.rear = (self.rear + 1) % self.capacity
        self.queue[self.rear] = item
        if self.front == -1:
            self.front = 0
        self.size += 1

    def dequeue(self):
        if self.size == 0:
            raise IndexError("Queue is empty")
        item = self.queue[self.front]
        self.front = (self.front + 1) % self.capacity
        self.size -= 1
        return item

--- Deque (Double-Ended Queue) ---
Insert and delete from both ends in O(1).

from collections import deque
d = deque()
d.appendleft(1)   # add to front
d.append(2)       # add to rear
d.appendleft(0)
print(d)          # deque([0, 1, 2])
d.popleft()       # remove from front → 0
d.pop()           # remove from rear  → 2
print(d)          # deque([1])

--- Priority Queue ---
Elements are dequeued based on priority, not insertion order.
Python's heapq is a min-heap by default.

import heapq

pq = []
heapq.heappush(pq, (3, 'low'))
heapq.heappush(pq, (1, 'high'))
heapq.heappush(pq, (2, 'medium'))
print(heapq.heappop(pq))  # (1, 'high')
print(heapq.heappop(pq))  # (2, 'medium')

# Max-heap: negate priorities
heapq.heappush(pq, (-5, 'top priority'))
print(heapq.heappop(pq))  # (-5, 'top priority')

--- Difference: Stack vs Queue ---
Stack: LIFO — last added is first removed. Uses: DFS, backtracking, undo.
Queue: FIFO — first added is first removed. Uses: BFS, scheduling, buffering.