四つのデータA、B、C、Dがこの順に入っているキューと空のスタックがある。
手続pop_enq、deq_pushを使ってキューの中のデータをD、C、B、Aの順に並べ替えるとき、deq_pushの実行回数は最小で何回か。
ここで、op_enqはスタックから取り出したデータをキューに入れる操作であり、deq_pushはキューから取り出したデータをスタックに入れる操作である。
| ア | 2 | イ | 3 | ウ | 4 | エ | 5 |
答え イ
【解説】
問題は下図のようにキューの順番をスタックを使って入れ替えることである。
- 最初のキューとスタックの状態は
- 1回目手続pop_enqを行うと、キューから“A”を取り出し、スタックに入れ
- 2回目手続pop_enqを行うと、キューから“B”を取り出し、スタックに入れ
- 3回目手続pop_enqを行うと、キューから“C”を取り出し、スタックに入れ
- 1回目手続deq_pushを行うと、スタックから“C”を取り出し、キューに入れ
- 2回目手続deq_pushを行うと、スタックから“B”を取り出し、キューに入れ
- 3回目手続deq_pushを行うと、スタックから“A”を取り出し、キューに入れ
【キーワード】
・キュー
・スタック
- キュー
一時的なデータの格納領域で、格納したのと同じ順でデータを取り出すことができます。
(First-In First-Out、FIFO) - スタック
一時的なデータの格納領域で、格納したのと逆の順でデータを取り出すことができます。
(Last-In First-Out、LIFO)
もっと、「キュー」について調べてみよう。
戻る
一覧へ
次へ