基本情報技術者試験 基本情報技術者試験 平成29年度 秋期 午前 午前 問5: A, B, C, D の順に到着するデータに対して，一つのスタックだけを用いて出力可能なデータ列はどれか。

問題本文

A, B, C, D の順に到着するデータに対して，一つのスタックだけを用いて出力可能なデータ列はどれか。

選択肢

• ア.A, D, B, C
• イ.B, D, A, C
• ウ.C, B, D, A
• エ.D, C, A, B

正解

ウ. C, B, D, A

解説

スタックはLIFO。各データ到着時にpush/popを任意に挟める。Cを出すならA,B,Cまでpush→popでC、popでB、Dをpush→popでD、popでA → C,B,D,A 可能。

選択肢ごとの解説

• ア.A,D,B,Cは Aを出してから後でBより先にDを出すには A→push,pop, B,C,Dと積んで Dを出した時点でB,Cが下に。Bを次に出すには C先になる必要があり不可。
• イ.B,D,A,Cでは Bの後に Dを出した時点で残りはA,C(順A→C積み)、A出すならCを先に出す必要があり不可。
• ウ.C,B,D,A は前述の通り実現可能。
• エ.D,C,A,Bでは A,B,C,Dをすべて積んだ後 popで D,C,B,Aと出るしかなく A,Bの順序が逆。