待ち行列（キュー）の操作列を追って次のDEQで出るデータを求める
基本情報技術者試験 平成30年度秋期 午前 問5 ／ アルゴリズムとプログラミング › データ構造
過去問にチャレンジ
待ち行列に対する操作を，次のとおり定義する。 ENQ n:待ち行列にデータnを挿入する。DEQ :待ち行列からデータを取り出す。 空の待ち行列に対し，ENQ1，ENQ2，ENQ3，DEQ，ENQ4，ENQ5，DEQ，ENQ6，DEQ，DEQの操作を行った。次にDEQ操作を行ったとき，取り出されるデータはどれか。
- ア
1
- イ
2
- ウ
5
- エ
6
会話形式の解説
講師今回は待ち行列（キュー）の問題です。ポイントは、待ち行列が先入れ先出し、つまりFIFOで動くことです。ENQでデータを入れ、DEQで取り出す操作が続くので、1つずつ順に追っていきましょう。
受験者操作が10個もあると、頭の中だけで追うと途中で混乱しそうです。私はこういう問題で時間がかかりがちです。
講師それなら、操作ごとに行列の中身を書き出すのが確実です。左を先頭として、角かっこで並べていきます。まずENQ1、ENQ2、ENQ3のあとはどうなりますか。
受験者[1,2,3]です。次のDEQでは、最初に入った1が先頭から出るので、[2,3]になります。
講師そのとおりです。続けてENQ4、ENQ5、DEQ、ENQ6まで進めてみてください。
受験者ENQ4とENQ5で[2,3,4,5]、DEQで先頭の2が出て[3,4,5]、ENQ6で末尾に6が加わって[3,4,5,6]です。
講師よくできています。残りはDEQが2回です。どのデータが出て、何が残りますか。
受験者先頭から3と4が順に出て、[5,6]が残ります。なので次のDEQでは先頭の5が取り出される、ということですね。
講師正解です。5と6のうち、5のほうが先に入っているので、FIFOでは5が先に出ます。ほかの選択肢も確かめておきましょう。1と2はどうでしょう。
受験者1は最初のDEQで、2は2回目のDEQで、もう取り出されています。操作列が終わった時点では行列に残っていないので、次のDEQで出ることはありません。
講師そうですね。では6はどうですか。
受験者6は最後に入ったので末尾にあります。前に5が並んでいるので、6が出るのはさらにその次のDEQです。
講師完璧です。関連して、後に入ったものから先に出る、後入れ先出し（LIFO）の構造をスタックといいます。待ち行列とは出る順が逆なので、同じ操作列でもスタックとして追うと出てくるデータの順が変わり、答えも違ってきます。問題文が待ち行列なのかスタックなのかを最初に確認する習慣をつけておくと安全です。
受験者まず構造の種類を確かめて、そのあと中身を1行ずつ書き出していけば、取り違えずに解けそうです。
まとめ
待ち行列（キュー）は先入れ先出し（FIFO）で動き、DEQのたびにその時点で最も早く入ったデータが先頭から出ていきます。この問題の操作列を順に追うと、行列の中身は[1,2,3]→[2,3]→[2,3,4,5]→[3,4,5]→[3,4,5,6]と変わり、最後の2回のDEQで3と4が出て[5,6]が残ります。したがって次のDEQで取り出されるのは5です。1と2はすでに取り出されており、6は5より後ろに並んでいるため答えになりません。後入れ先出し（LIFO）のスタックとは出る順が逆になるので、問題文がどちらの構造かを最初に確認することが大切です。
解答・解説
正解はウです
この問題のテーマ
待ち行列（キュー）が先入れ先出し（FIFO）で動くことを踏まえ、ENQとDEQの操作列を順に追って、次のDEQで取り出されるデータを求める問題です。
解き方の考え方
待ち行列では、DEQのたびにその時点で最も早く入ったデータが先頭から出ていきます。操作を1つずつ追い、行列の中身を書き出していくと確実です。ENQ1〜3の後は[1,2,3]で、DEQで1が出て[2,3]になります。ENQ4・ENQ5で[2,3,4,5]、DEQで2が出て[3,4,5]、ENQ6で[3,4,5,6]となり、続く2回のDEQで3と4が出て[5,6]が残ります。次のDEQでは先頭の5が取り出されるので、正解のウと一致します。
選択肢ごとの解説
- ×ア 1データ1は最初に挿入されたので、操作列の最初のDEQで取り出されています。そのため、操作列が終わった時点では行列に残っていません。次のDEQで1が出ることはありません。
- ×イ 2データ2は、1が出た後に先頭になり、2回目のDEQで取り出されています。操作列の終了時に残っているのは5と6だけなので、2は答えになりません。
- ○ウ 5操作列の後に残る5と6のうち、5は6より先に挿入されています。FIFOでは先に入ったものから出るので、次のDEQで取り出されるのは5です。
- ×エ 6データ6は最後に挿入されたので、行列の末尾にあります。6の前には5が並んでいるため、6が取り出されるのはさらにその次のDEQです。
補足
スタックだと考えて同じ操作列を追うと、出てくるデータの順がまったく変わってしまいます。問題文が「待ち行列」なのか「スタック」なのかを、最初に確認しておくと安全です。
POINT
- 待ち行列（キュー）は先入れ先出し（FIFO）で、DEQではその時点で最も早く入ったデータが出ます。
- 操作列の問題は、操作ごとに行列の中身を書き出すと取り違えを防げます。
- 最後に入ったものから出るのはスタック（LIFO）で、待ち行列とは逆の順になります。