Queue Variants

Queue Variants: The Four Magical Lines

Imagine you’re at a theme park with different types of waiting lines. Each line has its own special rules. Let’s discover them all!

The Big Picture

Think of queues as waiting lines. But not all lines work the same way!

• Regular Queue = Normal line at a store
• Deque = A line where people can join OR leave from BOTH ends
• Priority Queue = VIP line where important people go first
• Monotonic Queue = A special line that stays sorted automatically

graph TD
    A["Queue Variants"] --> B["Queue Fundamentals"]
    A --> C["Deque"]
    A --> D["Priority Queue"]
    A --> E["Monotonic Queue"]

1. Queue Fundamentals

What is a Queue?

A queue is like the line at an ice cream truck. First person in line gets served first.

This rule has a fancy name: FIFO (First In, First Out).

Real Life Examples

• Waiting in line for a movie
• Printer jobs waiting to print
• Messages waiting to be sent

The Two Main Actions

JavaScript Example

class Queue {
  constructor() {
    this.items = [];
  }

  enqueue(item) {
    this.items.push(item);
  }

  dequeue() {
    return this.items.shift();
  }

  peek() {
    return this.items[0];
  }

  isEmpty() {
    return this.items.length === 0;
  }
}

Let’s Use It!

const line = new Queue();
line.enqueue("Alice");
line.enqueue("Bob");
line.enqueue("Charlie");

console.log(line.dequeue());
// Output: "Alice" (first in, first out!)

Why Queues Matter

• Fair: Everyone waits their turn
• Organized: No cutting in line
• Predictable: You know when it’s your turn

2. Deque (Double-Ended Queue)

The Magic Line

Imagine a line where you can:

• Join from the FRONT or BACK
• Leave from the FRONT or BACK

That’s a Deque (pronounced “deck”)!

When Would You Use This?

Think of a playlist:

• Add songs to the front (play next)
• Add songs to the back (play later)
• Remove from front (skip current)
• Remove from back (remove last added)

The Four Actions

graph LR
    A["Add Front"] --> B["DEQUE"]
    C["Add Back"] --> B
    B --> D["Remove Front"]
    B --> E["Remove Back"]

JavaScript Example

class Deque {
  constructor() {
    this.items = [];
  }

  addFront(item) {
    this.items.unshift(item);
  }

  addBack(item) {
    this.items.push(item);
  }

  removeFront() {
    return this.items.shift();
  }

  removeBack() {
    return this.items.pop();
  }
}

Let’s Play!

const playlist = new Deque();

playlist.addBack("Song A");
playlist.addBack("Song B");
playlist.addFront("Priority Song");

console.log(playlist.removeFront());
// Output: "Priority Song"

Deque is a Superpower

A Deque can act as:

• A Queue (add back, remove front)
• A Stack (add back, remove back)
• Both at the same time!

3. Priority Queue Fundamentals

The VIP Line

Not all waiting is equal. Sometimes important things go first!

A Priority Queue is like an emergency room:

• Heart attack patient = HIGH priority (treated first)
• Small cut = LOW priority (waits longer)

The Key Idea

Every item has a priority number. Lower number = more important.

graph TD
    A["Add: Task #40;priority 5#41;"] --> B["Priority Queue"]
    C["Add: Urgent #40;priority 1#41;"] --> B
    D["Add: Normal #40;priority 3#41;"] --> B
    B --> E["Remove: Urgent #40;priority 1#41;"]

JavaScript Example

class PriorityQueue {
  constructor() {
    this.items = [];
  }

  enqueue(item, priority) {
    const element = { item, priority };
    let added = false;

    for (let i = 0; i < this.items.length; i++) {
      if (priority < this.items[i].priority) {
        this.items.splice(i, 0, element);
        added = true;
        break;
      }
    }

    if (!added) {
      this.items.push(element);
    }
  }

  dequeue() {
    return this.items.shift()?.item;
  }
}

Real Example

const hospital = new PriorityQueue();

hospital.enqueue("Headache", 3);
hospital.enqueue("Heart Attack", 1);
hospital.enqueue("Broken Arm", 2);

console.log(hospital.dequeue());
// Output: "Heart Attack" (priority 1 = most urgent!)

Where Priority Queues Shine

• Task scheduling: Important tasks first
• Dijkstra’s algorithm: Finding shortest paths
• Operating systems: Managing processes
• Game AI: Deciding what to do next

4. Monotonic Queue

The Sorted Magic Line

This is the trickiest one. Let’s make it simple!

A Monotonic Queue keeps items in order:

• Monotonic Increasing: Each item is bigger than the one before
• Monotonic Decreasing: Each item is smaller than the one before

Why Is This Useful?

Imagine you’re tracking the maximum temperature over a sliding window of days.

Instead of checking every day, a monotonic queue keeps the maximum ready instantly!

The Secret Trick

When adding a new item:

1. Remove all smaller items from the back (for decreasing)
2. Add the new item
3. The front is always the maximum!

graph TD
    A["New Value: 7"] --> B{Is back < 7?}
    B -->|Yes| C["Remove back"]
    C --> B
    B -->|No| D["Add 7 to back"]
    D --> E["Front = Maximum"]

JavaScript Example (Decreasing)

class MonotonicQueue {
  constructor() {
    this.deque = [];
  }

  push(val) {
    // Remove smaller values from back
    while (
      this.deque.length > 0 &&
      this.deque[this.deque.length - 1] < val
    ) {
      this.deque.pop();
    }
    this.deque.push(val);
  }

  pop(val) {
    // Only remove if it's at the front
    if (this.deque[0] === val) {
      this.deque.shift();
    }
  }

  max() {
    return this.deque[0];
  }
}

Sliding Window Maximum

function maxSlidingWindow(nums, k) {
  const mq = new MonotonicQueue();
  const result = [];

  for (let i = 0; i < nums.length; i++) {
    mq.push(nums[i]);

    // Remove element leaving the window
    if (i >= k) {
      mq.pop(nums[i - k]);
    }

    // Window is complete
    if (i >= k - 1) {
      result.push(mq.max());
    }
  }

  return result;
}

// Example
console.log(maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3));
// Output: [3, 3, 5, 5, 6, 7]

When To Use Monotonic Queue

• Finding maximum/minimum in sliding windows
• Next greater/smaller element problems
• Stock span problems
• Histogram problems

Quick Comparison

The Journey So Far

You’ve learned four powerful queue types:

1. Queue - The fair waiting line
2. Deque - The flexible double-door
3. Priority Queue - The VIP treatment center
4. Monotonic Queue - The auto-sorting wizard

Each one solves different problems. Now you have FOUR new tools in your coding toolbox!

Practice Time!

Try implementing each queue type from memory. Start simple:

1. Create a basic Queue
2. Upgrade it to a Deque
3. Build a Priority Queue
4. Challenge yourself with a Monotonic Queue

Remember: The best way to learn is by doing. Happy coding!