23.2 キュー

キューは入出力機構の実装に良く用いられるメカニズムで、スーパー のレジに並ぶ買物客を想像すれば良い。この場合、最初に並んだ人から順に 処理され、新しい人は列の最後に並ばなければならない。最後に並んだ人が 最後に処理され出て行くので、Last In Last Out (LILO)とも呼ばれる。 ここでは買物客を例にしたが、買物客の代わりにキーボードから入力された キーデータを考えれば、キーボードバッファの仕組みになるし、通信の際に 出て行くデータの列だと考えれば、通信用の出力バッファの仕組みにもなる。 (こうしたメカニズムが必要なのは多くの場合、キューに入る動作と キューから出ていく動作が同期していないような場合である。そのような とき、キューはデータを管理するのに非常に便利な性質を持っている。 )

このようにキューは非常に自然なメカニズムであるが、その実現はリストを 理解していれば簡単である。勿論、キュー自体は配列などを利用しても実現 出来るが、その場合には、どれが最初のデータで、どれが最後かを自分で 管理する必要があり、かえって面倒でさえある。しかし、場合によっては、 配列で実装しなければならない場合もあるので、リストでないと出来ない という訳では無いことを知っておく必要はある。ここでは、単純にリスト を使って実現する方法を考えよう。

図: キュー
\begin{figure}\begin{center} \epsfile{file=que}\end{center}\end{figure}

まずデータが入ってくる場合であるが、入ってくるデータは全てリストの 最後に付け加える事にしよう。つまり、キューからデータを取り出す場合 には必ず、リストの先頭から取り出すようにする訳である。

まず、ヘッダーは次のようにする。 

/* header of QUE */
    typedef struct Que {
        struct Que *next;
        void *data;
    } QUE;
    static QUE *First;

ここで typedef を用いて、QUE 型を作っているが、前の章での リストの実現方法と少し異なる点がある。それは、リストの最初の 要素の場所をどうやって保持するかという点であり、この例では 最初からモジュール内部に First という静的外部変数を用意して いる。静的外部変数であるために、モジュールの外から参照する ことはできない(15章を参照)が、モジュール内部ではグローバル な変数として扱える。このために、取り扱いは楽であるが、代わりに 複数のキューを持つことがこのままでは難しい。

キューに必要な関数はキューに追加する事と、キューから取り出す事 だけであるので実装はやさしい。

キューからデータを取り出す関数は最初の要素からデータを取り出し、 その要素をリストから取り除く。但し、もしキューにある要素がない 場合は NULL を返す。 

void *get_que(void){
    QUE *lp = First;
    void *data;
    if(lp==NULL){    /* データがキューにない */
    	return NULL;
    }
    data = lp->data;
    lp = lp->next;
    free(First);
    First=lp;
    return data;
}

次に、キューに一個新たにデータを追加する関数では、リストの最後にデータを 作って追加する、キューにデータがない場合にのみ、Firstを更新する。 

void add_que(void *data){
    QUE *lp=First;
    if(lp!=NULL){
        while(lp->next!=NULL){
            lp=lp->next;
        }
        lp = lp->next = (QUE*)malloc(sizeof(QUE));
    }else{
        lp = First=(QUE*)malloc(sizeof(QUE));
    }
    lp->data = data;
    lp->next = NULL:
    return;
}


最初のページ 戻る 次へ 最後のページ 目次
Hiroyasu Asami