後に入れたデータが先に取り出されるデータ構造（以下，スタックという）がある。これを用いて，図に示すような，右側から入力されたデータの順番を変化させて，左側に出力する装置を考える。この装置に対する操作は次の3通りである。 ① 右側から入力されたデータをそのまま左側に出力する。 ② 右側から入力されたデータをスタックの1番上に積み上げる。 ③ スタックの1番上にあるデータを取り出して左側に出力する。 この装置の右側から順番にデータA, B, C, Dを入力した場合に，この①〜③の操作を組み合わせても，左側に出力できない順番はどれか。
- アB, A, D, C
- イB, D, C, A
- ウC, B, D, A
- エC, D, A, B
正解と解説を見る
正解
エ C, D, A, B
正解は④(C, D, A, B)。このデータ構造はLIFO(後入れ先出し)のスタックであり、一度スタックの下に積まれたデータは、その上にあるデータが先に取り出されるまで取り出せない。C, D, A, Bを出力するには、Cを出すために先にA, Bをスタックに積む必要があるが、その結果Aの上にBが積まれた状態になり、3番目にAを出そうとしてもBがまだ必要とされておらず取り出せないため、この順序は実現できない。他の選択肢(B,A,D,C / B,D,C,A / C,B,D,A)はいずれもスタック操作の組合せで実現可能である。