キュー とは？

先に入ったものを先に処理する「待ち行列」のデータ構造。コンビニのレジの列と同じで、最初に並んだ人が最初に処理される（FIFO）。印刷ジョブをスプールに溜めて順番に印刷したり、メッセージキューにタスクを積んで非同期に処理したりするのに使われる。

スタックは「後入れ先出し（LIFO）」。積み重ねたお皿のイメージで、最後に積んだものを最初に取り出す。関数の呼び出し履歴（コールスタック）・ブラウザの戻るボタン（ページ履歴）がスタックの例。キューとスタックはデータ構造の基本的な対として覚えておくと良い。

AWS Simple Queue Serviceの略。クラウドのマネージドメッセージキューサービス。例えばユーザーが画像をアップロードしたとき「変換タスク」をSQSに入れておき、バックエンドのワーカーが順番に取り出して処理する非同期アーキテクチャを簡単に作れる。

通常のキューはFIFOだけど、優先度付きキューは「優先度の高いものから先に処理される」んだ。病院の救急外来で重症者を先に診るのと同じイメージ。アルゴリズムではダイクストラ法（最短経路探索）やA*探索で使われるよ。内部実装にはヒープというデータ構造が使われることが多い。

ここが設計の肝だね。SQSには「可視性タイムアウト」という仕組みがあって、ワーカーがメッセージを取得しても一定時間内に処理完了しないと、メッセージがキューに戻されて別のワーカーが再処理するんだ。さらに何度もリトライして失敗したメッセージは「デッドレターキュー」に送られて、後から人間が確認できるようになっているよ。