Queue Use Cases: BFS, Task Scheduling, and Message Queues

Real-World Queue Applications

Queues are everywhere in software systems. The FIFO property guarantees fairness and ordering, making queues the natural choice for many problems.

1. Breadth-First Search (BFS)

BFS uses a queue to explore a graph level by level:

Start at node A
Queue: [A]
Visit A, enqueue neighbors B, C -> Queue: [B, C]
Visit B, enqueue neighbor D     -> Queue: [C, D]
Visit C, enqueue neighbor E     -> Queue: [D, E]
Visit D (no new neighbors)      -> Queue: [E]
Visit E (no new neighbors)      -> Queue: []

The queue ensures we visit all nodes at distance 1 before distance 2, distance 2 before distance 3, and so on. This is why BFS finds the shortest path in unweighted graphs.

2. Task Scheduling

Operating systems use queues for CPU scheduling:

• Round-robin scheduling: Each process gets a time slice. When its time expires, it is enqueued at the rear, and the front process gets the CPU.
• Job queue: Batch jobs are processed in the order they are submitted.
• I/O queue: Disk and network requests wait in a queue until the device is available.

3. Message Queues

Distributed systems use message queues (RabbitMQ, Kafka, SQS) to decouple producers and consumers:

• Producers enqueue messages at their own pace.
• Consumers dequeue and process messages at their own pace.
• The queue acts as a buffer, handling bursts of traffic without overwhelming the consumer.

4. Print Spooling

Print jobs are processed in FIFO order. The first document sent to the printer is printed first, ensuring fairness when multiple users share a printer.

5. Rate Limiting

Token bucket and sliding window rate limiters often use queues to track request timestamps. Old timestamps are dequeued as they fall outside the window; new requests are enqueued. If the queue size exceeds the limit, the request is rejected.

6. Asynchronous Processing

Web applications enqueue tasks (email sending, image processing, report generation) for background workers. This prevents slow operations from blocking the main request-response cycle.