BohYoh.com《基本情報技術者試験》2010年度＝平成22年度・秋期午前問5

基本情報技術者試験

2010年度＝平成22年度・秋期

午前

問5

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

ア　A、D、B、C

イ　B、D、A、C

ウ　C、B、D、A

エ　D、C、A、B

解答

ウ

解説

　スタック（stack）は、データをLIFO（Last-In First-Out）で蓄えます。ちょうど、机の上に重ねた皿のように、最も上に重ねた皿を優先的に取り出すのと同様です。
　データを入れる操作をプッシュ（push）、データを取り出す操作をポップ（pop）といいます。

ア　A、D、B、C
　プッシュ、ポップは、次のようになります。

push Ａ　pop Ａ push Ｂ push Ｃ push Ｄ　pop Ｄ　pop Ｃ　pop Ｂ　┐　┌　┐　┌　┐　┌　┐　┌　┐　┌　┐　┌　┐　┌　┐　┌ 　│　│　│　│　│　│　│　│　│　│　│　│　│　│　│　│ 　│　│　│　│　│　│　│　│　│Ｄ│　│　│　│　│　│　│ 　│　│　│　│　│　│　│Ｃ│　│Ｃ│　│Ｃ│　│　│　│　│ 　│Ａ│　│　│　│Ｂ│　│Ｂ│　│Ｂ│　│Ｂ│　│Ｂ│　│　│ 　└─┘　└─┘　└─┘　└─┘　└─┘　└─┘　└─┘　└─┘

　Dを取り出した後は、C、Bと取り出されることになりますので、A、D、C、Bでなければなりません。

イ　B、D、A、C
　プッシュ、ポップは、次のようになります。

push Ａ push Ｂ　pop Ｂ push Ｃ push Ｄ　pop Ｄ　pop Ｃ　pop Ａ　┐　┌　┐　┌　┐　┌　┐　┌　┐　┌　┐　┌　┐　┌　┐　┌ 　│　│　│　│　│　│　│　│　│　│　│　│　│　│　│　│ 　│　│　│　│　│　│　│　│　│Ｄ│　│　│　│　│　│　│ 　│　│　│Ｂ│　│　│　│Ｃ│　│Ｃ│　│Ｃ│　│　│　│　│ 　│Ａ│　│Ａ│　│Ａ│　│Ａ│　│Ａ│　│Ａ│　│Ａ│　│　│ 　└─┘　└─┘　└─┘　└─┘　└─┘　└─┘　└─┘　└─┘

　Dを取り出した後は、C、Aと取り出されることになりますので、B、D、C、Aでなければなりません。

ウ　C、B、D、A
　プッシュ、ポップは、次のようになります。

push Ａ push Ｂ push Ｃ　pop Ｃ　pop Ｂ push Ｄ　pop Ｄ　pop Ａ　┐　┌　┐　┌　┐　┌　┐　┌　┐　┌　┐　┌　┐　┌　┐　┌ 　│　│　│　│　│　│　│　│　│　│　│　│　│　│　│　│ 　│　│　│　│　│Ｃ│　│　│　│　│　│　│　│　│　│　│ 　│　│　│Ｂ│　│Ｂ│　│Ｂ│　│　│　│Ｄ│　│　│　│　│ 　│Ａ│　│Ａ│　│Ａ│　│Ａ│　│Ａ│　│Ａ│　│Ａ│　│　│ 　└─┘　└─┘　└─┘　└─┘　└─┘　└─┘　└─┘　└─┘

　正解です。

エ　D、C、A、B
　プッシュ、ポップは、次のようになります。

push Ａ push Ｂ push Ｃ push Ｄ　pop Ｄ　pop Ｃ　pop Ｂ　pop Ａ　┐　┌　┐　┌　┐　┌　┐　┌　┐　┌　┐　┌　┐　┌　┐　┌ 　│　│　│　│　│　│　│Ｄ│　│　│　│　│　│　│　│　│ 　│　│　│　│　│Ｃ│　│Ｃ│　│Ｃ│　│　│　│　│　│　│ 　│　│　│Ｂ│　│Ｂ│　│Ｂ│　│Ｂ│　│Ｂ│　│　│　│　│ 　│Ａ│　│Ａ│　│Ａ│　│Ａ│　│Ａ│　│Ａ│　│Ａ│　│　│ 　└─┘　└─┘　└─┘　└─┘　└─┘　└─┘　└─┘　└─┘

　Cを取り出した後は、B、Aと取り出されることになりますので、D、C、B、Aでなければなりません。