Queues and Deques

🚂 The Train Station: Java Queues & Deques

Imagine a busy train station. People line up to buy tickets. The person who arrives first gets served first. That’s exactly how Queues work in Java!

🎯 What You’ll Learn

• Queue Interface – The “first come, first served” line
• PriorityQueue – The VIP line where important people go first
• Deque Interface – A magical double-ended line
• ArrayDeque – The super-fast double-ended line

🎫 The Queue Interface: First In, First Out

The Story

Picture a line at an ice cream shop. The first person in line gets their ice cream first. The last person waits the longest. This is called FIFO – First In, First Out.

What is a Queue?

A Queue is like a waiting line. You can only:

• Add people at the back of the line
• Remove people from the front of the line

The Magic Words (Methods)

Your First Queue

Queue<String> iceCreamLine = new LinkedList<>();

// People join the line
iceCreamLine.offer("Alice");
iceCreamLine.offer("Bob");
iceCreamLine.offer("Charlie");

// Who's first? Let's peek!
System.out.println(iceCreamLine.peek());
// Output: Alice

// Serve the first person
String served = iceCreamLine.poll();
System.out.println(served + " got ice cream!");
// Output: Alice got ice cream!

// Who's next?
System.out.println(iceCreamLine.peek());
// Output: Bob

💡 Golden Rule

Use offer() and poll() instead of add() and remove()

Why? They’re safer! They won’t crash your program if something goes wrong.

graph TD
    A["🧑 Alice joins"] --> B["Line: Alice"]
    B --> C["🧑 Bob joins"]
    C --> D["Line: Alice, Bob"]
    D --> E["🧑 Charlie joins"]
    E --> F["Line: Alice, Bob, Charlie"]
    F --> G["Alice served!"]
    G --> H["Line: Bob, Charlie"]

👑 PriorityQueue: The VIP Line

The Story

Imagine a hospital emergency room. A person with a small cut waits. Then someone having a heart attack arrives. Who gets treated first? The heart attack patient – because their need is more urgent!

PriorityQueue is like this. It doesn’t follow “first come, first served.” Instead, the most important item comes out first!

How Does It Decide Importance?

By default, smaller numbers = higher priority.

Think of it like grades: 1st place is better than 10th place!

Your First PriorityQueue

PriorityQueue<Integer> emergencyRoom =
    new PriorityQueue<>();

// Patients arrive (lower = more urgent)
emergencyRoom.offer(5);  // Mild fever
emergencyRoom.offer(1);  // Heart attack!
emergencyRoom.offer(3);  // Broken arm

// Who gets treated first?
System.out.println(emergencyRoom.poll());
// Output: 1 (Heart attack patient)

System.out.println(emergencyRoom.poll());
// Output: 3 (Broken arm)

System.out.println(emergencyRoom.poll());
// Output: 5 (Mild fever)

Reverse Priority (Biggest First)

Sometimes you want the biggest number first – like serving the oldest person:

PriorityQueue<Integer> oldest =
    new PriorityQueue<>(Collections.reverseOrder());

oldest.offer(25);
oldest.offer(65);
oldest.offer(40);

System.out.println(oldest.poll());
// Output: 65 (oldest person first!)

Custom Priority with Strings

// Shortest name = highest priority
PriorityQueue<String> byLength =
    new PriorityQueue<>(
        (a, b) -> a.length() - b.length()
    );

byLength.offer("Alexander");
byLength.offer("Bob");
byLength.offer("Kate");

System.out.println(byLength.poll());
// Output: Bob (shortest name!)

🚫 Important Warnings

1. No null values allowed! PriorityQueue will crash.
2. No guaranteed order when iterating! Only poll() gives correct order.
3. Not thread-safe! Don’t share between threads.

graph TD
    A["5, 1, 3 added"] --> B["Internal heap organizes"]
    B --> C["poll returns 1"]
    C --> D["poll returns 3"]
    D --> E["poll returns 5"]
    style C fill:#90EE90
    style D fill:#90EE90
    style E fill:#90EE90

🚪 Deque Interface: The Double-Door Room

The Story

Imagine a room with two doors – one at each end. People can enter or leave from either door! This magical room is called a Deque (pronounced “deck”).

Deque = Double Ended Queue

The Superpowers

A Deque can work as:

• A Queue (line at a store)
• A Stack (pile of plates)
• Or both at once!

The Method Family

Using Deque as a Queue (FIFO)

Deque<String> queue = new ArrayDeque<>();

queue.offerLast("First");   // Add at back
queue.offerLast("Second");
queue.offerLast("Third");

System.out.println(queue.pollFirst());
// Output: First

Using Deque as a Stack (LIFO)

Think of a stack of pancakes. You add on top, you eat from top!

Deque<String> stack = new ArrayDeque<>();

stack.push("Bottom pancake");
stack.push("Middle pancake");
stack.push("Top pancake");

System.out.println(stack.pop());
// Output: Top pancake

System.out.println(stack.pop());
// Output: Middle pancake

💡 Pro Tip

push() = addFirst() (adds to front) pop() = removeFirst() (removes from front)

graph LR
    A["🚪 Front Door"] --> B["Room/Deque"]
    B --> C["🚪 Back Door"]
    D["addFirst"] --> A
    A --> E["removeFirst"]
    F["addLast"] --> C
    C --> G["removeLast"]

⚡ ArrayDeque: The Speed Champion

The Story

ArrayDeque is like a super-fast version of Deque. It uses an array that grows automatically. Think of it as a stretchy container that expands when needed!

Why ArrayDeque?

Use ArrayDeque unless you need null values!

Creating an ArrayDeque

// Empty deque (starts with 16 slots)
Deque<String> deque1 = new ArrayDeque<>();

// With initial capacity
Deque<String> deque2 = new ArrayDeque<>(32);

// From a collection
List<String> list = Arrays.asList("A", "B", "C");
Deque<String> deque3 = new ArrayDeque<>(list);

Real-World Example: Browser History

Deque<String> history = new ArrayDeque<>();

// Visit pages
history.push("google.com");
history.push("youtube.com");
history.push("github.com");

// Current page
System.out.println("Now at: " + history.peek());
// Output: Now at: github.com

// Go back
history.pop();
System.out.println("Now at: " + history.peek());
// Output: Now at: youtube.com

Real-World Example: Undo/Redo

Deque<String> undoStack = new ArrayDeque<>();
Deque<String> redoStack = new ArrayDeque<>();

// User types
undoStack.push("Hello");
undoStack.push("Hello World");
undoStack.push("Hello World!");

// User presses Undo
String undone = undoStack.pop();
redoStack.push(undone);

System.out.println("Current: " + undoStack.peek());
// Output: Current: Hello World

// User presses Redo
String redone = redoStack.pop();
undoStack.push(redone);

System.out.println("Current: " + undoStack.peek());
// Output: Current: Hello World!

🚫 Important Warning

Never store null in ArrayDeque!

Deque<String> deque = new ArrayDeque<>();
deque.offer(null);  // 💥 NullPointerException!

🎯 Quick Comparison

graph TD
    A["Need a Collection?"] --> B{Order matters?}
    B -->|FIFO| C["Queue"]
    B -->|Priority| D["PriorityQueue"]
    B -->|Both ends| E["Deque"]
    C --> F["Use ArrayDeque"]
    E --> F
    D --> G["Use PriorityQueue"]

🏆 Summary Table

🎉 You Did It!

Now you understand:

• ✅ Queue is like a line – first person served first
• ✅ PriorityQueue is like an ER – urgent cases first
• ✅ Deque is like a double-door room – enter/exit anywhere
• ✅ ArrayDeque is the fast, go-to implementation

Next step: Try building a task manager using PriorityQueue!