Queues, Deques & Priority Queues in Python

The Story That Explains Queues

All three structures share one DNA: they manage ordered access to elements. The difference is which end you can touch and which element comes out next.

Queue Anatomy — FIFO Visual

Python Code — Regular Queue with collections.deque

Python has no dedicated Queue class for general algorithmic use. The correct tool is collections.deque, which gives O(1) append and popleft — unlike a plain list whose pop(0) is O(n).

from collections import deque

# ── Create an empty queue ──────────────────────────────────
q = deque()

# ── Enqueue (add to tail) ──────────────────────────────────
q.append("ticket_001")   # O(1)
q.append("ticket_002")
q.append("ticket_003")
print("Queue:", q)

# ── Peek at head (without removing) ───────────────────────
print("Head:", q[0])           # O(1)

# ── Dequeue (remove from head) ────────────────────────────
served = q.popleft()          # O(1)
print("Served:", served)
print("Remaining:", q)

# ── Size check ────────────────────────────────────────────
print("Size:", len(q))
print("Empty?", len(q) == 0)

# ── Drain the queue ───────────────────────────────────────
while q:
    print("→ Serving", q.popleft())

Deque — Double-Ended Queue

Python Deque — Full API

from collections import deque

dq = deque([10, 20, 30])

# ── Add elements ──────────────────────────────────────────
dq.append(40)          # right  → [10,20,30,40]   O(1)
dq.appendleft(5)      # left   → [5,10,20,30,40] O(1)

# ── Remove elements ───────────────────────────────────────
r = dq.pop()            # right  → 40  O(1)
l = dq.popleft()       # left   → 5   O(1)
print(dq)              # deque([10, 20, 30])

# ── Peek ──────────────────────────────────────────────────
print(dq[0], dq[-1])  # 10  30  — O(1) both ends

# ── Rotate (useful for round-robin scheduling) ────────────
dq.rotate(1)           # [30, 10, 20]  right-rotate by 1
dq.rotate(-1)          # [10, 20, 30]  back to original

# ── Bounded deque (sliding window) ───────────────────────
window = deque(maxlen=3)
for x in [1, 2, 3, 4, 5]:
    window.append(x)
print(window)           # deque([3, 4, 5], maxlen=3)

Priority Queue — Heap-Based Ordering

A Priority Queue serves elements in priority order, not arrival order. Python's heapq module implements a min-heap: the smallest element always exits first. For a max-heap, negate your values.

Python heapq — Complete Priority Queue

import heapq

# ── Min-Heap (default) ────────────────────────────────────
heap = []
heapq.heappush(heap, (3, "Task C"))
heapq.heappush(heap, (1, "Task A"))   # priority 1 → highest
heapq.heappush(heap, (2, "Task B"))
heapq.heappush(heap, (5, "Task E"))

# Peek at root (min element) — O(1)
print("Next:", heap[0])

# Pop smallest — O(log n)
while heap:
    prio, task = heapq.heappop(heap)
    print(f"Serving [{prio}] {task}")

# ── Max-Heap trick: negate priority ──────────────────────
max_heap = []
for prio, task in [(3,"C"),(1,"A"),(5,"E")]:
    heapq.heappush(max_heap, (-prio, task))  # negate!

neg_prio, task = heapq.heappop(max_heap)
print(f"Max-heap top: [{-neg_prio}] {task}")

# ── heapify an existing list — O(n) ──────────────────────
data = [(4,"D"), (2,"B"), (7,"G"), (1,"A")]
heapq.heapify(data)
print("Heapified root:", data[0])

Time & Space Complexity Table

Real-World Use Cases

Real-World Pattern — BFS with Queue

from collections import deque

def bfs(graph, start):
    """Breadth-First Search — returns visit order."""
    visited = set()
    queue   = deque([start])
    order   = []

    while queue:
        node = queue.popleft()          # O(1) — always deque, never list
        if node in visited:
            continue
        visited.add(node)
        order.append(node)
        for neighbour in graph.get(node, []):
            if neighbour not in visited:
                queue.append(neighbour)

    return order

# Example graph (adjacency list)
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [], 'E': [], 'F': []
}

print(bfs(graph, 'A'))

Real-World Pattern — Dijkstra with Priority Queue

import heapq

def dijkstra(graph, start):
    """Shortest weighted path — Priority Queue drives node selection."""
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    pq = [(0, start)]          # (cost, node)

    while pq:
        cost, node = heapq.heappop(pq)   # always picks cheapest node
        if cost > dist[node]:
            continue               # stale entry — skip
        for nbr, weight in graph[node]:
            new_cost = cost + weight
            if new_cost < dist[nbr]:
                dist[nbr] = new_cost
                heapq.heappush(pq, (new_cost, nbr))
    return dist

graph = {
    'A': [('B', 1), ('C', 4)],
    'B': [('C', 2), ('D', 5)],
    'C': [('D', 1)],
    'D': []
}
print(dijkstra(graph, 'A'))

Queue vs Deque vs Priority Queue — At a Glance

Queue Operations — Pipeline View

Golden Rules