基本情報技術者試験のサンプル問題を解こう！（12）（科目B）「優先度付きキューを操作するプログラム」

基本情報技術者試験のサンプル問題（科目B）を解いてみよう。

今回のテーマは、「優先度付きキューを操作するプログラム」」である。

〔プログラム〕

○prioSched( )
PrioQueue: prioQueue ← PrioQueue( )
prioQueue.enqueue("A", 1)
prioQueue.enqueue("B", 2)
prioQueue.enqueue("C", 2)
prioQueue.enqueue("D", 3)
prioQueue.dequeue( ) /* 戻り値は使用しない /
 prioQueue.dequeue( ) / 戻り値は使用しない / 
prioQueue.enqueue("D", 3) 
prioQueue.enqueue("B", 2) 
prioQueue.dequeue( ) / 戻り値は使用しない / 
prioQueue.dequeue( ) / 戻り値は使用しない */
prioQueue.enqueue("C", 2)
prioQueue.enqueue("A", 1)
while (prioQueue.size( ) が 0 と等しくない)
    prioQueue.dequeue( ) の戻り値を出力
 endwhile

解答群
ア “A”，“B”，“C”，“D”
イ “A”，“B”，“D”，“D”
ウ “A”，“C”，“C”，“D”
エ “A”，“C”，“D”，“D”

この問題は、 優先度付きキュー (PrioQueue) の処理をわかりやすく解説した内容である。
なお、プログラム中の行番号は筆者によるものである。

問題を整理しよう

1. 優先度付きキューとは？
   • 各要素に「優先度（prio）」が付いており、小さい値ほど高優先度である。
   • dequeue() は 最も優先度が高い（prio が最小）ものから順に取り出す。
   • 同優先度の要素が複数ある場合、先に enqueue された順番で取り出される。
2. プログラムの流れ
   • enqueue と dequeue の動きを追い、最後に while 内で dequeue() の戻り値を出力する。

ステップごとのキューの中身を確認しよう

○prioSched( )　　　　　　　　　　　　プログラムの定義
PrioQueue: prioQueue ← PrioQueue( )　空の優先度付きキューを生成
enqueue("A", 1) → [("A",1)]          先度付きキューに文字列"A"を要素として、優先度1で追加する
enqueue("B", 2) → [("A",1), ("B",2)]
enqueue("C", 2) → [("A",1), ("B",2), ("C",2)]
enqueue("D", 3) → [("A",1), ("B",2), ("C",2), ("D",3)]
　　　　　　　　　　　　　　　　　　　　行番号３と同様に文字列を追加する
dequeue() → "A" を取り出す（最優先）
              キュー→ [("B",2), ("C",2), ("D",3)]
dequeue() → "B" を取り出す（BとCはprio=2でBの方が先）
              キュー→ [("C",2), ("D",3)]

enqueue("D",3) → [("C",2), ("D",3), ("D",3)]
enqueue("B",2) → [("C",2), ("D",3), ("D",3), ("B",2)]

dequeue() → "C" を取り出す（CとBはprio=2でCが先）
              キュー→ [("D",3), ("D",3), ("B",2)]
dequeue() → "B" を取り出す（prio=2が最優先）
              キュー→ [("D",3), ("D",3)]

enqueue("C",2) → [("D",3), ("D",3), ("C",2)]
enqueue("A",1) → [("D",3), ("D",3), ("C",2), ("A",1)]

この状態から while ループで dequeue() を4回実行すると、出力は、

"A" → prio=1（最優先）  
"C" → prio=2  
"D" → prio=3（先に追加されたD）  
"D" → prio=3（2つ目のD） 

したがって、“A”, “C”, “D”, “D” の順で出力される。

まとめ

• 優先度付きキューでは、優先度順 + FIFO順（同じ優先度内）がポイント。
• 問題では、enqueue と dequeue のタイミングを追っていくのが肝となる。
• 表や状態遷移図を使って、キューの中身を整理しながら理解すると効果的。