next up previous contents
Next: 2. スタック Up: 26. キュー・スタック・バイナリーツリー Previous: 26. キュー・スタック・バイナリーツリー

1. キュー

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

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

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

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

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

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

ここで前回に学習した typedef を用いて、List 型を作っている。 キューに必要な関数はキューに追加する事と、キューから取り出す事 だけであるので実装はやさしい。

キューからデータを取り出す関数は最初の要素からデータを取り出し、 その要素をリストから取り除く。但し、もしキューにある要素がない 場合は 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){
    List *lp=First;
    if(lp!=NULL){
        while(lp->next!=NULL){
            lp=lp->next;
        }
        lp = lp->next = (List*)malloc(sizeof(Que));
    }else{
        lp = First=(List*)malloc(sizeof(List));
    }
    lp->data = data;
    lp->next = NULL:
    return;
}



Noriyo Kanayama 平成14年11月26日