キュー
まず結論
キューはFIFO（First In First Out）＝「最初に入れたものが最初に出てくる」データ構造です。コンビニのレジ行列や印刷待ちと同じ仕組み。追加（enqueue）は末尾、取り出し（dequeue）は先頭から行います。
キューのしくみ：FIFOを図で理解
enqueue（追加）
→
dequeue（取り出し）
→
A（最初に入った）
追加は末尾（右）から ／ 取り出しは先頭（左）から → FIFO
キューの操作とトレース
| 操作 | キューの状態（先頭→末尾） | 取り出し値 |
|---|---|---|
| 初期状態 | （空） | - |
| enqueue(10) | [10] | - |
| enqueue(20) | [10, 20] | - |
| enqueue(30) | [10, 20, 30] | - |
| dequeue() | [20, 30] | 10（最初に入った） |
| enqueue(40) | [20, 30, 40] | - |
| dequeue() | [30, 40] | 20 |
キューの用途
・プリンタの印刷待ちキュー
・ネットワークのパケット送受信
・CPU の実行待ちプロセス管理
・幅優先探索（BFS）
スタックとの違い
スタック: LIFO（後入れ先出し）
キュー: FIFO（先入れ先出し）
スタック→「積み重ね」
キュー→「行列・待ち行列」
循環キュー
配列でキューを実装する際、dequeueを繰り返すと先頭が後ろにずれていく問題がある。循環キューは配列の末尾を先頭に繋げることでメモリを効率的に利用する。
循環キューのポイント：frontとrearのインデックスをモジュロ演算（% 配列サイズ）で循環させる。front == rear のとき「空」、(rear + 1) % size == front のとき「満杯」。
🎯 試験での出方
- 「FIFO（先入れ先出し）の構造」→ キュー
- 「プリンタの印刷待ちに使われるデータ構造」→ キュー
- enqueue/dequeueの操作後のキューの状態を問う問題
- スタック（LIFO）との違いを問う問題
⚠️ よくある間違い
- 「キューはLIFO」→ ✗ キューはFIFO。LIFOはスタック
- 「enqueueは先頭に追加」→ ✗ enqueueは末尾に追加、dequeueは先頭から取り出し
- 「キューとスタックは同じもの」→ ✗ 全く逆の取り出し順序
✍️ 確認クイズ
Q1. キューにA→B→Cの順でenqueueした後、dequeueを1回行った。取り出される値はどれか。
✅ 正解は①。キューはFIFO（先入れ先出し）。最初にenqueueされたAが最初にdequeueされます。
Q2. キューの性質を正しく表しているものはどれか。
✅ 正解は②。キューはFIFO（First In First Out）。最初に入れたデータが最初に出てきます。スタックはLIFO（Last In First Out）です。
Q3. キューが実際のシステムで使われている例として適切なものはどれか。
✅ 正解は③。プリンタの印刷待ちはFIFO（先に送ったものが先に印刷）なのでキューを使います。「戻る」機能やコールスタックはスタック（LIFO）です。
Q4. 空のキューに対してenqueue(A)→enqueue(B)→dequeue()→enqueue(C)→dequeue()の操作後、キューの状態はどれか。
✅ 正解は③。操作を順番に追うと：enqueue(A)→[A]、enqueue(B)→[A,B]、dequeue()→Aを取り出し[B]、enqueue(C)→[B,C]、dequeue()→Bを取り出し[C]。FIFOのルールで先頭から取り出すことを確実に追跡することが重要です。
Q5. 優先度付きキュー（Priority Queue）の説明として正しいものはどれか。
✅ 正解は③。優先度付きキューは各要素に優先度を設け、追加順ではなく優先度が高い要素から取り出します。OSのプロセススケジューリング（優先度順）や、ダイクストラ法（最短経路算出）に使われます。通常のキュー（FIFO）とは異なります。
Sponsor Link