3 キュー

最初に入れたデータをはじめに取り出すキューと呼ばれるデータ構造について説明する．

3.1 イメージ

待ち行列と呼ばれるキュー(queue)も辞書で調べてみた．それには，次のような意味がある．

1. 順番を待つ人・車などの）列(line)；（待つ）一群の人々
2. 《コンピューター》待ち行列

これは，窓口に並ぶ順番待ちの行列の意味で，図4のようなデータ構造となっている． スタックではデータの挿入と取り出しが列の一方からのみであったの対して，キューは列 の両端から行う．一方がデータの追加で一方がデータの取り出しとして使われる．キュー では，最初に入れたデータが一番最初に取り出されることにある．取り出され るデータは格納されている最古のデータで，最初に入れられたものが最初に取り出され ることから，FIFO(first in first out, 先入れ先出し)と呼ばれる．スタック同様，スタッ クの途中のデータを取り出すことは許されないのである．

図 4: キュー

キューはスタックに比べて少しばかり，構造が複雑になっている．実際，それを直線的な イメージのメモリーにデータを追加しようとすると，以下のような問題が生じる．

• FIFOを続けると，いずれはメモリーの端に到達して，データの追加が出来なくな る．
• データを追加したり取り出したりする毎に，データの列を移動させることも考え られる．こうすると計算量が増加して不経済である．

これを防ぐために，図5のようなリングバッファと言うものが考えられた．

図 5: リングバッファー

3.2 実際の応用

これは，入れられた順序通りに処理すべきデータに使われる．たとえば，次のような応用 がある．

• データをバッファーにためて，処理を行う場合．プリンターの処理などである． プリント待ちのデータをプリントキューと言うことがある．
• オンライントランザクション処理²の管理に用いれれる．この処理では，原則的に は到着順に処理しなくてはならない．

3.3 キューの実装

配列を使えば，キューの実装も簡単である．教科書 [1]では，次のよう な構造体を宣言している．

	typedef struct queue{
	  int head;
	  int tail;
	  int size;
	  int data[1];
	}queue_t;

この構造体には，キューに必要な情報がすべてがある．図6に示 すようにメンバー変数headは，最新のデータを格納している配列の添え字を表して いる．tailはもっとも古いデータ--次に取り出すデータ--の次の配列の添え字を 表していいる．sizeはこのスタックに蓄えることができるデータ数を表している． それは，配列の要素数に1(番兵の分)を加えた値となっている．

図 6: 教科書 [1]のキューのイメージ．配列中の?はデータは あるが，意味のない--使い道のない--データを表している．

キューを実際に使うためには記憶領域が確保と操作を行う必要がある．教科書のqueue.c では，次の3つの関数でそれを行っている．記憶領域の確保を行うcreat_queue()と データを格納するenqueue()，データを取り出すdequeue()である．

ホームページ: Yamamoto's laboratory
著者: 山本昌志