キュー（待ち行列）とは？FIFO・データ構造の定義・操作・優先度キュー解説

キュー（待ち行列）の基本概念からFIFO動作、Enqueue/Dequeueの操作、優先度キューの仕組みと実装例までわかりやすく解説。

コンピュータサイエンスにおいて、待ち行列はデータ構造の一つであり、処理される前の項目を順序を保って保存するために使われます。最も基本的な性質はFIFO（First In, First Out）で、先に入れた要素が先に出てきます。

基本操作

• Enqueue（エンキュー）：キューの末尾（後ろ）に項目を追加する操作。
• Dequeue（デキュー）：キューの先頭にある項目を取り出して削除する操作。
• Peek / Front（先頭参照）：キューを削除せずに先頭の項目を見る操作（オプションだがよく使われる）。

キューの先頭要素と最後の要素の間にある中間のアイテムは、直接ランダムにアクセスできないのが一般的です（配列の添字でアクセスする実装はあっても概念上は順次アクセス）。

実装方式と計算量

• 単方向連結リスト：先頭から削除（Dequeue）と末尾への追加（Enqueue）をO(1)で実行できる。ただし末尾ポインタを持つ必要がある。
• 配列（循環バッファ）：固定長配列を使い、head/tail インデックスを modulo 演算で管理する。各操作はO(1)で、メモリを連続確保できる利点がある。可変長にする場合は、必要時に再確保（リサイズ）して amortized O(1）となる。
• 動的配列（リングなし）：単純に先頭をずらす実装だと Dequeue がO(n)になるため、インデックスをずらす方式（head/tail 管理）が一般的。

代表的な計算量（単純なキュー）

• Enqueue：O(1)
• Dequeue：O(1)
• Peek：O(1)

バリアントと関連構造

• Deque（デック、双方向キュー）：両端から要素の追加・削除が可能。
• 循環キュー（リングバッファ）：固定長バッファをループ状に扱い高効率な実装。
• バウンド付きキュー / 拡張可能キュー：容量制限があるもの（容量オーバーでエラー／ブロックする）と、必要に応じて拡張するものがある。
• ブロッキングキュー（同期キュー）：空のときに Dequeue を呼ぶと待機し、満杯のときに Enqueue を呼ぶと待機する。プロデューサー・コンシューマー問題でよく使われる。

優先度キュー（プライオリティ・キュー）

優先度キューは一般的なFIFOキューとは異なり、各項目に優先度（重み）が付与され、その優先度に基づいて次に取り出す項目が決まります。最小値（または最大値）を取り出す操作をサポートします。

主な操作：

• Insert（挿入）
• Extract-Min / Extract-Max（最小/最大抽出）
• Decrease-Key / Increase-Key（キーの更新）— 一部の実装でサポート

実装例と計算量（一例）：

• 二分ヒープ（Binary Heap）：Insert O(log n)、Extract O(log n)、Peek O(1)
• d分ヒープ：枝分かれを増やして高さを下げることで定数因子を調整できる
• フィボナッチヒープ：Insert は amortized O(1)、Extract は amortized O(log n)（アルゴリズム設計で理論的利点あり）

優先度キューはDijkstraの最短経路アルゴリズム、イベント駆動シミュレーション、OSのプロセススケジューリングなどで広く使われます。

応用例

• 幅優先探索（BFS）：訪問する頂点をFIFOに入れて順に処理する。
• ジョブスケジューリングやプリントキュー：到着順に処理する単純な場面。
• ネットワークのパケットバッファ：到着順にパケットを取り出すことで順序性を保つ。
• プロデューサー・コンシューマー問題：スレッド間でデータをやり取りする際の同期手段としてのキュー（ブロッキングキューなど）。

注意点とエラー処理

• Underflow（アンダーフロー）：空のキューから Dequeue を呼ぶとエラーまたは例外、あるいは待機（ブロッキングキューの場合）。
• Overflow（オーバーフロー）：固定容量のキューに対して Enqueue を行うとエラーまたは待機。
• 安定性：同じ優先度の要素が挿入順に取り出されるか（安定）どうかは実装次第。FIFOキューは本質的に安定。

簡単な疑似コード（循環バッファ）

 initialize queue:   array A[size]   head = 0   tail = 0   count = 0  Enqueue(x):   if count == size: error "overflow" (または resize)   A[tail] = x   tail = (tail + 1) % size   count = count + 1  Dequeue():   if count == 0: error "underflow" (または block)   x = A[head]   head = (head + 1) % size   count = count - 1   return x  Peek():   if count == 0: error "underflow"   return A[head] 

まとめ

キューは単純だが非常に有用なデータ構造で、FIFOの性質を利用する多くのアルゴリズムやシステムで使われます。用途に応じて配列（循環バッファ）、連結リスト、または優先度キューやブロッキングキューといったバリアントを選ぶことで、性能や挙動を最適化できます。

文字で検索