ITパスポート過去問解説

ITパスポート過去問 28年秋問92

問題

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

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

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

解説

スタックに対するデータ操作は、プッシュとポップがあるが、プッシュは、スタックの1番上にデータを積み上げることで、また、ポップは、スタックの1番上にあるデータを取り出すことである。
スタックには、データを複数入れることができるが、1番上にしか入れることができない。
また、スタックに、データが複数入っていても、取り出すことができるのは、1番上のデータだけ。

このことから、ア～エのような出力ができるかをそれぞれ見ていくと、次のようになる。

■ア　次のようにすれば、B，A，D，Cと出力できる
1　Aをスタックへプッシュ
2　Bをそのまま出力
3　Aをスタックからポップして出力
4　Cをスタックへプッシュ
5　Dをそのまま出力
6　Cをスタックからポップして出力

■イ　次のようにして、B，D，C，Aと出力できる
1　Aをスタックへプッシュ
2　Bをそのまま出力
3　Cをスタックへプッシュ
4　Dをそのまま出力
5　Cをスタックからポップして出力
6　Aをスタックからポップして出力

■ウ　次のようにして、C，B，D，Aと出力できる　
1　Aをスタックへプッシュ
2　Bをスタックへプッシュ
3　Cをそのまま出力
4　Bをスタックからポップして出力
5　Dをそのまま出力
6　Aをスタックからポップして出力

■エ　C，D，A，Bの順で出力することはできない
1　Aをスタックへプッシュ
2　Bをスタックへプッシュ
3　Cをそのまま出力
4　Dをそのまま出力
5　スタックからポップするとBが取り出されるのでBしか出力できない
6　もう1回ポップすると今度はAが取り出されるが、Bの後にしか出力できない

このことから、エが正解となる