平成28年 秋期 ITパスポート 問92

後に入れたデータが先に取り出されるデータ構造(以下、スタックという)がある。
これを用いて、図に示すような、右側から入力されたデータの順番を変化させて、左側に出力する装置を考える。
この装置に対する操作は次の3通りである。

 @  右側から入力されたデータをそのまま左側に出力する。
 A  右側から入力されたデータをスタックの1番上に積み上げる。
 B  スタックの1番上にあるデータを取り出して左側に出力する。

この装置の右側から順番にデータA、B、C、Dを入力した場合に、この@〜Bの操作を組み合わせても、左側に出力できない順番はどれか。

 ア  B, A, D, C
 イ  B, D, C, A
 ウ  C, B, D, A
 エ  C, D, A, B


答え エ


解説

 ア  B, A, D, Cは、A→@→B→A→@→Bで可能です。
 イ  B, D, C, Aは、A→@→A→@→B→Bで可能です。
 ウ  C, B, D, Aは、A→A→@→B→@→Bで可能です。
 エ  C, D, A, Bは、Cを先に出すためにAとBをスタックに積む必要がありますが、このときA→Bの順に取り出すことができません。


キーワード
・スタック

キーワードの解説

戻る 一覧へ 次へ