BohYoh.com《基本情報技術者試験》2014年度＝平成26年度・春期午前問7

基本情報技術者試験

2014年度＝平成26年度・春期

午前

問7

　空の状態のキューとスタックの二つのデータ構造がある。次の手続を順に実行した場合、変数x に代入されるデータはどれか。ここで、手続きで引用している関数は、次のとおりとする。

〔関数の定義〕
　push(y )：データy をスタックに積む。
　pop()：スタックからデータを取り出して、その値を返す。
　enq(y )：データy をキューに挿入する。
　deq()：キューからデータを取り出して、その値を返す。

〔手続〕
　　push(a)
　　push(b)
　　enq(pop())
　　enq(c)
　　push(d)
　　push(deq())
　　x ← pop()

ア　a

イ　b

ウ　c

エ　d

解答

イ

解説

　スタック（stack）は、データを後入れ先出し（LIFO = Last-In First-Out）で蓄えます。ちょうど、机の上に重ねた皿のように、最も上に重ねた皿を優先的に取り出すのと同様です。
　キュー（queue）は、データを先入れ先出し（FIFO = First-In First-Out）で蓄えます。ちょうど、銀行の待ち行列のように、より早く到着して待っているお客さんから、優先的に手続きが行われるのと同様です。

　まずａをプッシュします（左図はキュー、右図はスタックです）。　　　　　　　　　　　ａ　　　　　　　　　　　↓ 　　│　│　　　　　┐　┌ 　　├─┤　　　　　├─┤ 　　│　│　　　　　│　│ 　　├─┤　　　　　├─┤ 　　│　│　　　　　│　│ 　　├─┤　　　　　├─┤ 　　│　│　　　　　│　│ 　　├─┤　　　　　├─┤ 　　│　│　　　　　│ａ│ 　　└─┘　　　　　└─┘ 　続いてｂをプッシュします。　　　　　　　　　　　ｂ　　　　　　　　　　　↓ 　　│　│　　　　　┐　┌ 　　├─┤　　　　　├─┤ 　　│　│　　　　　│　│ 　　├─┤　　　　　├─┤ 　　│　│　　　　　│　│ 　　├─┤　　　　　├─┤ 　　│　│　　　　　│ｂ│ 　　├─┤　　　　　├─┤ 　　│　│　　　　　│ａ│ 　　└─┘　　　　　└─┘
　スタックから取り出したｂを、キューにエンキューします。　　　　←　　ｂ　← 　　　↓　　　　　　　↑ 　　│　│　　　　　┐　┌ 　　├─┤　　　　　├─┤ 　　│　│　　　　　│　│ 　　├─┤　　　　　├─┤ 　　│　│　　　　　│　│ 　　├─┤　　　　　├─┤ 　　│　│　　　　　│　│ 　　├─┤　　　　　├─┤ 　　│ｂ│　　　　　│ａ│ 　　└─┘　　　　　└─┘ 　キューにｃをエンキューします。　　　ｃ　　　↓ 　　│　│　　　　　┐　┌ 　　├─┤　　　　　├─┤ 　　│　│　　　　　│　│ 　　├─┤　　　　　├─┤ 　　│　│　　　　　│　│ 　　├─┤　　　　　├─┤ 　　│ｃ│　　　　　│　│ 　　├─┤　　　　　├─┤ 　　│ｂ│　　　　　│ａ│ 　　└─┘　　　　　└─┘ 　スタックにｄを、プッシュします。　　　　　　　　　　　ｄ　　　　　　　　　　　↓ 　　│　│　　　　　┐　┌ 　　├─┤　　　　　├─┤ 　　│　│　　　　　│　│ 　　├─┤　　　　　├─┤ 　　│　│　　　　　│　│ 　　├─┤　　　　　├─┤ 　　│ｃ│　　　　　│ｄ│ 　　├─┤　　　　　├─┤ 　　│ｂ│　　　　　│ａ│ 　　└─┘　　　　　└─┘ 　キューから取り出したｂを、スタックにプッシュします。　　　　　　　　　→　　　　　　　　　　　　　↓ 　　│　│　　↑　　┐　┌ 　　├─┤　　　　　├─┤ 　　│　│　　　　　│　│ 　　├─┤　　ｂ　　├─┤ 　　│　│　　　　　│ｂ│ 　　├─┤　　　　　├─┤ 　　│　│　　↑　　│ｄ│ 　　├─┤　　　　　├─┤ 　　│ｃ│　　　　　│ａ│ 　　└─┘　　　　　└─┘ 　　　↓　　　↑ 　　　　　→　　スタックからポップして得られる値はｂとなります。　　　　　　　　　　　ｂ　　　　　　　　　　　↑ 　　│　│　　　　　┐　┌ 　　├─┤　　　　　├─┤ 　　│　│　　　　　│　│ 　　├─┤　　　　　├─┤ 　　│　│　　　　　│　│ 　　├─┤　　　　　├─┤ 　　│　│　　　　　│ｄ│ 　　├─┤　　　　　├─┤ 　　│ｃ│　　　　　│ａ│ 　　└─┘　　　　　└─┘