Queue Variants

🎢 Queue Variants: The Amazing Line-Up Adventures!

The Story of Waiting in Line

Imagine you’re at a super fun amusement park. There are different rides, and each ride has a special way people wait in line. Some lines are simple—first person in goes first. Others let important guests skip ahead. And some magical lines even let you enter from both ends!

That’s exactly what Queue Variants are in Java! Different ways to organize waiting lines for your data.

🎯 What We’ll Discover Today

graph TD
    A["Queue Variants"] --> B["Queue Fundamentals"]
    A --> C["Deque"]
    A --> D["Priority Queue"]
    A --> E["Monotonic Queue"]
    B --> B1["First In First Out"]
    C --> C1["Double-Ended Magic"]
    D --> D1["VIP Treatment"]
    E --> E1["Sorted Superhero"]

🎪 Chapter 1: Queue Fundamentals

The Ice Cream Truck Story

Picture an ice cream truck arriving at your street. Kids line up to buy ice cream.

The rule is simple:

• First kid to arrive → First kid to get ice cream
• Last kid to arrive → Last kid to get ice cream

This is called FIFO — First In, First Out!

What is a Queue?

A Queue is like a waiting line. Data enters from the back and leaves from the front.

import java.util.Queue;
import java.util.LinkedList;

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

// Kids join the line (back)
iceCreamLine.offer("Emma");
iceCreamLine.offer("Liam");
iceCreamLine.offer("Sophia");

// Who's first? (front)
System.out.println(
    iceCreamLine.peek()
); // Emma

// Serve ice cream (remove front)
iceCreamLine.poll(); // Emma leaves

Key Queue Operations

💡 Real Life Examples

• Printer jobs — First document sent prints first
• Customer support — First caller gets helped first
• YouTube videos — Watch queue plays in order

Why Use Queue?

✅ Fair ordering — Everyone waits their turn ✅ Predictable — You know exactly who’s next ✅ Simple — Easy to understand and use

🎭 Chapter 2: Deque (Double-Ended Queue)

The Magic Door Story

Imagine a special theater with doors on BOTH sides. Actors can:

• Enter from the front door OR the back door
• Exit from the front door OR the back door

This is a Deque (pronounced “deck”)—a line with two ends!

What is a Deque?

Deque = Double Ended Queue

Unlike a regular queue (one way in, one way out), a Deque lets you add and remove from both ends!

import java.util.Deque;
import java.util.ArrayDeque;

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

// Add to FRONT
magicLine.addFirst("VIP Guest");

// Add to BACK
magicLine.addLast("Regular Person");

// Remove from FRONT
magicLine.removeFirst();

// Remove from BACK
magicLine.removeLast();

Deque as Stack AND Queue

The magic: A Deque can act as BOTH!

graph LR
    subgraph Deque
    A["Front"] <--> B["Items..."] <--> C["Back"]
    end
    D["Add/Remove"] --> A
    E["Add/Remove"] --> C

As Queue (FIFO):

deque.addLast(item);   // Join back
deque.removeFirst();   // Leave front

As Stack (LIFO):

deque.addFirst(item);  // Push to front
deque.removeFirst();   // Pop from front

Key Deque Operations

💡 Real Life Examples

• Browser history — Go back AND forward
• Undo/Redo — Actions from both ends
• Card deck — Draw from top or bottom

Why Use Deque?

✅ Flexible — Two-way access ✅ Fast — O(1) for both ends ✅ Versatile — Works as stack or queue

👑 Chapter 3: Priority Queue Fundamentals

The Hospital Emergency Room Story

Imagine a hospital emergency room. Not everyone waits equally!

• 🚑 Heart attack → Treated IMMEDIATELY
• 🤕 Broken arm → Treated soon
• 🤧 Small cold → Wait longer

The sickest patients go first, not the first to arrive!

This is a Priority Queue — items with higher priority come out first!

What is a Priority Queue?

A Priority Queue doesn’t follow FIFO. Instead, it follows priority order!

import java.util.PriorityQueue;

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

// Patients arrive (random order)
patients.offer(5);  // Mild case
patients.offer(1);  // Critical!
patients.offer(3);  // Moderate

// Who gets treated first?
// SMALLEST number = highest priority
System.out.println(
    patients.poll()
); // 1 (Critical)

System.out.println(
    patients.poll()
); // 3 (Moderate)

System.out.println(
    patients.poll()
); // 5 (Mild)

Understanding Priority

By default: Smaller number = Higher priority

Want bigger = higher? Use a Comparator:

// Max priority (bigger first)
PriorityQueue<Integer> maxPQ =
    new PriorityQueue<>(
        (a, b) -> b - a
    );

maxPQ.offer(5);
maxPQ.offer(1);
maxPQ.offer(3);

maxPQ.poll(); // Returns 5 (biggest)

How Priority Queue Works (Heap)

Inside, it uses a heap (a special tree):

graph TD
    A["1 - Highest"] --> B["3"]
    A --> C["5"]
    B --> D["7"]
    B --> E["4"]

The smallest (or highest priority) is always at the top!

Key Operations & Time

💡 Real Life Examples

• CPU scheduling — Important tasks first
• Dijkstra’s algorithm — Closest node first
• Event systems — Urgent events first

Why Use Priority Queue?

✅ Smart ordering — Important things first ✅ Efficient — Heap structure is fast ✅ Essential — Many algorithms need it

🦸 Chapter 4: Monotonic Queue

The Superhero Scanning Story

Imagine a superhero flying over buildings, always watching the tallest building in view.

As the superhero moves, some buildings leave the view, new ones enter. The superhero always needs to know: “What’s the tallest building I can see RIGHT NOW?”

This is a Monotonic Queue — a queue that stays sorted (increasing or decreasing)!

What is Monotonic Queue?

A Monotonic Queue maintains elements in sorted order. There are two types:

Monotonic Decreasing: Biggest at front (like finding max) Monotonic Increasing: Smallest at front (like finding min)

The Sliding Window Problem

Classic use: Find maximum in a sliding window.

Array: [1, 3, -1, -3, 5, 3, 6, 7]
Window size: 3

Window [1,3,-1] → Max: 3
Window [3,-1,-3] → Max: 3
Window [-1,-3,5] → Max: 5
...

How Monotonic Queue Works

import java.util.*;

public int[] maxSlidingWindow(
    int[] nums, int k
) {
    Deque<Integer> dq =
        new ArrayDeque<>();
    int[] result =
        new int[nums.length - k + 1];

    for (int i = 0; i < nums.length; i++) {
        // Remove old elements outside window
        while (!dq.isEmpty()
            && dq.peekFirst() < i - k + 1) {
            dq.pollFirst();
        }

        // Remove smaller elements
        // (they'll never be max)
        while (!dq.isEmpty()
            && nums[dq.peekLast()] < nums[i]) {
            dq.pollLast();
        }

        // Add current index
        dq.offerLast(i);

        // Record result
        if (i >= k - 1) {
            result[i - k + 1] =
                nums[dq.peekFirst()];
        }
    }
    return result;
}

Visualization

graph LR
    subgraph Monotonic Decreasing Queue
    A["5"] --> B["3"] --> C["1"]
    end
    D["Biggest at Front"]
    D --> A

When new number comes:

1. Remove from back all smaller numbers
2. Add new number to back
3. Front is always the maximum!

Key Properties

💡 Real Life Examples

• Stock prices — Max price in last 7 days
• Temperature — Hottest day in sliding week
• Network traffic — Peak usage in window

Why Use Monotonic Queue?

✅ O(1) max/min access — Instant answers ✅ Efficient windows — O(n) for all windows ✅ Algorithm power — Solves hard problems easily

🎓 Summary: Your Queue Toolkit

graph TD
    A["Need a Line?"] --> B{What kind?}
    B -->|Simple FIFO| C["Queue"]
    B -->|Both ends| D["Deque"]
    B -->|By importance| E["Priority Queue"]
    B -->|Sliding max/min| F["Monotonic Queue"]

Quick Comparison

🚀 You Did It!

You now understand the four amazing queue variants:

1. Queue — The fair line (first come, first served)
2. Deque — The magic two-way line
3. Priority Queue — The VIP treatment line
4. Monotonic Queue — The always-sorted superhero

Each one is a powerful tool in your Java toolkit. Use them wisely, and your programs will be faster, smarter, and more elegant!

Remember: Just like choosing the right line at an amusement park, choosing the right queue makes all the difference! 🎢