Queues

Overview

A queue is a First-In, First-Out (FIFO) collection: items are removed in the same order they were added, like a line at a checkout. The core operations are enqueue (add to back) and dequeue (remove from front). Using collections.deque gives O(1) operations at both ends, whereas a plain list's pop(0) is O(n).

Syntax / Usage

Use deque for an efficient queue.

from collections import deque

queue = deque()

queue.append("a")      # enqueue -> O(1)
queue.append("b")
queue.append("c")

front = queue[0]       # peek front -> O(1) -> "a"
item = queue.popleft() # dequeue    -> O(1) -> "a"

print(len(queue))      # remaining items -> 2

Examples

Process print jobs in the order they arrive:

from collections import deque

jobs = deque(["doc1", "doc2", "doc3"])
while jobs:
    current = jobs.popleft()  # O(1) FIFO
    print("printing", current)
# printing doc1 / doc2 / doc3

Breadth-first traversal uses a queue to visit nodes level by level:

from collections import deque

graph = {"a": ["b", "c"], "b": ["d"], "c": [], "d": []}
visited, queue = set(), deque(["a"])
while queue:
    node = queue.popleft()
    if node not in visited:
        visited.add(node)
        queue.extend(graph[node])  # enqueue neighbors
print(visited)  # {'a', 'b', 'c', 'd'}

Common Mistakes

• Using list.pop(0) for dequeue, which is O(n) instead of O(1)
• Mixing up FIFO (queue) with LIFO (stack) semantics
• Calling popleft() on an empty deque, raising IndexError
• Forgetting to import deque from collections
• Assuming a queue supports fast random access — it does not

See Also

data-structures-stacks data-structures-linked-lists data-structures-arrays