Queue Interface: FIFO and Priority Processing

1. The Hook (The "Byte-Sized" Intro)

In a Nutshell: Queue processes elements in FIFO (First-In-First-Out) order. Deque (Double-Ended Queue) allows both ends access. PriorityQueue orders by priority (not FIFO). ArrayDeque is the modern, fast implementation for both Queue and Stack operations. Use queues for task scheduling, breadth-first search, and buffering.

Think of customer service line. First person in line → first served (FIFO). Priority queue = airport check-in (business class goes first, regardless of arrival order)!

2. Conceptual Clarity (The "Simple" Tier)

💡 The Analogy: The Ticket System

Queue (LinkedList): Regular line, FIFO
PriorityQueue: Hospital emergency room (critical patients first)
Deque (ArrayDeque): Double doors (enter/exit from both sides)

3. Technical Mastery (The "Deep Dive")

Queue Methods

Method	Throws Exception	Returns Special Value
Insert	`add(e)`	`offer(e)` → boolean
Remove	`remove()`	`poll()` → null if empty
Examine	`element()`	`peek()` → null if empty

Prefer: offer(), poll(), peek() (no exceptions)

Implementations

Type	Implementation	Use Case
FIFO Queue	LinkedList, ArrayDeque	Task queue, BFS
Priority Queue	PriorityQueue	Job scheduling, Dijkstra's algorithm
Deque	ArrayDeque	Stack, Deque operations

4. Interactive & Applied Code

java

import java.util.*;

public class QueueDemo {
    public static void main(String[] args) {
        // FIFO QUEUE (LinkedList)
        Queue<String> queue = new LinkedList<>();
        queue.offer("First");
        queue.offer("Second");
        queue.offer("Third");
        
        System.out.println("Peek: " + queue.peek()); // First (doesn't remove)
        System.out.println("Poll: " + queue.poll()); // First (removes)
        System.out.println("Queue: " + queue); // [Second, Third]
        
        // PRIORITY QUEUE (min-heap by default)
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.offer(5);
        pq.offer(1);
        pq.offer(3);
        
        while (!pq.isEmpty()) {
            System.out.print(pq.poll() + " "); // 1 3 5 (sorted!)
        }
        System.out.println();
        
        // PRIORITY QUEUE with custom comparator (max-heap)
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        maxHeap.offer(5);
        maxHeap.offer(1);
        maxHeap.offer(3);
        System.out.println("Max: " + maxHeap.poll()); // 5
        
        // DEQUE (ArrayDeque) - Both ends access
        Deque<String> deque = new ArrayDeque<>();
        deque.offerFirst("Front");
        deque.offerLast("Back");
        System.out.println("Deque: " + deque); // [Front, Back]
        System.out.println("Poll First: " + deque.pollFirst()); // Front
        System.out.println("Poll Last: " + deque.pollLast()); // Back
        
        // ArrayDeque as Stack (LIFO)
        Deque<String> stack = new ArrayDeque<>();
        stack.push("Bottom");
        stack.push("Top");
        System.out.println("Pop: " + stack.pop()); // Top (LIFO!)
    }
}

5. The Comparison & Decision Layer

Decision Tree: Choosing a Queue

graph TD A{Need priority ordering?} A -- Yes --> B[PriorityQueue] A -- No --> C{Need both ends access?} C -- Yes --> D[ArrayDeque] C -- No FIFO only --> E[LinkedList or ArrayDeque]

6. The "Interview Corner" (The Edge)

The "Killer" Interview Question: "What's the time complexity of PriorityQueue operations?" Answer: PriorityQueue uses a binary heap:

offer() (insert): O(log n) (bubble up)
poll() (remove min/max): O(log n) (bubble down)
peek() (get min/max): O(1) (root element)

Not a sorted list—only the root is guaranteed to be min/max!

Pro-Tip: Use ArrayDeque, not Stack: