Queues
A queue is a linear data structure that follows the FIFO (First-In-First-Out) principle. The first element inserted is the first one removed. Think of a line of people — the first person in line is served first.
Core Operations
- Enqueue(item): Add an item to the back of the queue — O(1)
- Dequeue(): Remove and return the item from the front — O(1)
- Front(): Return the front item without removing it — O(1)
- isEmpty(): Check if the queue is empty — O(1)
Circular Buffer (Array-based Queue)
An array-based queue uses a fixed-size array with head and tail pointers that wrap around (modular arithmetic). When tail catches up to head, the queue is full.
Advantage: O(1) enqueue and dequeue without shifting elements.
Variations
| Type | Description |
|---|---|
| Simple Queue | FIFO, basic enqueue/dequeue |
| Circular Queue | Array-based, wraps around for space efficiency |
| Priority Queue | Elements dequeued by priority, not insertion order |
| Deque | Double-ended queue — insert/remove from both ends |
| Blocking Queue | Thread-safe, blocks on empty/full (concurrency) |
Common Applications
- BFS (Breadth-First Search): Queue holds vertices to visit level by level.
- Task scheduling: CPU scheduling (round-robin), job queues.
- Resource pools: Database connection pools, thread pools.
- Asynchronous messaging: Message queues, event loops.
- Buffering: I/O buffers, streaming data, print spooling.
Queue vs Stack
| Property | Stack | Queue |
|---|---|---|
| Order | LIFO | FIFO |
| Insert | Push (top) | Enqueue (back) |
| Remove | Pop (top) | Dequeue (front) |
| Use case | Function calls, undo | BFS, scheduling |