基本情報技術者試験 基本情報技術者試験 平成26年度 春期 午前 午前 問7: 空の状態のキューとスタックの二つのデータ構造がある。次の手続を順に実行した場合，変数 x に代入されるデータはどれか。ここで，手続で引用している関数は，次のとお

問題本文

空の状態のキューとスタックの二つのデータ構造がある。次の手続を順に実行した場合，変数 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

正解

イ. b

解説

スタックは後入先出(LIFO)、キューは先入先出(FIFO)で順を追って状態を更新します。最終的に pop で取り出すのは直前に push した値で、それは deq() で取り出した b です。

選択肢ごとの解説

• ア.a は最初にスタック底に積まれたまま最後まで取り出されません。
• イ.push(a),(b)後にスタック[a,b]→pop=b→enq(b),enq(c)でキュー[b,c]→push(d)でスタック[a,d]→deq=b→push(b)でスタック[a,d,b]→x=pop=b。
• ウ.c は enq(c) でキューに入った2番目の要素で、FIFO の取り出し順では b の後なので今回は取り出されません。
• エ.d は push(d) でスタックに積まれましたが、その後に push(b) が積まれたため pop の対象はその上の b になります。