平成28年度 秋期 ITパスポート試験 問92
テクノロジ／アルゴリズム後に入れたデータが先に取り出されるデータ構造（以下，スタックという）がある。これを用いて，図に示すような，右側から入力されたデータの順番を変化させて，左側に出力する装置を考える。この装置に対する操作は次の3通りである。 ① 右側から入力されたデータをそのまま左側に出力する。 ② 右側から入力されたデータをスタックの 1 番上に積み上げる。 ③ スタックの 1 番上にあるデータを取り出して左側に出力する。 この装置の右側から順番にデータ A, B, C, D を入力した場合に，この①～③の操作を組み合わせても，左側に出力できない順番はどれか。
出典：平成28年度 秋期 ITパスポート試験 問92
- アB, A, D, C
- イB, D, C, A
- ウC, B, D, A
- エC, D, A, B
正解：エ
解説
スタックは後入れ先出し（LIFO）です。データは A→B→C→D の順に入り，各データは「そのまま出力」「スタックに積む」のどちらかになり，積んだものは新しい方から取り出されます。C, D, A, B の場合，最初に C を出すには A, B を先に積んで C を出す必要があり，そのとき B が A の上に載っています。その後 A を出すには B を先に出さなければならないので，A, B の順には出せません。
下線の用語は 用語集 で意味を確認できます。
選択肢ごとの解説
- ア誤り。A を積み，B をそのまま出力，A を取り出し，C を積み，D を出力，C を取り出す，という操作で出力できます。
- イ誤り。A を積み，B を出力，C を積み，D を出力，C を取り出し，A を取り出す，という操作で出力できます。
- ウ誤り。A，B を積み，C を出力，B を取り出し，D を出力，A を取り出す，という操作で出力できます。
- エ正しい。C の後 A を出すには，上に載っている B を先に出す必要があるので，A，B の順にはできず，出力できません。