Overview
A Queue is a linear data structure that follows the FIFO (First-In, First-Out) principle. The first element added to the queue is the first one to be removed. Think of it like a line of people waiting for a bus.
Core Concepts
- Enqueue: Adding an element to the end (rear) of the queue.
- Dequeue: Removing an element from the front of the queue.
- Front/Peek: Looking at the first element without removing it.
- Time Complexity:
- Enqueue: $O(1)$.
- Dequeue: $O(1)$ (if implemented with a linked list or circular buffer).
- Search: $O(n)$.
Code Examples
class Queue<T> {
private items: T[] = [];
enqueue(element: T): void { this.items.push(element); }
dequeue(): T | undefined { return this.items.shift(); } // Note: shift() is O(n) in JS arrays
peek(): T | undefined { return this.items[0]; }
isEmpty(): boolean { return this.items.length === 0; }
}
const printQueue = new Queue<string>();
printQueue.enqueue("Doc1.pdf");
printQueue.enqueue("Doc2.pdf");
console.log(printQueue.dequeue()); // "Doc1.pdf"Use Cases
- Task Scheduling: Operating systems use queues to manage processes waiting for CPU time.
- Breadth-First Search (BFS): Queues are used to track nodes to visit next in a graph traversal.
- Message Brokers: Systems like RabbitMQ use queues to handle asynchronous communication between services.
Gotchas
- Array Performance: Using
Array.prototype.shift()in JavaScript for a queue is $O(n)$ because all other elements must be re-indexed. For production, use a linked list or a double-ended queue (Deque). - Queue Overflow: In fixed-size buffers, attempting to enqueue into a full queue.