Chapter 3: Stacks & Queues

1. Stack Fundamentals

Stack Operations

class Stack:
    """Stack implementation using list"""
    def __init__(self):
        # Step 1: Initialize empty list
        # List will store stack elements
        self.items = []
    
    def push(self, item):
        # Step 2: Add element to top of stack
        # Append adds to end of list (top of stack)
        self.items.append(item)
    
    def pop(self):
        # Step 3: Remove and return top element
        # Pop removes from end of list (LIFO)
        if self.is_empty():
            return None
        return self.items.pop()
    
    def peek(self):
        # Step 4: Return top element without removing
        if self.is_empty():
            return None
        return self.items[-1]
    
    def is_empty(self):
        # Step 5: Check if stack is empty
        return len(self.items) == 0

2. Valid Parentheses

Example: Check Balanced Parentheses

def is_valid(s):
    """
    Check if string has valid parentheses using stack.
    
    Args:
        s: String containing only '(', ')', '{', '}', '[', ']'
    
    Returns:
        True if parentheses are balanced, False otherwise
    """
    # Step 1: Initialize stack and mapping
    stack = []
    # Map closing brackets to their corresponding opening brackets
    mapping = {')': '(', '}': '{', ']': '['}
    
    # Step 2: Iterate through each character
    for char in s:
        # Step 3: Check if it's a closing bracket
        if char in mapping:
            # Step 3a: It's a closing bracket
            # Check if stack is empty or top doesn't match
            if not stack or stack.pop() != mapping[char]:
                return False
        else:
            # Step 3b: It's an opening bracket
            # Push it onto stack
            stack.append(char)
    
    # Step 4: Check if stack is empty
    # If empty, all brackets were matched
    return len(stack) == 0

Example:

Input: "()[]{}"

• '(': push → stack = ['(']
• ')': pop '(' → matches! → stack = []
• '[': push → stack = ['[']
• ']': pop '[' → matches! → stack = []
• '{': push → stack = ['{']
• '}': pop '{' → matches! → stack = []
• Stack empty → Valid!

3. Monotonic Stack

Algorithm Explanation

A monotonic stack maintains elements in monotonic (increasing or decreasing) order:

• Monotonic increasing: Elements increase from bottom to top
• Monotonic decreasing: Elements decrease from bottom to top
• Key insight: When we see an element that breaks monotonicity, we can process previous elements

Example: Next Greater Element

def next_greater_element(nums):
    """
    Find next greater element for each position using monotonic stack.
    
    Args:
        nums: List of integers
    
    Returns:
        List where result[i] is next greater element of nums[i], or -1 if none
    """
    # Step 1: Initialize result and stack
    n = len(nums)
    result = [-1] * n  # Default: no greater element
    stack = []  # Monotonic decreasing stack (stores indices)
    
    # Step 2: Iterate through array
    for i in range(n):
        # Step 3: While current element breaks monotonicity
        # Current element is greater than stack top
        while stack and nums[stack[-1]] < nums[i]:
            # Step 3a: Found next greater for stack top
            # Pop index from stack
            idx = stack.pop()
            # Step 3b: Set result for that index
            result[idx] = nums[i]
        
        # Step 4: Push current index
        # Current element might be next greater for future elements
        stack.append(i)
    
    return result

Example:

nums = [4, 5, 2, 10]

• i=0, num=4: stack=[0]
• i=1, num=5: 5 > 4 → result[0]=5, stack=[1]
• i=2, num=2: stack=[1, 2]
• i=3, num=10: 10 > 2 → result[2]=10, 10 > 5 → result[1]=10, stack=[3]
• Result: [5, 10, 10, -1]

4. Queue Fundamentals

Queue Operations

from collections import deque

class Queue:
    """Queue implementation using deque"""
    def __init__(self):
        # Step 1: Initialize deque (double-ended queue)
        # Deque provides O(1) operations on both ends
        self.items = deque()
    
    def enqueue(self, item):
        # Step 2: Add element to rear (end) of queue
        self.items.append(item)
    
    def dequeue(self):
        # Step 3: Remove and return front (beginning) element
        # popleft removes from left (FIFO)
        if self.is_empty():
            return None
        return self.items.popleft()
    
    def peek(self):
        # Step 4: Return front element without removing
        if self.is_empty():
            return None
        return self.items[0]
    
    def is_empty(self):
        # Step 5: Check if queue is empty
        return len(self.items) == 0

5. BFS (Breadth-First Search) with Queue

Example: Level-Order Traversal

from collections import deque

def level_order_traversal(root):
    """
    Traverse binary tree level by level using BFS.
    
    Args:
        root: Root node of binary tree
    
    Returns:
        List of lists, where each inner list is a level
    """
    # Step 1: Handle empty tree
    if root is None:
        return []
    
    # Step 2: Initialize queue and result
    queue = deque([root])  # Start with root node
    result = []
    
    # Step 3: Process each level
    while queue:
        # Step 3a: Get current level size
        # This tells us how many nodes are in current level
        level_size = len(queue)
        level_nodes = []
        
        # Step 3b: Process all nodes in current level
        for _ in range(level_size):
            # Step 3c: Dequeue node
            node = queue.popleft()
            # Step 3d: Add to current level
            level_nodes.append(node.val)
            
            # Step 3e: Enqueue children
            # Add left and right children for next level
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        # Step 3f: Add level to result
        result.append(level_nodes)
    
    # Step 4: Return all levels
    return result

6. Priority Queue (Heap)

Example: Find K Largest Elements

import heapq

def find_k_largest(nums, k):
    """
    Find k largest elements using min heap.
    
    Args:
        nums: List of integers
        k: Number of largest elements to find
    
    Returns:
        List of k largest elements
    """
    # Step 1: Initialize min heap
    # Min heap of size k (smallest at top)
    heap = []
    
    # Step 2: Process each number
    for num in nums:
        # Step 3: Add to heap
        heapq.heappush(heap, num)
        
        # Step 4: Maintain heap size k
        # If heap exceeds k, remove smallest
        if len(heap) > k:
            # Step 4a: Remove smallest element
            # This keeps only k largest elements
            heapq.heappop(heap)
    
    # Step 5: Return k largest elements
    # Heap now contains k largest (convert to list)
    return list(heap)

Time Complexity:

O(n log k) - n elements, each heap operation is O(log k)

Space Complexity:

O(k) - Heap stores at most k elements

📚 Chapter Summary

• Stack (LIFO): Use for parentheses matching, expression evaluation, backtracking
• Monotonic Stack: Use for next greater/smaller element problems
• Queue (FIFO): Use for BFS, task scheduling, level-order traversal
• Priority Queue/Heap: Use for k largest/smallest, merging sorted lists, Dijkstra's

Key Takeaway: Stacks and queues are fundamental for many algorithms. Choose based on processing order needed (LIFO vs FIFO) and whether you need priority-based processing.