待ち行列,キュー(queue)

アドバンスドプログラミングのTOPページに戻る

  1. 待ち行列(queue)とは
  2. 待ち行列をとりあえず簡単に構築する
  3. リングバッファ
  4. 待ち行列の構造体を作る
  5. レポート問題

待ち行列(queue)とは

待ち行列(キュー)も,逐次入出力が繰り返されるデータを一時的に貯えておくためのデータ構造である。なお,英語でキュー(queue)とは,レジなどで順番を待つ人の列も意味する。

queue

待ち行列にデータを追加することを enqueue と言い,待ち行列からデータを取り出すことを dequeue と言う。待ち行列へのデータの追加取り出しは次のように行われる。

queue

すなわち,待ち行列から一つデータを取り出すとき,それは(残っているデータの中で)最初に追加したものである。このような追加取り出しの方法を先入れ先出し法,First In First Out (FIFO) と呼ぶことがある。待ち行列を用いるのは「仕事は頼まれた順に古い方から片付けて行く」という方針で動くプログラムを作るときである。

 配列で上のような待ち行列を実現したとしよう。すると, dequeue を行ったときに,配列内のデータが一つずつ左にずれる必要がある。人間の場合には,各々の人が前に進めばいいのであるが,プログラムではプログラムが動かしてやる必要があり,これでは処理が遅くなる。

そこで,データをずらすのではなく,行列の先頭の位置をずらすことにする。 人間の行列に例えると,人間は動かずに,レジが動いて行くと考えるわけである。

queue

データの動きの様子は次のようになる。

queue
ページ先頭へ戻る

待ち行列をとりあえず簡単に構築する

 とりあえず,待ち行列の機能をなすものを構築してみる。

#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) の仕様
data_t 型の enq_data を引数にとり,それを待ち行列に追加し,戻り値として SUCCESS を返す。
ただし,待ち行列が満杯であるときには追加せずに,戻り値として FAILURE を返す。
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) の仕様
待ち行列が空でなければ、それからデータを一つ取り出し,その値を *deq_data に代入し、queue_num は1減じ, queue_head は1つ進めて、SUCCESS を戻り値として返す。ただし,待ち行列が空のときは,戻り値として FAILURE を返す他は、何もしない。
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 となる。

リングバッファ1
リングバッファ2

これにより,待ち行列のための配列が完全に満杯になるまで,データを貯えることができる。

 リングバッファを用いた待ち行列を扱えるように,関数を書き直す。

int enqueue(data_t enq_data) の仕様
enq_data を待ち行列 queue_data に追加し(queue_num を1つ増やし),戻り値 SUCCESS を返す。ただし,待ち行列が満杯であるときには,追加せず FAILURE を返す。
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) の仕様
待ち行列が空でなければ、それからデータを一つ取り出し,その値を *deq_data に代入し、queue_num は1減じ, queue_head は1つ進めて、SUCCESS を戻り値として返す。ただし,待ち行列が空のときは,戻り値として 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 [  .  .  .  .  .  .  .  .  .  .]

待ち行列の実用例
 待ち行列が実際に使われているものの一つに,キーボードバッファというものがある。キーボードから入力された文字は,その処理が追い付かない場合には,一時的に貯えておく必要があるが,その場所をキーボードバッファという。キーボードバッファのデータは,入力された順に古い方から処理されるべきである。したがって,それには待ち行列のデータ構造が適している。

ページ先頭へ戻る

レポート問題

Queue-1 (レベルA)
 待ち行列を初期化する関数 void queueInitialize(queue_t *que) と,待ち行列が空であるかどうかを判断する関数 int queueEmptyQ(queue_t *que) とを作れ。
ただし, queueEmptyQ は,待ち行列が空であるときに 1 を,空ではないときに 0 を返すものとする。

解答解説 期限後に公開
Queue-2 (レベルC)
 N 人の人がいて,それらは番号 0, 1, 2, ..., N-1 で表されているとする。この N 人の人間関係(知り合いかどうか)を表した配列 a[N][N] がある。ただし, i 番目の人と j 番目の人とが知り合いであるとき a[i][j] == a[j][i] == 1 であり,知り合いでないとき a[i][j] == a[j][i] == 0 である。

このとき, x 番目の人から,知り合いの知り合いの知り合い.... という繋がりで, y 番目の人まで辿り着くには,最小で何回の知り合いという関係が必要か,を返す関数 int acquaintDistance(int a[N][N], int x, int y) を作れ。なお,x 番目の人から y 番目の人に辿り着けない場合には,acquaintDistance は -1 を返すこととする。関数名の acquaint は知り合いにさせる, distance は距離という意味である。

ヒント:待ち行列を利用する。最初に x を待ち行列に入れ,後は,「待ち行列から一つ dequeue して,その人の知り合いを待ち行列に enqueue する」ということを繰り返す。ただし,一度 enqueue した人は二度と enqueue しないようにし, y を enqueue する時点あるいは enqueue する一がいなくなった時点で,終了する。x から各人までの知り合い距離を入れる配列も用意しておき,新しい人を enqueue する度に,その人までの距離をその配列に入れる。

解答解説 期限後に公開
ページ先頭へ戻る

アドバンスドプログラミングのTOPページに戻る

Valid HTML 4.01!