キューのユースケース：BFS、タスクスケジューリング、メッセージキュー

キューの実世界アプリケーション

キューはソフトウェアシステムの至るところにあります。FIFO特性は公平性と順序を保証し、多くの問題に対する自然な選択となります。

1. 幅優先探索（BFS）

BFSはキューを使用してグラフをレベルごとに探索します：

ノードAから開始
Queue: [A]
Aを訪問、隣接ノードB, Cをenqueue -> Queue: [B, C]
Bを訪問、隣接ノードDをenqueue     -> Queue: [C, D]
Cを訪問、隣接ノードEをenqueue     -> Queue: [D, E]
Dを訪問（新しい隣接ノードなし）    -> Queue: [E]
Eを訪問（新しい隣接ノードなし）    -> Queue: []

キューにより距離1のすべてのノードを距離2の前に、距離2を距離3の前に訪問します。これがBFSが重み無しグラフで最短経路を見つける理由です。

2. タスクスケジューリング

OSはCPUスケジューリングにキューを使用します：

• ラウンドロビンスケジューリング：各プロセスにタイムスライスが与えられ、時間が切れると後方にenqueueされ、先頭のプロセスがCPUを得る。
• ジョブキュー：バッチジョブは投入順に処理。
• I/Oキュー：ディスクやネットワークリクエストはデバイスが利用可能になるまでキューで待機。

3. メッセージキュー

分散システムはメッセージキュー（RabbitMQ、Kafka、SQS）を使用してプロデューサーとコンシューマーを分離します。キューはバッファとして機能し、トラフィックのバーストをコンシューマーを圧倒せずに処理します。

4. 印刷スプーリング

印刷ジョブはFIFO順に処理されます。プリンタに最初に送信されたドキュメントが最初に印刷され、複数ユーザーがプリンタを共有する際の公平性が保証されます。

5. レートリミティング

トークンバケットやスライディングウィンドウのレートリミッターはリクエストタイムスタンプを追跡するためにキューをよく使用します。

6. 非同期処理

Webアプリケーションはタスク（メール送信、画像処理、レポート生成）をバックグラウンドワーカー用にキューに入れます。これにより遅い操作がメインのリクエスト-レスポンスサイクルをブロックすることを防ぎます。