キューに入れる・取り出すを並べただけのプログラムで、キューの中身を1行ずつ書き出していけば解けます。気をつけるのは2点 ── 途中で取り出したものは出力されないこと、最後に残ったものは入れた順ではなく優先度の順に出ることです。
難易度 ★★（当サイトの目安）── メソッドの説明を読み、出し入れを順に表で追う。一本道だが回数が多い。4段階の決め方は科目B 最短合格の戦略にあります。
出題
出典：基本情報技術者試験 科目B サンプル問題 問8
次の記述中の に入れる正しい答えを，解答群の中から選べ。
優先度付きキューを操作するプログラムである。優先度付きキューとは扱う要素に優先度を付けたキューであり，要素を取り出す際には優先度の高いものから順番に取り出される。クラスPrioQueue は優先度付きキューを表すクラスである。クラスPrioQueue の説明を図に示す。ここで，優先度は整数型の値1，2，3 のいずれかであり，小さい値ほど優先度が高いものとする。
手続prioSched を呼び出したとき，出力は の順となる。
コンストラクタ PrioQueue() … 空の優先度付きキューを生成する。
メソッド enqueue(文字列型: s, 整数型: prio) 戻り値：なし … 優先度付きキューに，文字列s を要素として，優先度prio で追加する。
メソッド dequeue() 戻り値：文字列型 … 優先度付きキューからキュー内で最も優先度の高い要素を取り出して返す。最も優先度の高い要素が複数あるときは，そのうちの最初に追加された要素を一つ取り出して返す。
メソッド size() 戻り値：整数型 … 優先度付きキューに格納されている要素の個数を返す。
図 クラスPrioQueue の説明（原本は表。当サイトで1行ずつに並べ直しました。字句は変えていません）
〔プログラム〕
○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”
答えだけ先に見る
正解は エ（“A”，“C”，“D”，“D”）です。
この問題に出てくる記号
読めない記号があったときだけ開いてください。
擬似言語の記号 3コ の読み方をひらく
| 書き方 | 読み方 |
|---|---|
PrioQueue: prioQueue ← PrioQueue() |
空の優先度付きキューを1つ作って、prioQueue という名前を付ける |
prioQueue.enqueue("A", 1) |
prioQueue に対して enqueue を呼ぶ。ここでは要素 “A” を優先度 1 で追加する |
/* … */ |
注釈（説明のための書き込み）。実行には関係ない |
コードは何をしているか
プログラムは、キューに入れる（enqueue）と取り出す（dequeue）を並べただけです。dequeue の戻り値とは、メソッドが返してくる値 ── ここでは取り出した要素です。途中の dequeue には「戻り値は使用しない」とあるので、取り出した要素は捨てられ、出力されません。出力されるのは、最後の while で残りを全部取り出すときだけです。
取り出す順の決まりは、図の説明のとおり2つです。
- 優先度の数字がいちばん小さい要素を取り出す（1 が最優先）
- いちばん小さい数字が複数あれば、先に追加したほう
キューの中身を1行ずつ追って、出力を決める
キューの中身を、追加した順に左から並べて書いていきます。「次へ」で1行ずつ進みます。上の列が要素、下の列がその優先度です。
1行ずつ追う prioSched()
出典：科目B サンプル問題 問8
ループ開始前
配列
いま計算していること
変数の状態
出力
トレース表（進めると1行ずつ積み上がります）
出力を決めるのは、14行目が終わったときに残っている4つです。
14行目のあとに残る4つ ── 入れた順と、出てくる順
琥珀＝最後に入れたが最初に出る A ／ 緑＝出力される順
残っている4つ（入れた順）
要素
D
D
C
A
優先度
3
3
2
1
A はいちばん最後に入れましたが、優先度は 1。
while で取り出される順（優先度の小さい順）
要素
A
C
D
D
優先度
1
2
3
3
A（1）→ C（2）→ D（3）→ D（3）。出力は “A”，“C”，“D”，“D”。
8行目・11行目でも優先度 2 が2つ並びますが、11行目で残ったほうは12行目で、8行目で残ったほうも11〜12行目で取り出されるので、どちらを先に出しても最後に残る4つは同じです。この問題では、同じ優先度の決まりは答えを左右しません。
解答群を見る
“A”，“C”，“D”，“D” は エ です。
答え合わせ
正解は エ です。
前半で取り出した A・B・C・B は捨てられているので、出力には出てきません。出力は最後の while の4つだけで、いちばん最後に入れた A が優先度 1 で先頭に出ます。
次に読む
この問題でどこに手間取ったかで、行き先が変わります。
この記事で引用した資料
いずれも独立行政法人情報処理推進機構（IPA）が公表したものです。IPAは公表済みの試験問題について、教育目的での使用に許諾および使用料を不要としていますが、著作権は放棄していません。本記事では問題文を改変せずに引用しています。
