A queue is a FIFO (first-in, first-out) container with enqueue (add to back) and dequeue (remove from front). Use collections.deque in Python — O(1) at both ends. A list as a queue is O(n) per dequeue and a common performance bug.
| Average | Worst | Space | ||||||
|---|---|---|---|---|---|---|---|---|
| Access | Search | Insertion | Deletion | Access | Search | Insertion | Deletion | Worst |
Θ(n) |
Θ(n) |
Θ(1) |
Θ(1) |
O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
Backed by a circular buffer or doubly-linked list with head and tail pointers. Enqueue advances tail; dequeue advances head. Both are pointer-bumps, so O(1). Indexing or searching by value still requires a scan — O(n).
from collections import deque
q = deque()
q.append("a") # enqueue
q.append("b")
q.append("c")
print(q.popleft()) # "a" — dequeue, O(1)
print(q.popleft()) # "b"
# DON'T do this — list.pop(0) is O(n):
# q = []
# q.append("a"); q.pop(0) # shifts every remaining element
# Explicit class:
class Queue:
def __init__(self):
self._d = deque()
def enqueue(self, x): # O(1)
self._d.append(x)
def dequeue(self): # O(1)
if not self._d:
raise IndexError("dequeue from empty queue")
return self._d.popleft()
def peek(self): # O(1)
return self._d[0]
def __len__(self):
return len(self._d)deque; O(n) per dequeue with list — always reach for deque.queue.Queue (thread-safe), asyncio.Queue (async), multiprocessing.Queue (cross-process).heapq.A queue is an abstract data type that returns elements in the order they arrived: first in, first out. Its two core operations are enqueue, which adds at the back, and dequeue, which removes from the front; most implementations also provide peek and size. Queues model anything that must be processed fairly in arrival order, such as print jobs, network packets, tasks for a worker pool, or the frontier of a breadth-first search. The key implementation requirement is that both ends are O(1). A Python list fails this at the front, because removing index 0 shifts every remaining element; collections.deque and circular buffers meet it.
| Operation | deque / circular buffer | Python list (pop(0)) |
|---|---|---|
| enqueue | O(1) amortised | O(1) amortised |
| dequeue | O(1) | O(n) |
| peek front | O(1) | O(1) |
| search | O(n) | O(n) |
| space | O(n) | O(n) |
Queues appear in two related variants. A double-ended queue (deque) allows insertion and removal at both ends and can act as either a queue or a stack. A priority queue, despite the name, is not FIFO: it always returns the element with the highest priority and is usually implemented with a binary heap. Choosing the wrong one is a common source of subtle bugs, for example using a priority queue when fairness in arrival order was required. Bounded queues add a third consideration: what happens when the queue is full. The options are to block the producer, to reject the new item, or to drop the oldest item, as a deque with maxlen does.
A circular buffer stores elements in a fixed array with two indices. The head points to the next element to dequeue; the tail points to where the last element was written. Both advance with modulo arithmetic, so when the tail reaches the end of the array it wraps to index 0 and reuses slots freed by earlier dequeues. No elements are ever shifted. A separate count (or one deliberately empty slot) distinguishes a full buffer from an empty one, because in both cases head and tail can be equal. A growable version doubles the array when full and copies elements in order, giving amortised O(1) enqueue.
class CircularQueue:
def __init__(self, capacity=8):
self.buf = [None] * capacity
self.head = 0 # index of front element
self.size = 0
def enqueue(self, x):
if self.size == len(self.buf):
self._grow()
tail = (self.head + self.size) % len(self.buf)
self.buf[tail] = x
self.size += 1
def dequeue(self):
if self.size == 0:
raise IndexError("dequeue from empty queue")
x = self.buf[self.head]
self.buf[self.head] = None # release reference
self.head = (self.head + 1) % len(self.buf)
self.size -= 1
return x
def _grow(self):
old = self.buf
self.buf = [old[(self.head + i) % len(old)] for i in range(self.size)]
self.buf += [None] * len(old)
self.head = 0
q = CircularQueue(2)
for c in "abcde":
q.enqueue(c)
print([q.dequeue() for _ in range(5)]) # ['a', 'b', 'c', 'd', 'e']
Outside algorithms, queues are the standard way to connect components running at different speeds. A web request can enqueue a job and return immediately while a worker processes it later. In-process, Python offers queue.Queue for threads and asyncio.Queue for coroutines; across machines, brokers such as RabbitMQ, Amazon SQS or Kafka play the same role with durability. Bounding the queue size is important: an unbounded queue hides overload until memory runs out, while a bounded one pushes back on producers.
from collections import deque
import queue, threading
# Breadth-first search: the queue holds the frontier in distance order
graph = {"A": ["B", "C"], "B": ["D"], "C": ["D", "E"], "D": ["F"], "E": ["F"], "F": []}
def bfs(start):
dist, q = {start: 0}, deque([start])
while q:
node = q.popleft()
for nxt in graph[node]:
if nxt not in dist:
dist[nxt] = dist[node] + 1
q.append(nxt)
return dist
print(bfs("A")) # {'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 2, 'F': 3}
# Bounded producer/consumer with worker threads
jobs = queue.Queue(maxsize=10)
def worker():
while (item := jobs.get()) is not None:
print("processed", item)
jobs.task_done()
jobs.task_done()
t = threading.Thread(target=worker); t.start()
for i in range(3):
jobs.put(i) # blocks if the queue is full
jobs.put(None) # sentinel to stop the worker
jobs.join(); t.join()
BFS visits nodes in order of distance precisely because the queue is FIFO; replacing it with a stack turns the same loop into depth-first search.
| Need | Use |
|---|---|
| Single-threaded FIFO | collections.deque |
| Threads sharing work | queue.Queue (with maxsize) |
| Coroutines | asyncio.Queue |
| Highest priority first | heapq or queue.PriorityQueue |
| Both ends, sliding window | deque with maxlen |
| Across processes or machines | multiprocessing.Queue, SQS, RabbitMQ, Kafka |
list.pop(0) as dequeue, turning O(n) algorithms into O(n^2).q.empty() then calling get() across threads; the state can change between the calls.