ALDS1_3_B:

キュー

ラウンドロビンスケジューリングは、プロセスを格納（管理）するキューを用いてシミュレートすることができます。まず、初期状態のプロセスを順番にキューに入れます。次にキューが空になるまで、「先頭からプロセスを取り出し、最大でもクオンタムだけ処理を行い、まだ必要な処理（時間）が残っている場合は再度キューに追加する」処理を繰り返します。

ここでは、整数型のデータが格納されるキューを配列を用いて実装する方法を紹介します。

キューの操作と制約

• enqueue(x): キューの末尾に要素 x を追加します。
• dequeue( ): キューの先頭から要素を取り出します。
• isEmpty( ): キューが空かどうかを調べます。
• isFull( ): キューが満杯かどうかを調べます。
  ※実用的なキューには、これらの他にもキューの先頭の要素を参照したり、キューに指定されたデータが含まれているかを調べたりする操作も含まれます。

データの中でより最も早く入ったものが最初に取り出されます。dequeue では追加された順番に要素が取り出されます。enqueue されてからの時間が最も長い要素から順番に取り出されます。

キューの実装

配列を用いたキューの実装に必要な主な変数と関数は以下のとおりです。

データを格納するための整数型 1 次元配列 : Q
配列 Q の各要素に enqueue されたデータを格納していきます。問題に応じた十分な記憶領域を確保することが必要です。上図では、既にいくつかの要素が格納されています。

先頭ポインタである整数型変数：head
キューの先頭の場所を指し示す変数です。dequeue されると head で指されている要素が取り出されます。キューの先頭の要素のインデックスが常に 0 とは限らないことに注意してください。

末尾ポインタである整数型変数：tail
キューの末尾＋ 1 の場所（最後の要素の隣）を指し示す変数です。tail は新しい要素が追加される場所を示します。head と tail で挟まれた部分（tail が指す要素は含まない）が、キューの中身を表します。

キューに要素 x を追加する関数 enqueue(x)
Q[tail] に x を代入し、tail を１つ増やします。

キューの先頭から要素を取り出す関数 dequeue( )
Q[head] の値を返し、head を１つ増やします。

実際にキューのデータ構造を操作する様子を見てみましょう。次の図は、キューに適当な値を適当に出し入れしている様子を表しています。

head と tail が一致しているとき、キューが空の状態となります。このとき、これらは 0 とは限りません。enqueue(x) が実行されると、新しい要素は tail の位置に追加され tail が１つ増えます。dequeue() では head が指す要素が返され、head が１つ増えます。

配列によってキューを実装すると、上図に示すように、データの追加と取り出し操作を繰り返すことによって、head と tail に挟まれたキューのデータ本体が配列の末尾に向かって（図の右側に）移動していきます。このままでは、tail と head が配列の容量をすぐに超えてしまいます。tail が配列の領域を超えた時点でオーバーフローとして追加を諦めてしまっては、まだ使える配列の領域を無駄にしてしまいます。しかし、それを防ぐために dequeue() が実行されたときに head を常に 0 に保つようにデータ全体を配列の先頭に（左に）向かって移動していては、その度にO(n)の計算が必要になってしまいます。

この問題を解決するために、配列によるキューの実装では次のように、配列をリングバッファとみなしてデータを管理することがあります。

リングバッファは1 次元配列で実現され、キューの範囲を指し示す head、tail が配列の領域を超えてしまったときにこれらのポインタを循環させます。つまり、ポインタを1つ増やして、それが配列の範囲を超えてしまった場合には、ポインタを 0 にリセットします。

上の図は既にいくつかのデータが格納されたキューにデータを出し入れしている様子を示しています。最初に enqueue(1) によって 1 を追加したときに、tail の値が1 つ増えますが、既に tailが 7 であったため配列の領域を超えてしまうので tail を 0 に設定します。リングバッファを時計回りに見ると、キューにデータがある場合はポインタが head → tail の順番に並びます。また、キューが空のときと満杯のときを区別するために tail &raar; head の間には常に１つ以上の空きを設けます。

配列を用いたキューは次のように実装することができます。

1  initialize()
2    head = tail = 0
3
4  isEmpty()
5    return head == tail
6
7  isFull()
8    return head == (tail + 1) % MAX
9
10 enqueue(x)
11   if isFull()
12     エラー（オーバーフロー）
13   Q[tail] = x
14   if tail + 1 == MAX
15     tail = 0
16   else
17     tail++
18 
19
20 dequeue()
21   if isEmpty()
22     エラー（アンダーフロー）
23   x = Q[head]
24   if head + 1 == MAX
25     head = 0
26   else
27     head++
28   return x

initialize関数では、head と tail を同じ値に設定することで、キューを空に設定し、isEmpty 関数では、head とtail が同じ値かを調べて、キューが空かどうかを判定します。

isFull 関数では、キューが満杯かどうかを調べます。例えば、配列が 0 オリジンで容量が MAX で定義されていれば、head が (tail+1)%MAX に等しいとき、キューが満杯と判定されます。ここで a%b は a を b で割った余りを示します。

enqueue関数は、tail が指す場所に x を追加します。要素が 1 つ増えたので tail を1 増やします。ただし、配列の容量である MAX 以上になってしまう場合は tail を 0として循環させます。また、キューが満杯の場合はなんらかのエラー処理を行います。

dequeue関数は、head が指すキューの先頭の要素を変数 x に一時的に記録し、head を1 増やしてから x の値を返します。ただし、head を増やした値が MAX 以上になってしまう場合は head を0として循環させます。また、キューが空の場合はなんらかのエラー処理を行います。

配列によるキューの実装では、メモリを有効に活用しつつ、enqueue と dequeue の操作をそれぞれ$O(1)$ のアルゴリズムで行うことがポイントになります。リングバッファを用いれば、enqueue、dequeue ともに $O(1)$ のアルゴリズムで実装することができます。

Reference

---