Deques and Priority Queues

When "First Come, First Served" Is Not Enough

Imagine a hospital emergency room at 2 AM. The waiting room has a queue — patients arrive and take a number. But then an ambulance rolls in with someone in critical condition. Should that patient wait behind the person with a sprained ankle who arrived twenty minutes earlier?

Of course not. The hospital uses priority. Critical patients jump to the front regardless of when they arrived. Someone with a minor issue waits even if they got there first. This is the real world, and sometimes importance matters more than order.

This is exactly what a priority queue models. And to understand it fully, we first look at its cousin: the deque.

Part 1: The Deque — Double-Ended Queue

A regular queue allows adding to the back and removing from the front. A deque (pronounced "deck," short for double-ended queue) is more flexible: you can add or remove from either end.

Think of a train car — passengers can board or exit from both the front door and the rear door.

Python's collections.deque

Python's built-in deque supports all four directional operations in O(1):

from collections import deque

d = deque()

# Adding elements
d.append("C")          # Add to the RIGHT (back)  → deque(['C'])
d.append("D")          # Add to the RIGHT         → deque(['C', 'D'])
d.appendleft("B")      # Add to the LEFT (front)  → deque(['B', 'C', 'D'])
d.appendleft("A")      # Add to the LEFT          → deque(['A', 'B', 'C', 'D'])

print("Deque:", d)     # deque(['A', 'B', 'C', 'D'])

# Removing elements
print(d.pop())         # Remove from RIGHT → 'D'  deque(['A', 'B', 'C'])
print(d.popleft())     # Remove from LEFT  → 'A'  deque(['B', 'C'])

# Peeking without removing
print(d[0])            # Front element → 'B'
print(d[-1])           # Back element  → 'C'

# Useful extras
d.rotate(1)            # Rotate right — last element moves to front
print(d)               # deque(['C', 'B'])

d.rotate(-1)           # Rotate left — first element moves to back
print(d)               # deque(['B', 'C'])

Output:

Deque: deque(['A', 'B', 'C', 'D'])
D
A
B
C
deque(['C', 'B'])
deque(['B', 'C'])

All deque Operations at a Glance

Deques are perfect for sliding window problems, implementing both stacks and queues, and palindrome checking (compare from both ends simultaneously).

Part 2: The Priority Queue

A priority queue is an abstract data structure where each element has an associated priority. The element with the highest priority is always removed first, regardless of insertion order.

Priority Queue: A collection where each element has a key (priority), and dequeue() always returns the element with the minimum (or maximum) priority key.

This is not FIFO. It is not LIFO. It is priority-ordered.

Python's heapq Module

The most efficient implementation of a priority queue uses a binary heap — a tree structure that keeps the smallest element at the top. Python's heapq module gives you a min-heap directly on a regular list.

Basic Priority Queue with heapq

import heapq

tasks = []

# heappush(heap, item) — add item to heap while maintaining heap order
heapq.heappush(tasks, (3, "Low priority task"))
heapq.heappush(tasks, (1, "URGENT: Server down!"))
heapq.heappush(tasks, (2, "Medium priority"))
heapq.heappush(tasks, (1, "URGENT: Payment failed!"))

# heappop(heap) — always removes and returns the SMALLEST item
print("Processing tasks by priority:")
while tasks:
    priority, task = heapq.heappop(tasks)
    print(f"  Priority {priority}: {task}")

Output:

Processing tasks by priority:
  Priority 1: URGENT: Payment failed!
  Priority 1: URGENT: Server down!
  Priority 2: Medium priority
  Priority 3: Low priority task

The two priority-1 tasks are processed before priority-2 and priority-3, regardless of the order they were added. Ties in priority are broken by the second element (string comparison).

Peeking Without Removing

import heapq

tasks = [(3, "Low"), (1, "High"), (2, "Medium")]
heapq.heapify(tasks)       # Convert existing list into a valid heap

print("Next task:", tasks[0])   # Peek at the min without removing
# Output: Next task: (1, 'High')

Max-Heap Workaround

heapq is a min-heap by default. To simulate a max-heap, negate the priority values:

import heapq

max_heap = []
heapq.heappush(max_heap, (-5, "Very important"))
heapq.heappush(max_heap, (-1, "Not important"))
heapq.heappush(max_heap, (-3, "Somewhat important"))

while max_heap:
    neg_priority, task = heapq.heappop(max_heap)
    print(f"Priority {-neg_priority}: {task}")

Output:

Priority 5: Very important
Priority 3: Somewhat important
Priority 1: Not important

Thread-Safe: queue.PriorityQueue

For multi-threaded programs where multiple threads add and remove tasks simultaneously, queue.PriorityQueue is the safe choice:

from queue import PriorityQueue

pq = PriorityQueue()
pq.put((2, "Normal task"))
pq.put((1, "High priority"))
pq.put((3, "Background task"))

while not pq.empty():
    priority, task = pq.get()
    print(f"  [{priority}] {task}")

Output:

  [1] High priority
  [2] Normal task
  [3] Background task

queue.PriorityQueue uses locks internally, making it safe for concurrent access. heapq does not — it is single-threaded only.

Priority Queue: Time Complexity

Real-World Applications

Dijkstra's Algorithm — Finding the shortest path in a weighted graph. The algorithm always processes the unvisited node with the smallest known distance. A priority queue makes this efficient.

Operating System Process Scheduling — The OS assigns priorities to processes. Higher-priority processes (like system tasks) get CPU time before lower-priority ones (background downloads).

Event-Driven Simulation — Simulating events over time. Each event has a timestamp as its priority. The simulator always processes the earliest-scheduled event next.

A Pathfinding* — Used in game AI and GPS navigation. Nodes are explored in order of estimated total cost, managed by a priority queue.

Hospital Triage Systems — Exactly the opening analogy. Critical conditions get priority over routine cases, regardless of arrival time.

Deque vs Queue vs Priority Queue

Key Takeaway

When the order of processing must reflect importance rather than arrival time, a priority queue is the right tool. Use heapq for fast single-threaded code, and queue.PriorityQueue when threads are involved. Deques are the flexible generalization of queues — useful when you need access from both ends. Together, these structures cover a huge range of scheduling, search, and simulation problems.