Data Structures

Queues

A queue is a First-In, First-Out (FIFO) data structure. Like a line at a coffee shop — the first person to join is the first to be served. New items join at the back (enqueue); items leave from the front (dequeue).

What Is a Queue?

Text

Enqueue 10 → [10]
Enqueue 20 → [10, 20]
Enqueue 30 → [10, 20, 30]
Dequeue    → returns 10  → [20, 30]   ← FIFO
Dequeue    → returns 20  → [30]

⚠️

Do not use list for queues

list.pop(0) is O(n) because Python must shift all remaining elements one position to the left. Always use collections.deque for O(1) dequeue from the front.

Using collections.deque

deque (double-ended queue) provides O(1) append and popleft from both ends using a doubly-linked list of fixed-size blocks.

Python

from collections import deque

queue = deque()

# Enqueue (add to back) — O(1)
queue.append(10)
queue.append(20)
queue.append(30)
print(queue)        # deque([10, 20, 30])

# Dequeue (remove from front) — O(1)
front = queue.popleft()   # 10
print(queue)              # deque([20, 30])

# Peek at front without removing
print(queue[0])     # 20

# Size
print(len(queue))   # 2

Queue Class

Python

from collections import deque

class Queue:
    def __init__(self):
        self._data = deque()

    def enqueue(self, item):
        self._data.append(item)      # O(1)

    def dequeue(self):
        if self.is_empty():
            raise IndexError("dequeue from empty queue")
        return self._data.popleft()  # O(1)

    def peek(self):
        if self.is_empty():
            raise IndexError("peek at empty queue")
        return self._data[0]

    def is_empty(self):
        return len(self._data) == 0

    def __len__(self):
        return len(self._data)

q = Queue()
q.enqueue('a'); q.enqueue('b'); q.enqueue('c')
print(q.peek())     # 'a'
print(q.dequeue())  # 'a'
print(len(q))       # 2

Priority Queue

A priority queue dequeues the highest-priority element first, regardless of insertion order. Python’s heapq module implements a min-heap.

Python

import heapq

pq = []
heapq.heappush(pq, (3, 'low priority'))
heapq.heappush(pq, (1, 'high priority'))
heapq.heappush(pq, (2, 'medium priority'))

# Always pops the smallest (highest priority) item
while pq:
    priority, task = heapq.heappop(pq)
    print(f"{priority}: {task}")
# Output:
# 1: high priority
# 2: medium priority
# 3: low priority

Use Cases

Use Case	Why a Queue?
BFS traversal	Explore nodes level by level using FIFO order
Task scheduling	Process tasks in the order they arrive
Print spooler	Print jobs processed in submission order
Message queues	Events processed in order (Kafka, RabbitMQ)
Dijkstra’s algorithm	Min-heap priority queue for shortest path