待ちとは？
|
待ち行列（キュー）も，逐次入出力が繰り返されるデータを一時的に貯えておくためのデータ構造である。なお，英語でキュー(queue)とは，レジなどで順番を待つ人の列も意味する。 待ち行列にデータを追加することを enqueue と言い，待ち行列からデータを取り出すことを dequeue と言う。待ち行列へのデータの追加取り出しは次のように行われる。 すなわち，待ち行列から一つデータを取り出すとき，それは（残っているデータの中で）最初に追加したものである。このような追加取り出しの方法を先入れ先出し法，First In First Out (FIFO) と呼ぶことがある。待ち行列を用いるのは「仕事は頼まれた順に古い方から片付けて行く」という方針で動くプログラムを作るときである。 配列で上のような待ち行列を実現したとしよう。すると， dequeue を行ったときに，配列内のデータが一つずつ左にずれる必要がある。人間の場合には，各々の人が前に進めばいいのであるが，プログラムではプログラムが動かしてやる必要があり，これでは処理が遅くなる。 QUEUE_SIZE は待ち行列本体である配列の要素数であり，これが待ち行列に収納できるデータの最大数となる。 スタックでは，データの追加および取り出しが，データの末尾でのみ行われたから，データの先頭の位置は変化することがなかった。しかし，待ち行列においては，データの追加はデータ末尾で，取り出しはデータ先頭で行われるから，先頭の位置が変化する。そこで， queue_head という先頭位置を表すための変数も必要となる。データ末尾の位置は queue_head + queue_num 待ち行列が空でなければ、それからデータを一つ取り出し，その値を *deq_data に代入し、queue_num は１減じ， queue_head は１つ進めて、SUCCESS を戻り値として返す。ただし，待ち行列が空のときは，戻り値として FAILURE を返す他は、何もしない。 という関数で待ち行列の機能を作ることができるが，現実には，これではすぐに待ち行列が満杯になってしまい，機能不全に陥る。 前述の，待ち行列がすぐに満杯になる問題を解決するには，データを取り出す度に配列 queue_data の先頭部分に空きができるから，この部分を再利用すれば良いことに気付く。これを効果的に行ったデータ構造が，次に述べるリングバッファである。 前節の queue_data という配列の最後尾を配列の先頭にくっつけることにより，配列が環状になったと考える。すなわち，queue_data[QUEUE_SIZE-1] の次の要素は queue_data[0] と考えるわけである。これにより，配列の先頭部分にできる空きを再利用することが可能になる。 配列を環状に扱うためには，剰余演算子 % を活用して，添字を巡回的に動かせば良い（巡回的な添字を参照）。 待ち行列が空でなければ、それからデータを一つ取り出し，その値を *deq_data に代入し、queue_num は１減じ， queue_head は１つ進めて、SUCCESS を戻り値として返す。ただし，待ち行列が空のときは，戻り値として FAILURE を返す他は、何もしない。 は待ち行列が満杯であるため，追加できていない。そして，待ち行列が空になるまで，データを取り出して終了している。この最後の部分は、次のようにも書き換えることができる。 をまとめて，構造体 queue として定義し直し，関数群も queue 型を指すポインタを引数にとるように変更してみる。 次の関数は，待ち行列の内容を表示する関数である。data[i] にデータが入っているかどうかの判断を行うのに，排他的和演算子 ^ を用いている。 待ち行列が実際に使われているものの一つに，キーボードバッファというものがある。キーボードから入力された文字は，その処理が追い付かない場合には，一時的に貯えておく必要があるが，その場所をキーボードバッファという。キーボードバッファのデータは，入力された順に古い方から処理されるべきである。したがって，それには待ち行列のデータ構造が適している。 ただし， queueEmptyQ は，待ち行列が空であるときに 1 を，空ではないときに 0 を返すものとする。 人の人間関係（知り合いかどうか）を表した配列 a[N][N] がある。ただし， i 番目の人と j 番目の人とが知り合いであるとき 番目の人に辿り着けない場合には，acquaintDistance は -1 を返すこととする。関数名の acquaint は知り合いにさせる， distance は距離という意味である。 ヒント：待ち行列を利用する。最初に x を待ち行列に入れ，後は，「待ち行列から一つ dequeue して，その人の知り合いを待ち行列に から各人までの知り合い距離を入れる配列も用意しておき，新しい人を enqueue する度に，その人までの距離をその配列に入れる。 |
[ 59] 待ち行列
[引用サイト] http://www.cc.kyoto-su.ac.jp/~yamada/ap/queue.html
