下から上へデータを積み上げ、上にあるデータから順に取り出すデータ構造（以下、スタックという）がある。これを用いて、図に示すような、右側から入力されたデータの順番を変化させて、左側に出力する装置を考える。この装置に対する操作は次の3通りである。①右側から入力されたデータをそのまま左側に出力する。②右側から入力されたデータをスタックに積み上げる。③スタックの1番上にあるデータを取り出して左側に出力する。この装置の右側から順番にX、Y、Zを入力した場合に、この①〜③の操作を組み合わせても、左側に出力できない順番はどれか。

選択肢

• アX, Z, Y
• イY, Z, X
• ウZ, X, Y
• エZ, Y, X

正解と解説

正解：ウ Z, X, Y

スタックは後に入れたものが先に出る構造なので、いったん積んだデータより先に、それより下にあるデータを取り出すことはできない。Zを最初に出すにはX、Yを順に積む必要があり、その状態でスタックの一番上はYであるから、次に出せるのはYに限られる。したがってZの次にXが出る順番は実現できない。

選択肢ごとの解説

• アXをそのまま出し、Yを積んでZを出してからYを出せば実現できる。
• イXとYを積んでYを出し、Zを出してからXを出せば実現できる。
• ウZを出すにはX、Yを積む必要があり、次に取り出せるのは上にあるYなので実現できない。
• エXとYを積んだ後にZ、Y、Xの順で出せば実現できる。

同じ分野の他の問題

• ディレクトリ又はファイルがノードに対応する木構造で表現できるファイルシステムがある。ルートディレクトリを根として図のよう…2022年度 秋期 問90
• 下から上へ品物を積み上げて、上にある品物から順に取り出す装置がある。この装置に対する操作は、次の二つに限られる。 PUS…2019年度 秋期 問62
• 複数のデータが格納されているスタックからのデータの取出し方として、適切なものはどれか。2018年度 秋期 問76
• 先入れ先出し（First-In First-Out, FIFO）処理を行うのに適したキューと呼ばれるデータ構造に対して“…2018年度 春期 問96
• 後に入れたデータが先に取り出されるデータ構造（以下，スタックという）がある。これを用いて，図に示すような，右側から入力さ…2016年度 秋期 問92