後に入れたデータが先に取り出されるデータ構造(以下、スタックという)がある。
これを用いて、図に示すような、右側から入力されたデータの順番を変化させて、左側に出力する装置を考える。
この装置に対する操作は次の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の順に取り出すことができません。 |
【キーワード】
・スタック