正解は「ウ」です。
スタックは後入れ先出し(LIFO)の構造であり,データの到着順にプッシュし,任意のタイミングでポップして出力します。出力できる列は,スタックの性質上「3 番目に到着したものを最初に出力する」ような一部の並びに限られます。
「ウ」の C, B, D, A は次の手順で実現できます。
- A,B,C をこの順にプッシュする(スタックの上から C,B,A)。
- C をポップして出力,続いて B をポップして出力する(ここまでで C,B)。
- D をプッシュしてポップし出力する(ここまでで C,B,D)。
- 残った A をポップして出力する(C,B,D,A)。
- ア: A を出力した後に D を出力するには,先に B,C を処理する必要があり,D の次に B を出力できません。
- イ: B を出力した後に D を出力するには C をプッシュする必要があり,その後に A を出力できません。
- エ: D を出力した時点でスタックには A,B,C が残り,次に出力できるのは C だけなので C, A, B の順にはできません。