キューの実装

目次

C言語にはないデータ構造

データ構造でも説明していますが、C言語では元々実装されていないデータ構造が存在します。
このページではその内キューという構造を解説し、実装を試みます。

キューとは

キューは、「先入れ先出し」(FIFO:First In First Out)のデータ構造です。
末尾にデータを追加するENQ(エンキュー)と先頭のデータを取り出すDEQ(デキュー)という操作を行うことができます。

待ち行列とも言い、CPUや入出力装置の順番待ちなどに使われています。

例を見てみましょう。右が先頭で左が末尾とします。

2 5 0 6 7

先頭から順に7、6、0、5、2とデータが入っています。
これをDEQすると先頭の7が取り出され、以下のようになります。

2 5 0 6

今度はこれに1をENQします。

1 2 5 0 6

そうすると、このように末尾に1が格納されます。

キューの実装

#include <stdio.h>

#define MAX_DATA 32

struct queue
{
	int arr[MAX_DATA];
	int first;			//次にDEQする配列の添え字
	int last;			//次にENQする配列の添え字
};

int enq(struct queue *que, int input)
{
	if (que->arr[que->last] <= MAX_DATA) { que->arr[que->last] = input;
		que->last++;

		return 0;
	}
	else
	{
		printf("これ以上データを追加できません。\n");
		return -1;
	}
}

int deq(struct queue *que)
{
	int output = que->arr[que->first];

	if (output != 0)
	{
		que->arr[que->first] = 0;
		return output;
	}
	else
	{
		printf("データがありません。\n");
		return -1;
	}
}

void init_queue(struct queue *que)
{
	int i;

	for (i = 0; i < MAX_DATA; i++) que->arr[i] = 0;

	que->first = 0;
	que->last = 0;
}

void show_queue(struct queue *que)
{
	int i;
	for (i = 0; i < MAX_DATA; i++) printf("%d ", que->arr[i]);

	printf("\nfirst:%d last%d\n\n", que->first, que->last);
}

int main(void)
{
	int i;
	int d;
	struct queue que;

	init_queue(&que);
	for (i = 1; i <10; i++)
	{
		enq(&que, i * 2);
		show_queue(&que);
	}

	d = deq(&que);
	printf("\n%d\n", d);
	show_queue(&que);

	return 0;
}

長いプログラムに見えますが、実際は短いプログラムが並んでいるだけです。
上から順に構造体queue、関数enq()、関数deq()、関数init_queue()、関数show_queue()、main()関数の定義となっています。

構造体queueはデータを格納する配列arr[]と、先頭と末尾をそれぞれ表す変数first、lastを持っています。
関数enq()、deq()はそれぞれENQ、DEQの操作を実装しています。
関数init_queue()で構造体queueを初期化し、show_queue()で構造体queueの中身を表示しています。
これらの関数をmain()関数で使用しています。

このコードではDEQしたメモリ上には次のデータを格納できません。
これを解決できるように改良してみるのも良いでしょう。



「キューの実装」への2件のフィードバック

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

CAPTCHA