> データ構造 > キュー(待ち行列)

データ構造/キュー(待ち行列)

Last-modified: 2011-03-01 (火) 13:35:12

キュー(待ち行列,queue,FIFO)

キュー(last-in,last out)
挿入が一方の端でのみ行われ、削除が反対の端でのみ行われるもの

先頭(front)/末尾(rear)
キューでの最初/最後

リングバッファ(ring buffer)
n個の要素を持つ配列x[n]において、最後の要素x[n-1]の次に最初の要素x[0]があるとする構造

実装方法

配列を利用した場合

キューの先頭/末尾を指す変数front/rearを用意
- rearは末尾の次の要素を指す
- 何も要素が入ってない状態ではfront == rear
- キューに要素を入れるごとに変数rearが１増える
- 挿入/削除はともに計算量O(1)

リングバッファ
- frontとrearを１増加するときに、%演算子を利用して剰余をとる

rear==frontが空を表現する場合の問題
行列が空であるか、フルであるかの区別が不能
- 解決法
  1. キューが空であることを示すフラグを用意する
  2. 必ず１つ空の要素を残しておく

サンプルプログラム(C)

init()：キューの初期化
enqueue()：キューに挿入
dequeue()：キューから取り出し
empty()：キューのデータが空かを確認


#include
#include
#include

typedef long ELEM;

#define

ELEM queue[QUEUE_SIZE];
int front;
int rear;

#define

void error(char *s)
{
	fprintf(stderr,s);
	exit(1);
}

void init()
{
	fornt = rear = 0;
}

void enqueue(ELEM x)
{
	if(next(rear) == front){
		error("キューがフルなので要素を入れられません\n");
	}
	queue[rear] = x;
	rear = next(rear);
}

ELEM dequeue()
{
	ELEM x;

	if(front == rear){
		error("キューが空なので要素を取り出せません\n");
	}
	x = queue[front];
	front = next(front);
	return x;
}

int empty()
{
	return fornt == rear;
}

参考文献