What Is a Queue?
A queue is a First-In, First-Out (FIFO) data structure. The first element you add is the first one out — like a queue at a coffee shop: first person in line gets served first.
Core Operations
| Operation | Description | Time |
|---|---|---|
enqueue(item) | Add item to the back | O(1) |
dequeue() | Remove and return front | O(1) |
front() | View front without removing | O(1) |
is_empty() | Check if queue has items | O(1) |
Use Python's
collections.dequeor Java'sArrayDeque— not a plain list/array, because removing from the front of an array is O(N).
Implementation
Interactive Lab
Queue vs Stack — Quick Comparison
| Property | Queue (FIFO) | Stack (LIFO) |
|---|---|---|
| Add | Back | Top |
| Remove | Front | Top |
| Metaphor | Line at a counter | Stack of plates |
| Algorithm use | BFS | DFS, recursion |
The Ring Buffer (Circular Queue)
A common implementation uses a fixed-size circular array. Instead of shifting elements (O(N)), use head and tail index pointers that wrap around:
This is how O(1) dequeue is achieved in the C implementation above.
Key Applications
- BFS traversal of graphs and trees (the queue drives the level-by-level expansion)
- Task schedulers — OS process queues, print spoolers
- Message queues — Kafka, RabbitMQ (async job processing)
- Buffers — keyboard input buffer, network packet queue
- Level-order tree traversal
Key Takeaway
Queues enforce fairness — whoever arrived first is served first. They're the backbone of BFS and any system that processes work in arrival order. Always use a deque (double-ended queue) or circular buffer implementation, never a plain array — otherwise your O(1) dequeue silently becomes O(N).