A queue is a linear data structure that enforces first-in, first-out (FIFO) access — elements are inserted (enqueued) at the rear and removed (dequeued) from the front — providing O(1) enqueue, dequeue, and peek.
A queue is a line: the first person to join is the first to be served — first-in, first-out.
First-in, first-out (FIFO)
A queue has two operations: enqueue (add to the back) and dequeue (remove from the front). The element that has been waiting longest is always the next to be processed. This is FIFO — first-in, first-out.
from collections import deque
queue = deque()
queue.append("task_1") # enqueue — O(1)
queue.append("task_2")
queue.append("task_3")
print(queue[0]) # peek front: "task_1"
print(queue.popleft()) # dequeue: "task_1" — O(1)
print(queue.popleft()) # dequeue: "task_2"
print(list(queue)) # ["task_3"]Complexity table
| Operation | Average | Worst | Notes |
|---|---|---|---|
| Enqueue (insert at back) | O(1) | O(1) | Add to rear |
| Dequeue (remove from front) | O(1) | O(1) | Remove from front |
| Peek / Front | O(1) | O(1) | Read front without removing |
| Search | O(n) | O(n) | No random access |
| Space | O(n) | O(n) |
Where queues appear
Task schedulers: OS process scheduler keeps a queue of ready processes — each gets a turn in FIFO order (round-robin variant). Message queues (RabbitMQ, Kafka, SQS): producers enqueue messages; consumers dequeue in order. Breadth-first search (BFS): explore the graph level by level — enqueue the start node; repeatedly dequeue, process, enqueue unvisited neighbours. Print spoolers: documents print in the order submitted. Network packet buffers: packets processed in arrival order.
from collections import deque
def bfs(graph, start):
visited, queue = {start}, deque([start])
while queue:
node = queue.popleft() # FIFO
print(node, end=" ")
for neighbour in graph[node]:
if neighbour not in visited:
visited.add(neighbour)
queue.append(neighbour)Implementing a queue: the circular buffer
A naive array-backed queue that always dequeues from index 0 requires O(n) shift per dequeue. A circular buffer (ring buffer) solves this: maintain head and tail indices into a fixed-size array. Enqueue: write at tail, advance tail modulo capacity. Dequeue: read from head, advance head modulo capacity. Both are O(1). Used in OS kernel ring buffers, audio DSP pipelines, and network driver packet buffers.
class CircularQueue:
def __init__(self, capacity):
self.buf = [None] * capacity
self.cap = capacity
self.head = self.tail = self.size = 0
def enqueue(self, val): # O(1)
if self.size == self.cap: raise OverflowError("full")
self.buf[self.tail] = val
self.tail = (self.tail + 1) % self.cap
self.size += 1
def dequeue(self): # O(1)
if self.size == 0: raise IndexError("empty")
val = self.buf[self.head]
self.head = (self.head + 1) % self.cap
self.size -= 1
return valPriority queues
A priority queue is a generalised queue where each element has a priority, and dequeue always returns the highest-priority element (not necessarily the oldest). Implemented using a heap — O(log n) enqueue and dequeue. Python: heapq module. Java: PriorityQueue. Used in Dijkstra's algorithm, A* search, and OS schedulers with priority levels.
import heapq
pq = []
heapq.heappush(pq, (3, "low priority task"))
heapq.heappush(pq, (1, "urgent task"))
heapq.heappush(pq, (2, "medium task"))
while pq:
priority, task = heapq.heappop(pq)
print(f"{priority}: {task}")
# 1: urgent task
# 2: medium task
# 3: low priority taskDeque: double-ended queue
A deque (double-ended queue) supports O(1) insert and delete at both ends. Python's collections.deque is a doubly-linked list of 64-element fixed-size blocks — O(1) at both ends, O(n) random access. Java's ArrayDeque is a circular array — O(1) amortised at both ends. Deques are used as the backing structure for both stacks and queues.
list is not efficient as a queue. list.pop(0) is O(n) — it shifts every element left. Use collections.deque which gives O(1) popleft().POSIX message queues and kernel ring buffers
The operating system implements several queue abstractions. POSIX message queues (mq_open, mq_send, mq_receive) provide inter-process communication with FIFO ordering and optional priority. The Linux kernel's struct kfifo is a lock-free single-producer single-consumer circular buffer using memory barriers to ensure visibility without mutexes — O(1) enqueue and dequeue.
BFS and shortest paths
BFS on an unweighted graph finds the shortest path (minimum number of edges) between the start and every reachable vertex. Proof: BFS explores vertices in order of their distance from the source. Let d(v) be the true shortest-path distance. BFS assigns distance d(u)+1 to each neighbour v of u when u is dequeued. Since u was dequeued before all nodes at distance d(u)+1, v's distance is correct. This invariant is maintained by the FIFO property of the queue — Cormen et al. CLRS §22.2 provides the complete proof by induction.
CLRS (4th ed.), §10.1 — Queues; §22.2 — Breadth-first search. POSIX.1-2017 — mq_send, mq_receive. Linux kernel source: include/linux/kfifo.h.