3 キュー

3.1 イメージ

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

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

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

**図 3:** キュー
$\includegraphics[keepaspectratio,scale=0.9]{figure/queue.eps}$

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

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

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

**図 4:** リングバッファー
$\includegraphics[keepaspectratio,scale=1.0]{figure/ring_buffer.eps}$

3.2 実際の応用

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

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

教科書では，配列を用いたプリントキューのプログラム(p.123-125 List 4-5)を載せている．これも講義では説明しないので，各自，プログラムを解析せよ．

3.3 キューの実装

キューを実装する関数をリスト2に示す．これは，教科書の List 4-4(p.120-121)と同じである(転載について)．

このプログラムでは，配列queue[]を使ってキューを実現している．配列 queue[]とキューの先頭を表す変数queue_firstと末尾を表す queue_lastはグローバル変数と宣言されているので，以下のキューを操作する関数で直にアクセスすることができる．

キューを実装するための記憶領域が確保されたならば，それを操作しなくてはならない．キューの操作は2つで，データを追加することと，データを取り出すことである．リスト2では，次の2つの関数でそれを行っている．

void enqueue(int val): キューへデータvalを追加する関数である．データを追加したならば，キューの末尾を表す変数 queue_lastを1移動(加算)している．キューがいっぱいで，さらにデータを追加しようとするとプログラムはメッセージを出すようになっている．
int dequeue(void): キューからデータを取り出す関数で，戻り値が取り出したデータである．データを取り出したならば，キューの先頭を表す変数 queue_firstを1移動(加算)している．キューが空の状態でデータを取り出そうとするとプログラムはQUEUE_EMPTYを返すようになっている．

ここで使われているプログラムのテクニックは，すでに学習済みであるが，分かりにくいものだけ述べておく．

15行目 (queue_last+1)%QUEUE_MAX

2項演算子%は，割り算の結果の余りを返す．これをりようして，このプログラムでは，queue_lastやqueue_firstの値を，

$\displaystyle \cdots\rightarrow0\rightarrow 1\rightarrow 2\rightarrow 3\rightar... ...ghtarrow 3\rightarrow 4\rightarrow 5\rightarrow 0\rightarrow 1\rightarrow\cdots$

とサイクリック(cyclic:周期の)に変化させている．5の次の値を0にしているのである．これは，サイクリックに値を変化させて対時の常套手段である．

リスト2 キューの実装(転載について)

   1 #define QUEUE_MAX 5+1   /* キューのサイズ+1 */
   2 #define QUEUE_EMPTY -1
   3 
   4 /* 配列によるキュー構造 */
   5 int queue[QUEUE_MAX];
   6 /* キューの先頭位置（配列先頭からのオフセット） */
   7 int queue_first=0;
   8 /* キューの末尾位置（配列先頭からのオフセット） */
   9 int queue_last=0;
  10 
  11 /* キューにデータを追加する */
  12 void enqueue(int val)
  13 {
  14     /* lastの次がfirstならば */
  15     if((queue_last+1)%QUEUE_MAX ==queue_first)
  16     {
  17         /* 現在配列の中身は，すべてキューの要素で埋まっている */
  18         printf("ジョブが満杯です\n");
  19     }
  20     else
  21     {
  22         /* キューに新しい値を入れる */
  23         queue[queue_last]=val;
  24         /* queue_lastを1つ後ろにずらす。
  25            もし，いちばん後ろの場合は，先頭にもってくる */
  26         queue_last=(queue_last+1)%QUEUE_MAX;
  27     }
  28 }
  29 
  30 /* キューからデータを取り出す */
  31 int dequeue(void)
  32 {
  33     int ret;
  34 
  35     if(queue_first==queue_last)
  36     {
  37         /* 現在キューは1つもない */
  38         return QUEUE_EMPTY;
  39     }
  40     else
  41     {
  42         /* いちばん先頭のキューを返す準備 */
  43         ret=queue[queue_first];
  44         /* キューの先頭を次に移動する */
  45         queue_first=(queue_first+1)%QUEUE_MAX;
  46         return ret;
  47     }
  48 }

[転載について]
このページ中のリスト2のプログラムは，教科書として使用している以下の書籍

書名プログラミングの宝箱　アルゴリズムとデータ構造 ISBN4-7973-2419-8

著作者紀平拓男・春日伸弥

出版社ソフトバンク　パブリッシング株式会社

から転載しました．この転載に関しては，著者と版元に許諾を得ています．

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

no counter

書名	プログラミングの宝箱　アルゴリズムとデータ構造 ISBN4-7973-2419-8
著作者	紀平拓男・春日伸弥
出版社	ソフトバンク　パブリッシング株式会社