平成24年度 秋期 基本情報技術者試験 午前 問5
テクノロジ／アルゴリズム四つのデータA，B，C，Dがこの順に入っているキューと空のスタックがある。手続pop_enq，deq_pushを使ってキューの中のデータをD，C，B，Aの順に並べ替えるとき，deq_pushの実行回数は最小で何回か。ここで，pop_enqはスタックから取り出したデータをキューに入れる操作であり，deq_pushはキューから取り出したデータをスタックに入れる操作である。
出典：平成24年度 秋期 基本情報技術者試験 午前 問5
- ア2
- イ3
- ウ4
- エ5
正解：イ
解説
キューはD，C，B，Aの順に取り出せるように並べ替える必要があります。pop_enq（スタックから取り出してキューに入れる）とdeq_push（キューから取り出してスタックに入れる）を使い分けて，最小回数のdeq_pushで済む手順を考えます。A，B，Cをdeq_pushで順にスタックへ移してスタックの上をC，B，Aの順にし，その後pop_enqでキューへ戻すとキューはD，C，B，Aの順になります。deq_pushは3回で済みます。
選択肢ごとの解説
- ア誤り。2回のdeq_pushだけでは，スタックに積む要素が不足し，D，C，B，Aの順に並べ替えることができません。
- イ正しい。A，B，Cの3個をdeq_pushでスタックに移すとスタックの上からC，B，Aとなり，それをpop_enqでキューに戻すとD，C，B，Aの順に並びます。
- ウ誤り。3回で並べ替え可能なところを，不要な操作を挟むなどして4回としてしまった場合の回数です。
- エ誤り。全てのデータを一度スタックに移すなど，非効率な手順を想定した場合の回数です。