Queue
DSA · Stacks and Queues
Theory
A queue is a First-In-First-Out (FIFO) collection: items are added at the back (enqueue) and removed from the front (dequeue), like a line at a ticket counter. Both operations should be O(1). Using list.pop(0) is O(n) because every element shifts, so Python code uses collections.deque, which is a double-ended queue with O(1) operations at both ends.
Why we use it
Queues process work in arrival order, which keeps systems fair and predictable.
When to use it
Use queues for task scheduling, printer jobs, message processing, rate limiting, and breadth-first search.
How it works
- Empty queue
- Enqueue? Yes: Add item at the rear. No: Dequeue: remove from the front.
- Queue empty when dequeuing? Yes: Underflow. No: Return the front item.
- FIFO: first in, first out
Syntax
from collections import deque
q = deque()
q.append(x) # enqueue O(1)
q.popleft() # dequeue O(1)
q[0] # frontExample
from collections import deque
orders = deque()
for o in ["Order#101", "Order#102", "Order#103"]:
orders.append(o)
print("Received", o)
while orders:
print("Preparing", orders.popleft(), "| waiting:", list(orders))Key points
- FIFO: first in, first out
- Use deque, not list.pop(0)
- enqueue and dequeue are O(1)
- Core of BFS and job scheduling