基本情報技術者平成24年秋期 午前問5

午前問5

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

分類

テクノロジ系 » アルゴリズムとプログラミング » データ構造

正解

解説

「キュー」と「スタック」のデータ構造についておさらいしておきます。
キュー
先入れ先出しのデータ構造で、データを追加操作はenqueue(エンキュー)、データを取り出す操作はdequeue(デキュー)と呼ばれる。
スタック
後入れ先出しのデータ構造で、データを追加操作はpush(プッシュ)、データを取り出す操作はpop(ポップ)と呼ばれる。
キューのデータをD,C,B,Aに並べ替える手順は次のようになります。
  1. 初期状態
    05_1.gif/image-size:238×117
  2. キューからAを取り出しスタックに追加する。(deq_push)
    05_2.gif/image-size:238×117
  3. キューからBを取り出しスタックに追加する。(deq_push)
    05_3.gif/image-size:238×117
  4. キューからCを取り出しスタックに追加する。(deq_push)
    05_4.gif/image-size:238×117
    これでDがキュー構造の先頭に配置されました。
  5. スタックからCを取り出しキューに追加する。(pop_enq)
    05_5.gif/image-size:238×117
  6. スタックからBを取り出しキューに追加する。(pop_enq)
    05_6.gif/image-size:238×117
  7. スタックからAを取り出しキューに追加する。(pop_enq)
    05_7.gif/image-size:238×117
    並び替え完了
つまりdeq_pushの実行回数は最小で3回になります。
© 2010-2021 基本情報技術者試験ドットコム All Rights Reserved.

Pagetop