2019年国家一般職(電気・電子・情報) No.39解説

　問題　　　　　

図Ⅰのように後から入れたデータを先に取り出す LIFO (Last In First Out) 構造のスタックと、図Ⅱのように先に入れたデータを先に取り出す FIFO (First In First Out) 構造のキューについて考える。

いま、図Ⅲの状態にあるスタックと図Ⅳの状態にあるキューを用意し、ある一連の操作を実行したところ、キューの状態が図Ⅴのようになった。次の㋐～㋓の操作のうち、このとき実行されたと考えられる操作のみを全て挙げているのはどれか。

1．㋐
2．㋐，㋓
3．㋑，㋒
4．㋑，㋓
5．㋒

正解 (4)

　解説　　　　　

enq(pop()) は
「スタックから取り出してキューに上からつっこむ」という意味と読み取れます。

enq(deq()) は
「キューの下から取り出して上からつっこむ」という意味と読み取れます。

㋐と㋑はこれで操作のイメージがつかめると思います。㋑の初めの 2 操作分のイメージが以下になります。

操作の続きを考えると、enq(pop()) → enq(deq()) をもう１セット操作すれば、スタックに B が 1 個だけ残っており、キューの方は上から ABABA となることがわかります。各自確認してみてください。

最後に enq(pop()) で、スタックから最後の B を取り出して、キューに上からつっこめば、BABABA となります。㋑が妥当です。正解は 3 or 4 です。

㋒、㋓については
push(deq()) が「キューからデータを取り出して、スタックに乗っける」です。㋒、㋓共に初めの 4 操作は共通です。初めの 2 操作分のイメージが以下になります。

操作の続きを考えると、enq(pop()) → push(deq()) と操作すれば、スタックに上から ABBB、キューに上から ABA となります。

この操作では、キューの完成図を下から完成させています。すると次はせっかく出来上がっている ABA のデータを崩してしまう deq() は誤りです。そのため、㋒は誤りです。㋓が妥当です。

ぜひ余裕があれば
各自㋓の続きの操作におけるデータの流れを確認してみてください。

以上より、正解は 4 です。

コメント