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

基本情報技術者試験

2001年度＝平成13年度・秋期

午前

問13

　スタックとキューの二つのデータ構造がある。次の手続きを順に実行した場合、変数x に代入されるデータはどれか。ここで、
　データaをスタックに挿入することを、push(a)
　スタックからデータを取り出すことを、pop()
　データaをキューに挿入することを、enq(a)
　キューからデータを取り出すことを、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）で蓄えます。ちょうど、銀行の待ち行列のように、より早く到着して待っているお客さんから、優先的に手続きが行われるのと同様です。

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