キュー(Queue)
Top -> プログラミング -> アルゴリズム(Algorithm by the C language) -> キュー(Queue)
1.キュー(Queue)とは

イメージとしては筒を思い出してください。

片方から物を入れて、もう一方の出口から取り出す。これがキュー(Queue)です。

メリットとして、二つ以上のスレッドやオブジェクト同士でデータのやり取りをする場合、各スレッドの処理状態の違いから、スレッドによっては待ち時間が生じます。そこで、緩衝として、キュー(Queue)を用います。一番有名なのが、Windowsのメッセージキュー(Queue)です。Windowsはメッセージ処理をキューで処理しております。

2.キュー(Queue)の実装

キュー(Queue)にデータを入れるのには、リスト構造の最後へデータを追加する事で可能となります。

/* * リストの先頭にNodeを追加 */ void HeadInsert(LIST **Head, LIST *Node) { /* データを追加 */ Node->next = *Head; *Head = Node; } /* * リストの最後にNodeを追加 */ void TailInsert(LIST **Head, LIST *Node) { LIST *p; if(*Head == (LIST *)NULL){ /* リストにデータが無い場合、先頭に追加 */ HeadInsert(Head, Node); }else{ for(p=*Head; p->next!=(LIST *)NULL; p=p->next); /* リストの最後を検索 */ /* データを追加 */ p->next = Node; Node->next = NULL; } }

キュー(Queue)のデータを取り出すには、リスト構造の先頭でデータを取得し削除する事で可能となります。 データを入れるのには、リスト構造の先頭へ、取り出しはリスト構造の最後からでも実装可能です。

/* * リスト内のNodeを削除 */ void DeleteNode(LIST **Head, int Position) { LIST *p, *Node; Position--; /* 削除位置の一つ前にする */ if(*Head != (LIST *)NULL){ /* LISTが存在しないなら終了 */ if(Position==0){ /* 削除位置が先頭なら解放 */ p=*Head; *Head = p->next; NodeFree(p); /* 削除位置がList内なら */ }else if(GetNodeTotal(Head)>Position && Position>0){ p=GetNode(Head, Position); /* 削除位置のNodeを取得 */ Node = p->next; /* Nodeを解放する */ p->next = Node->next; NodeFree(Node); } } } /* * Nodeのデータを取得 */ LIST *GetNode(LIST **Head, int n) { int j=1; LIST *p; /* NULLが出るか、n番目のノードを取得するまでループ */ for(p=*Head; p!=(LIST *)NULL; p=p->next){ if(j==n)break; j++; } return p; }
サンプル

以下のリンクからサンプルを閲覧又はダウンロードできます。
このサンプルはSHIFT-JISで書かれております。

閲覧またはダウンロード
戻る
カウンター