問題プレビューID: df97ba1c

問 5

四つのデータ A, B, C, D がこの順に入っているキューと空のスタックがある。手続 pop_enq, deq_push を使ってキューの中のデータを D, C, B, A の順に並べ替えるとき，deq_push の実行回数は最小で何回か。ここで，pop_enq はスタックから取り出したデータをキューに入れる操作であり，deq_push はキューから取り出したデータをスタックに入れる操作である。

解説

キューは先頭から A, B, C, D の順に入っており，これを D, C, B, A の順に並べ替える。最小の手順は次のとおりである。

deq_push を 3 回実行し，A, B, C をキューから取り出してスタックに積む（スタックは下から A, B, C）。キューには D だけが残る。
pop_enq を 3 回実行し，スタックから C, B, A の順に取り出してキューに入れる。キューは D, C, B, A になる。

deq_push の実行回数は 3 回で，これが最小である。

したがって，正解は「イ」である。