The Checkout Line
A Queue is a linear data structure that follows the FIFO (First-In, First-Out) principle. The first item added is the first item removed — exactly like a checkout line at a grocery store. The person who joined the line first gets served first.
Core operations — all O(1):
| Operation | Description |
|---|---|
enqueue(item) |
Add item to the back |
dequeue() |
Remove and return the front item |
peek() |
Return the front item without removing it |
is_empty() |
Check if the queue has no items |
Implementation note: Do NOT implement a queue with a Python list using pop(0) — that is O(N) because it shifts every element. Use collections.deque instead, which provides O(1) append() (enqueue) and popleft() (dequeue).
from collections import deque
q = deque()
q.append("first") # enqueue
q.append("second")
q.popleft() # dequeue → returns "first"
Real-World Use Cases
- Printer Jobs: Documents are printed in the order they were submitted.
- Web Server Request Handling: Incoming HTTP requests are queued and processed in order.
- Breadth-First Search (BFS): The defining algorithm for shortest-path problems on unweighted graphs. A queue ensures nodes are explored layer by layer, guaranteeing the shortest path is found first.
- Rate Limiting: API gateways queue excess requests rather than dropping them immediately.
- Message Brokers: Systems like Kafka and RabbitMQ are essentially distributed, durable queues.
Key Point: The choice between a Stack (DFS) and a Queue (BFS) in graph traversal is not arbitrary — it determines the order in which nodes are visited and which problems each approach solves. BFS with a queue finds the shortest path in unweighted graphs. DFS with a stack is better for detecting cycles, topological sorting, and exhaustive path enumeration. Knowing when to use each is a senior-level distinction.