Queue Variants

🎢 Queue Variants: The Ultimate Line Adventure

The Story of Lines That Never Forget

Imagine you’re at the world’s most amazing amusement park. There are different types of lines everywhere! Some lines are simple—first in, first out. Others let VIPs jump ahead. Some let you enter and exit from both ends like a magical tunnel. And one special line even remembers who the tallest person is at all times!

That’s exactly what Queue Variants are in programming!

Today, we’ll explore four incredible types of “smart lines”:

• 🎯 Queue Fundamentals - The classic fair line
• 🔄 Deque - The two-door line
• ⭐ Priority Queue - The VIP line
• 📊 Monotonic Queue - The “who’s tallest?” line

🎯 Queue Fundamentals: The Classic Fair Line

What is a Queue?

A Queue is like a line at your favorite ice cream shop.

graph TD
    A["🧒 New Person"] --> B["Back of Line"]
    B --> C["Wait Your Turn"]
    C --> D["Front of Line"]
    D --> E["🍦 Get Ice Cream!"]

The Golden Rule: First In, First Out (FIFO)

• The person who arrives first gets served first
• New people join at the back
• People leave from the front

Simple Example

from collections import deque

# Create a line (queue)
ice_cream_line = deque()

# People join the line
ice_cream_line.append("Alice")
ice_cream_line.append("Bob")
ice_cream_line.append("Charlie")

# Who's first? Alice!
first = ice_cream_line.popleft()
print(first)  # Alice

Real Life Examples

• 🎬 Movie ticket line
• 🏦 Bank queue
• 📨 Print jobs waiting
• 🚗 Cars at a drive-through

Key Operations

🔄 Deque: The Two-Door Tunnel

What is a Deque?

Deque (pronounced “deck”) means Double-Ended Queue.

Imagine a tunnel with doors on both ends. You can:

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

graph LR
    A["🚪 Front Door"] <--> B["📦 Items"]
    B <--> C["🚪 Back Door"]

Why is this amazing?

A regular queue only lets you:

• Add at back
• Remove from front

A deque lets you:

• Add at front AND back
• Remove from front AND back

Simple Example

from collections import deque

# Create a deque
tunnel = deque()

# Add from both ends
tunnel.append("right")      # Add to back
tunnel.appendleft("left")   # Add to front

print(list(tunnel))
# ['left', 'right']

# Remove from both ends
tunnel.pop()        # Remove from back
tunnel.popleft()    # Remove from front

Real Life Examples

• 🎮 Undo/Redo in games (add recent, remove old)
• 🚂 Train cars (connect from either end)
• 📚 Sliding window problems (add right, remove left)

Key Operations

⭐ Priority Queue: The VIP Line

What is a Priority Queue?

Imagine a hospital emergency room. Not everyone waits in order of arrival. A person with a broken finger waits longer than someone having a heart attack!

Priority Queue = Important things go first!

graph TD
    A["New Patient Arrives"]
    A --> B{How urgent?}
    B -->|Emergency!| C["Jump to Front"]
    B -->|Not urgent| D["Wait in Line"]
    C --> E["Get Help First"]
    D --> E

The Magic Rule

• Each item has a priority (a number)
• Lower number = Higher priority (usually)
• Highest priority always comes out first!

Simple Example

import heapq

# Create priority queue
emergency = []

# Add patients (priority, name)
heapq.heappush(emergency, (3, "Headache"))
heapq.heappush(emergency, (1, "Heart Attack"))
heapq.heappush(emergency, (2, "Broken Arm"))

# Who gets help first?
first = heapq.heappop(emergency)
print(first)  # (1, 'Heart Attack')

Real Life Examples

• 🏥 Hospital emergencies
• ✈️ Airplane boarding (First class first!)
• 📧 Important emails
• 🎮 Game AI (attack strongest enemy)

Key Operations

How Priority Queue Works (The Heap)

Under the hood, Python uses a min-heap. Think of it like a pyramid where:

• Parent is always smaller than children
• Smallest item is always at the top!

graph TD
    A["1: Heart Attack"] --> B["2: Broken Arm"]
    A --> C["3: Headache"]

📊 Monotonic Queue: The “Who’s Tallest?” Line

What is a Monotonic Queue?

This is the coolest queue variant!

Imagine you’re tracking the tallest kid in a sliding window. As kids enter and leave your view, you always want to know: “Who’s the tallest right now?”

Monotonic = Items are always in order (biggest to smallest OR smallest to biggest)

graph LR
    A["5"] --> B["4"]
    B --> C["3"]
    C --> D["1"]
    style A fill:#4CAF50

The front always has the biggest (or smallest) item!

The Magic Trick

When a new item comes in:

1. Remove everyone smaller than it from the back
2. Add the new item to the back
3. The front is ALWAYS the maximum!

Simple Example

from collections import deque

def max_sliding_window(nums, k):
    result = []
    q = deque()  # stores indices

    for i, num in enumerate(nums):
        # Remove old indices
        while q and q[0] <= i - k:
            q.popleft()

        # Remove smaller elements
        while q and nums[q[-1]] < num:
            q.pop()

        q.append(i)

        if i >= k - 1:
            result.append(nums[q[0]])

    return result

nums = [1, 3, -1, -3, 5, 3, 6, 7]
print(max_sliding_window(nums, 3))
# [3, 3, 5, 5, 6, 7]

Visual Walkthrough

Window size = 3, Array = [1, 3, -1, -3, 5]

Why is this Fast?

• Naive approach: Check all k elements each time → O(n×k)
• Monotonic Queue: Each element enters and leaves once → O(n)

It’s like magic! 🎩✨

Real Life Examples

• 📈 Stock market: Max price in last 7 days
• 🌡️ Weather: Hottest day in last week
• 🎮 Games: Highest score in last 10 rounds

🎯 Quick Comparison

🚀 When to Use What?

graph TD
    A["Need a Queue?"]
    A --> B{Need both ends?}
    B -->|Yes| C["Use Deque"]
    B -->|No| D{Need priorities?}
    D -->|Yes| E["Use Priority Queue"]
    D -->|No| F{Need max/min in window?}
    F -->|Yes| G["Use Monotonic Queue"]
    F -->|No| H["Use Regular Queue"]

💡 Pro Tips

1. Python’s deque is your best friend for queues
2. heapq gives you priority queues (min-heap)
3. Monotonic queues are just deques used cleverly
4. All these are O(1) for their main operations (except heap which is O(log n))

🎉 You Did It!

You now understand the four amazing queue variants:

1. ✅ Queue - First come, first served
2. ✅ Deque - Enter/exit from both ends
3. ✅ Priority Queue - VIPs go first
4. ✅ Monotonic Queue - Always know the max/min

These are like superpowers for solving problems efficiently. The more you practice, the more natural they become!

Remember: Every data structure is just a smart way to organize things. Queues are simply “smart lines” that help your program run faster and cleaner.

Happy coding! 🐍✨