データ構造/キュー(待ち行列) - nkym_memo @ ウィキ

キュー(待ち行列,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 <stdlib.h>
#include <stdio.h>
#include <ctype.h>

typedef long ELEM;

#define QUEUE_SIZE 100

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

#define next(a) (((a) + 1) % QUEUE_SIZE)

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;
}

---

参考文献

• 定本 Cプログラマのためのアルゴリズムとデータ構造(近藤嘉雪,ソフトバンククリエイティブ,1998)