This question's explanation and your answers so far.
後に入れたデータが先に取り出されるデータ構造 (以下, スタックという) がある。これを用いて, 図に示すような, 右側から入力されたデータの順番を変化させて, 左側に出力する装置を考える。この装置に対する操作は次の3通りである。 ① 右側から入力されたデータをそのまま左側に出力する。 ② 右側から入力されたデータをスタックの1番上に積み上げる。 ③ スタックの1番上にあるデータを取り出して左側に出力する。 この装置の右側から順番にデータ A, B, C, D を入力した場合に, この①～③の操作を組み合わせても, 左側に出力できない順番はどれか。
“B, A, D, C” can be produced. Push A, push B, and pop them in the order B→A (B, A); then push C, push D, and pop them in the order D→C (D, C), yielding B, A, D, C. Since it can be output, this is not the answer.
“B, D, C, A” can be produced. Push A, push B and pop B (B); push C, push D, and pop them in the order D→C (D, C); finally pop the remaining A (A), yielding B, D, C, A. Since it can be output, this is not the answer.
“C, B, D, A” can be produced. Push A, B, C in order and pop them in the order C→B (C, B); then push D and pop it (D); finally pop the remaining A (A), yielding C, B, D, A. Since it can be output, this is not the answer.
正解 A stack is “last-in, first-out (LIFO)”: the data pushed later is taken out earlier. The data arrives from the right in the order A→B→C→D, and for each item you can choose to “output it directly (①)”, “push it (②)”, or “pop it and output it (③)”. To build option エ “C, D, A, B”, you must first push A and B so that C can be output first, then push C and pop it; at this point A and B remain in the stack from the bottom up, with B on top. Next you can push D and pop it to output D, but when you then try to output A, A is buried beneath B, and you cannot pop A unless you first pop B. In other words, B is always taken out before A, so you cannot produce an order that ends with “A, B” (with A coming before B). Therefore エ is an order that cannot be output, and this is the correct answer.