待ち行列(キュー)も,逐次入出力が繰り返されるデータを一時的に貯えておくためのデータ構造である。なお,英語でキュー(queue)とは,レジなどで順番を待つ人の列も意味する。
待ち行列にデータを追加することを enqueue と言い,待ち行列からデータを取り出すことを dequeue と言う。待ち行列へのデータの追加取り出しは次のように行われる。
すなわち,待ち行列から一つデータを取り出すとき,それは(残っているデータの中で)最初に追加したものである。このような追加取り出しの方法を先入れ先出し法,First In First Out (FIFO) と呼ぶことがある。待ち行列を用いるのは「仕事は頼まれた順に古い方から片付けて行く」という方針で動くプログラムを作るときである。
配列で上のような待ち行列を実現したとしよう。すると, dequeue を行ったときに,配列内のデータが一つずつ左にずれる必要がある。人間の場合には,各々の人が前に進めばいいのであるが,プログラムではプログラムが動かしてやる必要があり,これでは処理が遅くなる。
そこで,データをずらすのではなく,行列の先頭の位置をずらすことにする。 人間の行列に例えると,人間は動かずに,レジが動いて行くと考えるわけである。
データの動きの様子は次のようになる。
とりあえず,待ち行列の機能をなすものを構築してみる。
#define QUEUE_SIZE 10 /* 待ち行列に入るデータの最大数 */ typedef int data_t; /* データ型 */ data_t queue_data[QUEUE_SIZE]; /* 待ち行列データ本体 */ int queue_head; /* データ先頭 */ int queue_num; /* データ個数 */
QUEUE_SIZE は待ち行列本体である配列の要素数であり,これが待ち行列に収納できるデータの最大数となる。
data_t は待ち行列に入れるデータの型である。
スタックでは,データの追加および取り出しが,データの末尾でのみ行われたから,データの先頭の位置は変化することがなかった。しかし,待ち行列においては,データの追加はデータ末尾で,取り出しはデータ先頭で行われるから,先頭の位置が変化する。そこで, queue_head という先頭位置を表すための変数も必要となる。データ末尾の位置は queue_head + queue_num で得られるから、データ末尾の位置を表すための変数は必要ない。
queue_head と queue_head + queue_num とが指す場所は、次図のようになる。
この図を見ると、つぎのことがわかる。
このことをふまえて,待ち行列を操作する関数を作ってみる。
始めに,関数が返す値の定数を定義する。
#define SUCCESS 1 /* 成功 */ #define FAILURE 0 /* 失敗 */
一つ目の関数は,待ち行列へデータを追加する関数 enqueue である。
int enqueue(data_t enq_data) { if (queue_head + queue_num < QUEUE_SIZE) { queue_data[queue_head + queue_num] = enq_data; queue_num ++; return SUCCESS; } else { return FAILURE; } }
新しいデータをqueue_data[queue_head + queue_num] に保存した後, queue_num を一つ増やしている。
次は待ち行列の先頭のデータを取り出す関数 dequeue である。
int dequeue(data_t *deq_data) { if (queue_num > 0) { *deq_data = queue_data[queue_head]; queue_num --; queue_head ++; return SUCCESS; } else { return FAILURE; } }
取り出すべきデータは queue_data[queue_head] であるが,それを取り出した後は, queue_head の値を一つ増やす必要がある。
以上の enqueue と dequeue という関数で待ち行列の機能を作ることができるが,現実には,これではすぐに待ち行列が満杯になってしまい,機能不全に陥る。
前述の,待ち行列がすぐに満杯になる問題を解決するには,データを取り出す度に配列 queue_data の先頭部分に空きができるから,この部分を再利用すれば良いことに気付く。これを効果的に行ったデータ構造が,次に述べるリングバッファである。
前節の queue_data という配列の最後尾を配列の先頭にくっつけることにより,配列が環状になったと考える。すなわち,queue_data[QUEUE_SIZE-1] の次の要素は queue_data[0] と考えるわけである。これにより,配列の先頭部分にできる空きを再利用することが可能になる。
配列を環状に扱うためには,剰余演算子 % を活用して,添字を巡回的に動かせば良い(巡回的な添字を参照)。
たとえば,添字 i を k 個だけ後ろや前ににずらすには,次のようにすればよい。
i = (i + k) % QUEUE_SIZE; /* 後ろに k だけずらす */ i = (i - k + QUEUE_SIZE) % QUEUE_SIZE /* 前に k だけずらす */
また,次にデータを入れる要素の添字は,(queue_head + queue_num)%QUEUE_SIZE となる。
これにより,待ち行列のための配列が完全に満杯になるまで,データを貯えることができる。
リングバッファを用いた待ち行列を扱えるように,関数を書き直す。
int enqueue(data_t enq_data) { if (queue_num < QUEUE_SIZE) { queue_data[(queue_head + queue_num) % QUEUE_SIZE] = enq_data; queue_num ++; return SUCCESS; } else { return FAILURE; } }
int dequeue(data_t *deq_data) { if (queue_num > 0) { *deq_data = queue_data[queue_head]; queue_head = (queue_head + 1) % QUEUE_SIZE; queue_num --; return SUCCESS; } else { return FAILURE; } }
剰余演算子 % を用いて巡回的な添字を使用している。
待ち行列の動きを見るために,内容を表示する関数を作っておく。
void queuePrint() { int i; printf("queue ["); for (i = 0; i < QUEUE_SIZE; i++) { if ((queue_head + queue_num <= QUEUE_SIZE && queue_head <= i && i < queue_head + queue_num) ||(queue_head + queue_num > QUEUE_SIZE && (queue_head <= i || i < (queue_head + queue_num)%QUEUE_SIZE))) { printf("%3d", queue_data[i]); } else { printf("%3c", '.'); /* queue に入っていないデータは表示しない */ } } printf("]\n"); }
以上で構築した待ち行列を,次のような main 関数で動かしてみる。
main() { int i; data_t d; queue_head = queue_num = 0; /* queue を使用する前に,必ずこれらの変数を初期化 */ for (i = 1; i <= 7; i++) { printf("Enqueue%3d :", i); enqueue(i); queuePrint(); } for (i = 1; i <= 4; i++) { dequeue(&d); printf("Dequeue%3d :", d); queuePrint(); } for (i = 8; i <= 15; i++) { printf("Enqueue%3d :", i); if (enqueue(i) == SUCCESS) queuePrint(); else printf("Full queue\n"); } while(queue_num > 0) { dequeue(&d); printf("Dequeue%3d :", d); queuePrint(); } }
Enqueue 1 :queue [ 1 . . . . . . . . .] Enqueue 2 :queue [ 1 2 . . . . . . . .] Enqueue 3 :queue [ 1 2 3 . . . . . . .] Enqueue 4 :queue [ 1 2 3 4 . . . . . .] Enqueue 5 :queue [ 1 2 3 4 5 . . . . .] Enqueue 6 :queue [ 1 2 3 4 5 6 . . . .] Enqueue 7 :queue [ 1 2 3 4 5 6 7 . . .] Dequeue 1 :queue [ . 2 3 4 5 6 7 . . .] Dequeue 2 :queue [ . . 3 4 5 6 7 . . .] Dequeue 3 :queue [ . . . 4 5 6 7 . . .] Dequeue 4 :queue [ . . . . 5 6 7 . . .] Enqueue 8 :queue [ . . . . 5 6 7 8 . .] Enqueue 9 :queue [ . . . . 5 6 7 8 9 .] Enqueue 10 :queue [ . . . . 5 6 7 8 9 10] Enqueue 11 :queue [ 11 . . . 5 6 7 8 9 10] Enqueue 12 :queue [ 11 12 . . 5 6 7 8 9 10] Enqueue 13 :queue [ 11 12 13 . 5 6 7 8 9 10] Enqueue 14 :queue [ 11 12 13 14 5 6 7 8 9 10] Enqueue 15 :Full queue Dequeue 5 :queue [ 11 12 13 14 . 6 7 8 9 10] Dequeue 6 :queue [ 11 12 13 14 . . 7 8 9 10] Dequeue 7 :queue [ 11 12 13 14 . . . 8 9 10] Dequeue 8 :queue [ 11 12 13 14 . . . . 9 10] Dequeue 9 :queue [ 11 12 13 14 . . . . . 10] Dequeue 10 :queue [ 11 12 13 14 . . . . . .] Dequeue 11 :queue [ . 12 13 14 . . . . . .] Dequeue 12 :queue [ . . 13 14 . . . . . .] Dequeue 13 :queue [ . . . 14 . . . . . .] Dequeue 14 :queue [ . . . . . . . . . .]
1 から 7 までの整数を待ち行列に追加した後で,4個のデータを取り出し,さらに 8 から 15 までの整数を追加しているが,最後のデータ 15 は待ち行列が満杯であるため,追加できていない。そして,待ち行列が空になるまで,データを取り出して終了している。この最後の部分は、次のようにも書き換えることができる。
while(dequeue(&d) == SUCCESS) { printf("Dequeue%3d :", d); queuePrint(); }
前節で構築した待ち行列を構成する変数 queue_head, queue_num, queue_data をまとめて,構造体 queue として定義し直し,関数群も queue 型を指すポインタを引数にとるように変更してみる。
#define QUEUE_SIZE 10 /* 最大データ数 */ #define SUCCESS 1 /* 成功 */ #define FAILURE 0 /* 失敗 */ typedef int data_t; /* データ型 */ typedef struct { int head; int num; data_t data[QUEUE_SIZE]; } queue_t;
以上が,定数と型の定義である。待ち行列構造体 queue_t は,head と num という制御のためのメンバと,待ち行列本体である配列メンバ data とをもつ。
次の二つは,データ追加とデータ取り出しを行う関数である。
int enqueue(queue_t *que, data_t enq_data) { if (que->num < QUEUE_SIZE) { que->data[(que->head + que->num) % QUEUE_SIZE] = enq_data; que->num ++; return SUCCESS; } else { return FAILURE; } }
int dequeue(queue_t *que, data_t *deq_data) { data_t d; if (que->num > 0) { *deq_data = que->data[que->head]; que->head = (que->head + 1) % QUEUE_SIZE; que->num --; return SUCCESS; } else { return FAILURE; } }
次の関数は,待ち行列の内容を表示する関数である。data[i] にデータが入っているかどうかの判断を行うのに,排他的和演算子 ^ を用いている。
void queuePrint(queue_t *que) { int i; printf("queue ["); for (i = 0; i < QUEUE_SIZE; i++) { if (que->num > 0 && ((que->head < (que->head + que->num) % QUEUE_SIZE) ^ (que->head <= i) ^ (i < (que->head + que->num) % QUEUE_SIZE))) { printf("%3d", que->data[i]); } else { printf("%3c", '.'); } } printf("]\n"); }
待ち行列構造体と関数の使用例をあげる。
main(void) { int i; data_t d; queue_t que; que.num = que.head = 0; for (i = 1; i <= 7; i++) { printf("Enqueue%3d :", i); if (enqueue(&que, i)) queuePrint(&que); else printf("Full queue\n"); } for (i = 1; i <= 4; i++) { dequeue(&que, &d); printf("Dequeue%3d :", d); queuePrint(&que); } for (i = 8; i <= 15; i++) { printf("Enqueue%3d :", i); if (enqueue(&que, i)) queuePrint(&que); else printf("Full queue\n"); } while(que.num > 0) { dequeue(&que, &d); printf("Dequeue%3d :", d); queuePrint(&que); } }
Enqueue 1 :queue [ 1 . . . . . . . . .] Enqueue 2 :queue [ 1 2 . . . . . . . .] Enqueue 3 :queue [ 1 2 3 . . . . . . .] Enqueue 4 :queue [ 1 2 3 4 . . . . . .] Enqueue 5 :queue [ 1 2 3 4 5 . . . . .] Enqueue 6 :queue [ 1 2 3 4 5 6 . . . .] Enqueue 7 :queue [ 1 2 3 4 5 6 7 . . .] Dequeue 1 :queue [ . 2 3 4 5 6 7 . . .] Dequeue 2 :queue [ . . 3 4 5 6 7 . . .] Dequeue 3 :queue [ . . . 4 5 6 7 . . .] Dequeue 4 :queue [ . . . . 5 6 7 . . .] Enqueue 8 :queue [ . . . . 5 6 7 8 . .] Enqueue 9 :queue [ . . . . 5 6 7 8 9 .] Enqueue 10 :queue [ . . . . 5 6 7 8 9 10] Enqueue 11 :queue [ 11 . . . 5 6 7 8 9 10] Enqueue 12 :queue [ 11 12 . . 5 6 7 8 9 10] Enqueue 13 :queue [ 11 12 13 . 5 6 7 8 9 10] Enqueue 14 :queue [ 11 12 13 14 5 6 7 8 9 10] Enqueue 15 :Full queue Dequeue 5 :queue [ 11 12 13 14 . 6 7 8 9 10] Dequeue 6 :queue [ 11 12 13 14 . . 7 8 9 10] Dequeue 7 :queue [ 11 12 13 14 . . . 8 9 10] Dequeue 8 :queue [ 11 12 13 14 . . . . 9 10] Dequeue 9 :queue [ 11 12 13 14 . . . . . 10] Dequeue 10 :queue [ 11 12 13 14 . . . . . .] Dequeue 11 :queue [ . 12 13 14 . . . . . .] Dequeue 12 :queue [ . . 13 14 . . . . . .] Dequeue 13 :queue [ . . . 14 . . . . . .] Dequeue 14 :queue [ . . . . . . . . . .]
待ち行列の実用例
待ち行列が実際に使われているものの一つに,キーボードバッファというものがある。キーボードから入力された文字は,その処理が追い付かない場合には,一時的に貯えておく必要があるが,その場所をキーボードバッファという。キーボードバッファのデータは,入力された順に古い方から処理されるべきである。したがって,それには待ち行列のデータ構造が適している。