平成28年度秋期 ITパスポート 問92 解説
後に入れたデータが先に取り出されるデータ構造（以下，スタックという）がある。これを用いて，図に示すような，右側から入力されたデータの順番を変化させて，左側に出力する装置を考える。この装置に対する操作は次の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
要点スタックは後入れ先出し（LIFO）で、積んだ順の逆に出る
解説
スタックは後に入れたものが先に出るため、積んだA→Bは必ずB→Aの順に出ます。
エ（C，D，A，B）：最初にCを出すにはAとBを積む必要があり、このときスタックは下からA、B。Cを出し、Dをそのまま出した後、上にあるBより先にAは出せないので出力できません。
- ア：Aを積む→Bを出す→Aを出す→Cを積む→Dを出す→Cを出す、で可能。
- イ：Aを積む→Bを出す→Cを積む→Dを出す→C、Aの順に出す、で可能。
- ウ：A、Bを積む→Cを出す→Bを出す→Dを出す→Aを出す、で可能。