Queues & Priority Queues

// Step by step (FIFO order):
// offer(5) -> Queue: [5]
// offer(3) -> Queue: [5, 3]
// poll()   -> Returns 5, Queue: [3]
// offer(7) -> Queue: [3, 7]
// offer(2) -> Queue: [3, 7, 2]
// poll()   -> Returns 3, Queue: [7, 2]
// peek()   -> Returns 7, Queue: [7, 2]

// Answer: peek() returns 7
// Remaining queue (front to back): [7, 2]

// Both remove and return the front element
// Difference is behavior on EMPTY queue:

Queue q = new LinkedList<>();

// poll() - returns null if empty (safe)
Integer val = q.poll();  // val = null

// remove() - throws NoSuchElementException if empty
Integer val = q.remove();  // THROWS EXCEPTION!

// Best practice:
// Use poll() in most cases (safer)
// Use remove() only when empty queue is a bug

// Safe pattern:
if (!queue.isEmpty()) {
    int front = queue.poll();
}

FIFO = First In, First Out

Real-world examples:
1. Line at a store - first person in line served first
2. Printer queue - first document prints first
3. Customer service - first caller answered first

Queue vs Stack:
- Queue (FIFO): Add at back, remove from front
- Stack (LIFO): Add at top, remove from top

Use Queue when:
- Order of arrival matters
- Fair processing (first come, first served)
- BFS traversal, level-order processing

ArrayDeque (Preferred):
+ Better cache locality (contiguous memory)
+ No node allocation overhead
+ Faster in practice for most operations
+ Resizable array (amortized O(1))
- Cannot store null values

LinkedList:
+ Can store null values
+ No resize needed (true O(1) always)
+ Good if you need List operations too
- Node allocation overhead
- Worse cache performance

Use ArrayDeque when:
- Performance matters (most cases)
- You don't need null values

Use LinkedList when:
- You need to store null
- You also need List operations (get by index)

class MyQueue {
    Deque stackIn = new ArrayDeque<>();
    Deque stackOut = new ArrayDeque<>();
    
    public void push(int x) {
        stackIn.push(x);
    }
    
    public int pop() {
        moveIfNeeded();
        return stackOut.pop();
    }
    
    public int peek() {
        moveIfNeeded();
        return stackOut.peek();
    }
    
    private void moveIfNeeded() {
        if (stackOut.isEmpty()) {
            while (!stackIn.isEmpty()) {
                stackOut.push(stackIn.pop());
            }
        }
    }
    
    public boolean empty() {
        return stackIn.isEmpty() && stackOut.isEmpty();
    }
}
// Amortized O(1) for all operations!

Problem with regular array queue:
- After dequeue, front moves forward
- Space at beginning becomes wasted
- Eventually "full" even with empty slots

Example (capacity 5):
[X, X, C, D, E] - Can't add F even though 2 slots free!

Modulo solution:
rear = (rear + 1) % capacity

When rear = 4 (last index):
  (4 + 1) % 5 = 0  <- Wraps to beginning!

This allows:
- Reuse of "wasted" front slots
- Continuous operation without shifting
- True O(1) operations

Array becomes logically circular:
Index: 0 -> 1 -> 2 -> 3 -> 4 -> 0 -> 1 -> ...

Deque deque = new ArrayDeque<>();

// === Use as STACK (LIFO) ===
deque.push(1);      // Add to front
deque.push(2);      // Add to front
deque.push(3);      // Deque: [3, 2, 1]
deque.pop();        // Returns 3 (from front)
deque.peek();       // Returns 2 (front)

// === Use as QUEUE (FIFO) ===
deque.clear();
deque.offer(1);     // Add to back
deque.offer(2);     // Add to back  
deque.offer(3);     // Deque: [1, 2, 3]
deque.poll();       // Returns 1 (from front)
deque.peek();       // Returns 2 (front)

// Key insight:
// Stack: push/pop at FRONT
// Queue: add at BACK, remove at FRONT

Sliding Window Maximum problem:

Given: [1, 3, -1, -3, 5, 3, 6, 7], k=3
Find maximum in each window of size k

Use Deque to store indices:
- Add new element: pollLast() smaller elements
  (they can never be max), then offerLast()
- Remove expired: pollFirst() if outside window
- Get max: peekFirst() always has window max

Why both ends needed:
- Back: Remove smaller elements, add new
- Front: Remove expired elements, get max

This achieves O(n) instead of O(n*k)!

// add/remove: Throw exception on failure
// offer/poll: Return special value on failure

Deque d = new ArrayDeque<>();

// On empty deque:
d.removeFirst();   // Throws NoSuchElementException!
d.pollFirst();     // Returns null (safe)

d.getFirst();      // Throws NoSuchElementException!
d.peekFirst();     // Returns null (safe)

// For bounded deques (rare):
d.addFirst(x);     // Throws if full
d.offerFirst(x);   // Returns false if full

// Best practice:
// Use offer/poll/peek for safe operations
// Use add/remove/get only when empty = bug

// Min-Heap (default)
PriorityQueue minHeap = new PriorityQueue<>();
// peek() returns SMALLEST

// Max-Heap - Method 1: Collections.reverseOrder()
PriorityQueue maxHeap1 = 
    new PriorityQueue<>(Collections.reverseOrder());

// Max-Heap - Method 2: Lambda comparator
PriorityQueue maxHeap2 = 
    new PriorityQueue<>((a, b) -> b - a);

// Max-Heap - Method 3: Comparator.reverseOrder()
PriorityQueue maxHeap3 = 
    new PriorityQueue<>(Comparator.reverseOrder());

// All three methods work the same way
// peek() returns LARGEST element

// Use MIN-HEAP of size K!

// Why? Keep track of K largest elements
// The root (minimum of K largest) = Kth largest

int findKthLargest(int[] nums, int k) {
    PriorityQueue minHeap = new PriorityQueue<>();
    
    for (int num : nums) {
        minHeap.offer(num);
        if (minHeap.size() > k) {
            minHeap.poll();  // Remove smallest
        }
    }
    return minHeap.peek();  // Kth largest!
}

// Example: [3,2,1,5,6,4], k=2
// After processing: heap = [5, 6]
// peek() = 5 (2nd largest)

// Why not max-heap?
// Max-heap would need to store all elements
// Then poll K-1 times - less efficient!

poll() is O(log n):
- Always removes the ROOT (index 0)
- No searching needed
- Just bubble-down to restore heap property

remove(element) is O(n):
- Must FIND the element first
- Heap is NOT sorted - only parent-child order
- Must scan entire heap to find element
- Then bubble-up/down to restore heap

Workaround for frequent removals:
1. Lazy deletion: Mark as deleted, skip during poll
2. Use TreeMap/TreeSet for O(log n) removal
3. Use indexed priority queue (advanced)

// Lazy deletion pattern:
Set deleted = new HashSet<>();
while (!heap.isEmpty()) {
    int top = heap.peek();
    if (deleted.contains(top)) {
        heap.poll();  // Skip deleted
        continue;
    }
    // Process valid top
}

BFS needs FIFO (Queue):
- Process nodes in order they were discovered
- All nodes at distance d processed before d+1
- Guarantees shortest path in unweighted graphs

DFS uses LIFO (Stack):
- Process most recently discovered node first
- Goes deep before exploring siblings
- Used for backtracking, cycle detection

If you use Stack for "BFS":
- You get DFS instead!
- Nodes processed depth-first, not breadth-first
- Shortest path no longer guaranteed

Example traversal (same graph):
BFS with Queue: A -> B -> C -> D -> E (level by level)
DFS with Stack: A -> B -> D -> E -> C (deep first)

// WRONG - queue.size() changes during loop!
while (!queue.isEmpty()) {
    for (int i = 0; i < queue.size(); i++) {  // BUG!
        // queue.size() changes as we add children
    }
}

// CORRECT - capture size before processing level
while (!queue.isEmpty()) {
    int levelSize = queue.size();  // Snapshot!
    for (int i = 0; i < levelSize; i++) {
        TreeNode node = queue.poll();
        // Add children (queue grows)
        if (node.left != null) queue.offer(node.left);
        if (node.right != null) queue.offer(node.right);
    }
    // Now all nodes at current level processed
    // Queue contains only next level nodes
}

// This ensures we process EXACTLY one level per iteration
// Critical for: level grouping, distance tracking

// Multi-source BFS: Start from MULTIPLE nodes at once

// Example: Rotting Oranges
// All rotten oranges spread simultaneously
// Add ALL rotten oranges to queue initially!

int orangesRotting(int[][] grid) {
    Queue queue = new LinkedList<>();
    int fresh = 0;
    
    // Add ALL rotten oranges (multiple sources)
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[0].length; j++) {
            if (grid[i][j] == 2) {
                queue.offer(new int[]{i, j});
            } else if (grid[i][j] == 1) {
                fresh++;
            }
        }
    }
    
    // BFS from all sources simultaneously
    // Each level = 1 minute of rotting
}

// Other multi-source examples:
// - 01 Matrix: Distance from any 0
// - Walls and Gates: Distance from any gate

Naive approach: O(n * k)
- For each window, scan all k elements to find max
- n windows * k elements = O(n * k)

Monotonic Deque: O(n)
- Each element is added to deque at most ONCE
- Each element is removed from deque at most ONCE
- Total operations: 2n = O(n)

Key insight: Amortized analysis
- We don't scan k elements per window
- We maintain a "running max" structure
- pollFirst(): Remove expired (outside window)
- pollLast(): Remove smaller elements (never max)
- peekFirst(): Always has current window max

Why remove smaller elements?
- If nums[i] > nums[j] and i > j
- nums[j] can NEVER be max while nums[i] exists
- Safe to remove nums[j] permanently

// Min-heap of size K: O(n log k)
// We want K MOST frequent

// Why min-heap works:
// - Keep only K elements in heap
// - When heap size > k, remove SMALLEST frequency
// - Result: K largest frequencies remain!

// Why not max-heap?
// - Would need to store ALL elements first
// - Then poll K times
// - Space: O(n), Time: O(n log n)

// Min-heap approach:
PriorityQueue heap = new PriorityQueue<>(
    (a, b) -> count.get(a) - count.get(b)  // Min by frequency
);

for (int num : count.keySet()) {
    heap.offer(num);
    if (heap.size() > k) {
        heap.poll();  // Remove least frequent
    }
}
// Heap now contains K most frequent!

// Time: O(n log k) - much better than O(n log n)
// Space: O(k) - much better than O(n)

ListNode mergeKLists(ListNode[] lists) {
    // Min-heap of list heads
    PriorityQueue pq = new PriorityQueue<>(
        (a, b) -> a.val - b.val
    );
    
    // Add all non-null heads
    for (ListNode head : lists) {
        if (head != null) pq.offer(head);
    }
    
    ListNode dummy = new ListNode(0);
    ListNode curr = dummy;
    
    while (!pq.isEmpty()) {
        ListNode smallest = pq.poll();
        curr.next = smallest;
        curr = curr.next;
        
        // Add next node from same list
        if (smallest.next != null) {
            pq.offer(smallest.next);
        }
    }
    
    return dummy.next;
}
// Time: O(n log k) where n = total nodes
// Space: O(k) for the heap