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#
Let's take the example of this visualization: a queue already holding 10, 20, 30, with 10 at the front and 30 at the back. Press play and watch the dequeue. 10 leaves first because it arrived first, and 20 becomes the new front. Run it against the stack above and the difference is the whole lesson: same three values, opposite exit order.
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
What to Remember#
Queues enforce fairness: whoever arrived first is served first. BFS runs on them, and so does any system that processes work in arrival order. Always use a deque (double-ended queue) or circular buffer implementation, never a plain array, or your O(1) dequeue silently becomes O(N).