平成22年度 秋期 午前 問5

✓ これが正解ウC, B, D, A

解説

内側に残る文字は到着とは逆の順にしか出せません。

スタックは、最後に入れたものが先に出る入れ物です。データは到着した順にしか入れられないので、ある文字を取り出した時点で中に残っている文字は、必ず到着とは逆の並びで積み上がっています。そこで出力列を左から1文字ずつ見て、その文字を出すまでに何を積むことになるかをたどれば、実現できるかどうかが判定できます。正解の列は、まず3文字を積んでから2文字を取り出し、次の1文字を積んで取り出し、最後に底に残っていた1文字を取り出す順で作れます。判定の軸は、取り出した直後に上にくる文字が、出力列の次の文字と一致しているかどうかです。ここが食い違うと、その先はどう入れ替えても作れません。

ほかの選択肢はなぜ違うのか

• アA, D, B, C：最初の1文字を入れてすぐ取り出した後、4番目の文字を出すには残る2文字も積む必要があります。取り出した次に上にくるのは3番目の文字なので、2番目の文字を求める並びと食い違います。
• イB, D, A, C：2番目の文字を先に取り出した時点で、1番目の文字は下に残ります。4番目の文字を出すために3番目も積むことになり、その次に上にくるのは3番目なので、1番目を求める並びになりません。
• エD, C, A, B：4文字を全部積んでから上の2文字を取り出した形です。この時点で残る2文字は到着とは逆の並びで積まれており、上にくるのは2番目の文字なので、1番目を先に求める並びは作れません。