トップ-> C言語入門:データ構造-> 14-11. キュー

←前ページへ :  トップへ :  次ページへ→


14-11.キュー

  スタックでは追加した順とは逆の順で取り出すデータ構造でした。 キューはこのように最初に入れた物は最後に取り出すというLIFOのスタックとは 逆順のデータ構造です。すなわち、最初に入れたデータは最初に取り出すFIFO (First In First Out)の構造です。入れた順番と同じ順番で 取り出すことができます。

  キューにデータを追加することをエンキュー(Enqueue:ENQ)、キューからデータを 取り出すことをデキュー(Dequeue:DEQ)と言います。

スタックのイメージ
(単純)キュー
  (単純)キューは、上図のようにキューの一端からデータを追加(エンキュー)し、 もう一端からデータを取り出(デキュー)します。これを後述するディーキュー に対して「単純キュー」と言います。普通は単に「キュー」と言います。

  単純キューの実装は単方向リストを使用し、 エンキューする場合はaddtailを、デキューする場合にはremovehead関数を 使用し、他の関数(プログラム終了用のremoveall以外)を除くと、単純キューに なります。

ディーキュー
  ディーキューとは、キューのどちらの端にもデータの追加をすることができ、 また、どちらの端からもデータを取り出すことができる特別なキューです。

  例えば、マルチスレッドプログラムで、一方のスレッドがキューに命令を溜めていきます。 そしてもう一方のスレッドがそれを処理していくようなプログラムがあったとします。 命令を実行していく方のスレッドで、「この命令は今実行できない!」と判断したとき、 時間の無駄を省くため、先に別(その次)の命令を実行しようとします。このときに 後で実行するけど、一番最後に回すのはちょっと問題がある場合に、通常はキューの 最後に追加しますが、キューの最初に追加すれば、1回分だけ後回しができるといった 使い方をします。

  ディーキューの実装は双方向リストを使います。双方向リストでは、リストの両端の 追加および削除が単方向リストよりも効率よくできるためです。


←前ページへ :  トップへ :  次ページへ→