Queues

A queue is a data structure that follows FIFO — First In, First Out. The first element added is the first one to be removed, just like a real-world queue (line of people).

Structure

A queue tracks two ends: - HEAD (H) — the front, where elements are removed - TAIL (T) — the back, where new elements are added

H                             T
↓                             ↓
[1] → [2] → [3] → [4] → [5]

New elements enter at the TAIL →
Elements leave from the HEAD ←

Two Core Operations

Enqueue (add to tail)

A new element always enters at the tail:

Before: [1] → [2] → [3] → [4]
Enqueue 5
After:  [1] → [2] → [3] → [4] → [5]

Dequeue (remove from head)

An element always leaves from the head:

Before: [1] → [2] → [3] → [4] → [5]
Dequeue
After:        [2] → [3] → [4] → [5]
Returns: 1

Both operations are O(1) — no traversal needed since we always know exactly where the head and tail are.

In Python

Python has two ways to work with queues:

queue.Queue (thread-safe)

from queue import Queue

q = Queue()

q.put(1)
q.put(2)
q.put(3)

print(q.get())  # 1  ← first in, first out
print(q.get())  # 2

collections.deque (double-ended queue)

from collections import deque

q = deque()

q.append(1)    # add to tail
q.append(2)
q.append(3)

q.popleft()    # remove from head → 1

deque also supports adding and removing from both ends (left and right), making it more flexible.

How deque Works Internally

Under the hood, Python's deque is implemented in C (_collectionsmodule.c) as a doubly-linked list of fixed-length blocks (each block holds 64 elements):

Block 0        Block 1        Block 2
[64 items] ↔ [64 items] ↔ [64 items]

Key design decisions: - No realloc — appending or popping never moves other elements in memory, unlike arrays. - Fixed-length blocks — instead of one node per element (which would cost one malloc() per item), Python groups 64 elements per block. This makes the memory-to-data ratio much better. - Better cache locality — consecutive elements within a block are near each other in memory, which speeds up access.

This is why deque is the preferred choice for queues in Python: O(1) at both ends, memory-efficient, and faster in practice than a plain list.

Big O Summary

Key Takeaways

• Queue = FIFO: first element in is the first element out.
• Always add to the tail, always remove from the head.
• In Python, prefer collections.deque for performance, or queue.Queue when working with threads.
• deque is backed by a doubly-linked list of blocks — O(1) at both ends with no memory reallocation.