サンプル問題 科目B 問8

問題

次の記述中の [  ] に入れる正しい答えを，解答群の中から選べ。 
 
優先度付きキューを操作するプログラムである。優先度付きキューとは扱う要素に優先度を付けたキューであり，要素を取り出す際には優先度の高いものから順番に取り出される。クラス PrioQueue は優先度付きキューを表すクラスである。クラス PrioQueue の説明を図に示す。ここで，優先度は整数型の値 1，2，3 のいずれか
であり，小さい値ほど優先度が高いものとする。 手続 prioSched を呼び出したとき，出力は [  ] の順となる。 

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

出典：基本情報技術者試験 サンプル問題

キューとは？

キュー（英: queue）あるいは待ち行列は、コンピュータにおける基本的なデータ構造の一つ。データを先入れ先出しのリスト構造で保持するものである。キューからデータを取り出すときには、先に入れられたデータから順に取り出される。キューにデータを入れることをエンキュー、取り出すことをデキューという。

（Wikipedia）

具体的に考えてみる

プログラムを実行したとき、各段階でキューの内容がどうなるか具体的に考えます。

(a)まで実行した時

(a)まで実行すると、優先度1から3のキューにそれぞれ値が入ります。優先度2のキューの内容は、enqueueメソッドを先に呼び出したBがキューの先頭になります。

(b)まで実行した時

(b)まで実行すると、キューから2個の要素を取り出します。優先度が高い方から取り出すので、A、Bが取り出せます。

(c)まで実行した時

(c)まで実行すると、優先度2, 3のキューにBとDを追加するので、こうなります。

(d)まで実行した時

(d)まで実行すると、キューから2個取り出します。優先度順に取り出すので、優先度2のキューが空になります。

(e)まで実行した時

(e)では、新たに2個の要素を追加され、このような状態になります。

(f)まで実行した時

(f)ではキューのサイズが0になるまで取り出すので、キューはこうなります。

取り出す順は優先度が高い方からA、C、D、D。

優先度3の2つのDは、キュー先頭のDを先に取り出します。

回答

A、C、D、Dの順に取り出すので、エが答えです。