後に入れたデータが先に取り出されるデータ構造（以下，スタックという）がある。これを用いて，図に示すような，右側から入力されたデータの順番を変化させて，左側に出力する装置を考える。この装置に対する操作は次の3通りである。 ①　右側から入力されたデータをそのまま左側に出力する。 ②　右側から入力されたデータをスタックの1番上に積み上げる。 ③　スタックの1番上にあるデータを取り出して左側に出力する。 この装置の右側から順番にデータA，B，C，Dを入力した場合に，この①～③の操作を組み合わせても，左側に出力できない順番はどれか。

選択肢

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

正解と解説

正解：エ C, D, A, B

スタックは後入れ先出しなので、積んだ順の逆でしか取り出せない。Cを最初に出すにはAとBを積む必要があり、スタック内はAが下、Bが上になる。この状態ではAより先にBが出るため、AをBより先に出す順番は作れない。

選択肢ごとの解説

• アAを積んでBを素通しし、Aを取り出す流れで実現できる。
• イA・Bを積み、Cを積んでからDを素通しし、C・B・Aと取り出せば実現できる。
• ウA・Bを積みCを素通し、次にBを取り出しDを素通ししてAを取り出せば実現できる。
• エ正しい。AとBはこの順で積まれるため、AをBより先に出すことはできない。

この問題に出た用語

• スタック

同じ分野の他の問題

• ディレクトリ又はファイルがノードに対応する木構造で表現できるファイルシステムがある。ルートディレクトリを根として図のよう…2022年度 秋期 問90
• 下から上へ品物を積み上げて、上にある品物から順に取り出す装置がある。この装置に対する操作は、次の二つに限られる。 PUS…2019年度 秋期 問62
• 複数のデータが格納されているスタックからのデータの取出し方として、適切なものはどれか。2018年度 秋期 問76
• 先入れ先出し（First-In First-Out, FIFO）処理を行うのに適したキューと呼ばれるデータ構造に対して“…2018年度 春期 問96
• 下から上へデータを積み上げ、上にあるデータから順に取り出すデータ構造（以下、スタックという）がある。これを用いて、図に示…2010年度 春期 問85