This question's explanation and your answers so far.
下から上へデータを積み上げ，上にあるデータから順に取り出すデータ構造（以下，スタックという）がある。これを用いて，図に示すような，右側から入力されたデータの順番を変化させて，左側に出力する装置を考える。この装置に対する操作は次の3通りである。 ① 右側から入力されたデータをそのまま左側に出力する。 ② 右側から入力されたデータをスタックに積み上げる。 ③ スタックの1番上にあるデータを取り出して左側に出力する。 この装置の右側から順番に X，Y，Z を入力した場合に，この①～③の操作を組み合わせても，左側に出力できない順番はどれか。
“X, Z, Y”can be achieved, so it is not an order that cannot be output. Output X directly with ① → push Y onto the stack with ② → output Z directly with ① → take Y off the stack with ③ and output it, which gives X, Z, Y.
“Y, Z, X”can be achieved, so it is not an order that cannot be output. Push X onto the stack with ② → output Y directly with ① → output Z directly with ① → take X off with ③ and output it, which gives Y, Z, X.
正解 The correct answer is ウ“Z, X, Y”. To output Z first on the left side, the only way is to push both X and Y, which are input earlier, onto the stack with operation ②. Since the input order is X→Y→Z, the stack holds X at the bottom and Y on top of it. At that point Z can be output straight to the left with ① the moment it is input. However, the remaining X and Y can only be taken from the very top of the stack with ③, so Y, which is on top, comes out first and X, which is below it, comes out later. In other words, the item that can follow Z is always Y, and the order“X right after Z”cannot be produced. Therefore, the order that cannot be output no matter how ①-③ are combined is ウ.
“Z, Y, X”can be achieved, so it is not an order that cannot be output. Push X with ② → push Y with ② (X at the bottom, Y on top) → output Z directly with ① → output Y with ③ → output X with ③, which gives Z, Y, X. Reversing the input order exactly is the move a stack is best at.