アルゴリズムとプログラミング
平成24年度 秋期 基本情報技術者試験 午前 問5
四つのデータ A，B，C，D がこの順に入っているキューと空のスタックがある。手続 pop_enq，deq_push を使ってキューの中のデータを D，C，B，A の順に並べ替えるとき，deq_push の実行回数は最小で何回か。ここで，pop_enq はスタックから取り出したデータをキューに入れる操作であり，deq_push はキューから取り出したデータをスタックに入れる操作である。
- ア 2
- イ 3
- ウ 4
- エ 5
出典：平成24年度 秋期 基本情報技術者試験 午前 問5
答えと解説を見る
正解：イ
覚える知識
キューとスタックによる並べ替え操作回数
キューは先入れ先出し、スタックは後入れ先出しで、両者の組合せでデータの順序を入れ替えられる。
この問題で必要なこと
FIFOのキューとLIFOのスタックを組み合わせて順序を反転させる操作を追い、deq_pushの最小回数を求める。
ひっかけ
全データをスタックに積めば足りると考えて回数を数え誤らせる。
この知識の出題：本試験系 1 回・免除試験 0 回（公開問題での観測値）