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