Stack

A stack is a LIFO (Last In, First Out) data structure. Think of it like a stack of plates - you can only add or remove from the top.

Operations

class Stack:
    def __init__(self):
        self.items = []
    
    def push(self, item):  # O(1)
        self.items.append(item)
    
    def pop(self):  # O(1)
        if not self.is_empty():
            return self.items.pop()
    
    def peek(self):  # O(1)
        if not self.is_empty():
            return self.items[-1]
    
    def is_empty(self):  # O(1)
        return len(self.items) == 0

Applications

1. Balanced Parentheses

def is_balanced(s):
    stack = []
    pairs = {'(': ')', '{': '}', '[': ']'}
    
    for char in s:
        if char in pairs:
            stack.append(char)
        elif char in pairs.values():
            if not stack or pairs[stack.pop()] != char:
                return False
    
    return len(stack) == 0

Quiz

Key Takeaways

✅ LIFO principle - last in, first out
✅ O(1) operations - push, pop, peek
✅ Applications - undo/redo, expression evaluation, backtracking

Essential for function calls, parsing, and history tracking! 🚀