キュー

並んだ順に処理する

前回のスタックは、いちばん後に入れたものが先に出る入れ物でした。今回のキューはその逆で、先に入れたものが先に出ます。先入れ先出し (FIFO、First In First Out) と呼びます。レジの行列そのままで、先に並んだ人から順に呼ばれ、後から来た人は最後尾に付きます。

操作も2つです。enqueue は最後尾に1つ追加する操作、dequeue は先頭の1つを取り出して返す操作です。スタックと同じく dequeue も取り出す操作なので、実行すると中身が1つ減ります。

中身の書き方を先に決める

キューは入れる側と出る側が別なので、どちらの端が先頭かをはっきりさせないと必ず混乱します。このコースでは中身を {3, 1, 4} のように書き、左端を先頭 (次に出ていく側)、右端を最後尾 (次に入る側) とします。

  • {3, 1, 4} の状態で enqueue(5) を実行すると {3, 1, 4, 5} になります
  • 続けて dequeue() を実行すると 3 が返り、中身は {1, 4, 5} になります
  • 空のキューは {} と書きます

スタックでは右端から出ましたが、キューでは左端から出ます。この違いだけを押さえれば、あとの追い方は同じです。

キュー: q q.enqueue(3) q.enqueue(1) a ← q.dequeue() /* a に 3 が入り、q は {1} になる */

どこで使われているか

順番を守りたい処理はすべてキューです。印刷ジョブの待ち行列、OS が実行を待つプロセスを並べる待ち行列、Web サーバに届いたリクエストの受付など、先に来たものを先に片付けたい場面で使われます。

スタックとの違いが結果に効く例として、後の章で扱う探索があります。同じ地図をたどるのでも、次に見る場所をスタックに積むと深さ優先探索になり、キューに並べると幅優先探索になります。入れ物を変えるだけで探索の順番が変わる、というのはキューとスタックの性質の差そのものです。

試験での問われ方

科目Bでは、enqueue と dequeue が混ざった操作列を与えて、最後に取り出される値や、ある時点の中身を答えさせます。取り出した値をもう一度 enqueue で入れ直す問題もよく出ます。このとき、戻された値は先頭ではなく最後尾に付く点が引っ掛けになります。順番待ちの列にいったん抜けた人が戻れば、また最後尾に並び直すのと同じです。

リングバッファ (配列の端まで来たら先頭へ回り込む方式) で実装したキューの、先頭位置と末尾位置の変化を問う形も出ます。どちらの形でも、1操作ごとに中身を書き出せば確実に追えます。

次のトレースで、dequeue した値を加工して入れ直す動きを追ってみましょう。

課題

  1. 各行を実行したあとの値を入れる
  2. 値が変わらない変数はそのままの値を入れる
  3. キューの中身は {3, 1} の形で書き、左端を先頭とする

ヒント

1 / 8 行目のトレース

1○整数型: tameshi()
2 キュー: q
3 整数型: a, b
4 q.enqueue(3)
5 q.enqueue(1)
6 q.enqueue(4)
7 a ← q.dequeue()
8 q.enqueue(a + 10)
9 b ← q.dequeue()
10 return b
実行した行qab
実行前———
2 行目

2 行目を実行したあとの値を入れてください。変わらない変数は、 そのままの値を入れます。まだ値が入っていない変数は「—」と入れます。