平成24年秋期試験午前問題 問5

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

  • 2
  • 3
  • 4
  • 5
正解 問題へ
分野:テクノロジ系
中分類:アルゴリズムとプログラミング
小分類:データ構造
「キュー」と「スタック」のデータ構造についておさらいしておきます。
キュー
先入れ先出しのデータ構造で、データを追加操作はenqueue(エンキュー)、データを取り出す操作はdequeue(デキュー)と呼ばれる。
スタック
後入れ先出しのデータ構造で、データを追加操作はpush(プッシュ)、データを取り出す操作はpop(ポップ)と呼ばれる。
キューのデータをD,C,B,Aに並べ替える手順は次のようになります。
  1. 初期状態
    05_1.gif
  2. キューからAを取り出しスタックに追加する。(deq_push)
    05_2.gif
  3. キューからBを取り出しスタックに追加する。(deq_push)
    05_3.gif
  4. キューからCを取り出しスタックに追加する。(deq_push)
    05_4.gif
    これでDがキュー構造の先頭に配置されました。
  5. スタックからCを取り出しキューに追加する。(pop_enq)
    05_5.gif
  6. スタックからBを取り出しキューに追加する。(pop_enq)
    05_6.gif
  7. スタックからAを取り出しキューに追加する。(pop_enq)
    05_7.gif
    並び替え完了
つまりdeq_pushの実行回数は最小で3回になります。

Pagetop