キューについても復習がてら実装してみます。

スポンサーリンク

キューのデータ構造を実装

キューのデータ構造は配列で実現し、リングバッファにします。
enqueueとdequeueの関数を実装しています。
バッファがフルか空かの判定は、enqueueとdequeue時に行い、
enumで定義した定数で状態管理をしています。ここが今回少し悩んだ箇所です。いくつか方法がありますが、最終的にわかり易さを優先して、フラグで状態管理することにしました。
下記が実装したソースコードになります。
main関数でdequeueとenqueueをしています。

 $ cat queue.c
#include <stdio.h>
#define SIZE 3

enum status{
	EMPTY,
	AVAILABLE,
	FULL
};

typedef struct{
	int data[SIZE];
	int head;
	int tail;
	int flag;
}queue_t;

//キューの中身をprint出力
void printQueue(queue_t* pQueue){
	int i;
	for(i = 0; i <= SIZE - 1; i++){
		printf("%d ", pQueue->data[i]);
	}
	printf("\n");
}

//キューの初期化
void initQueue(queue_t* pQueue){
	int i;
	//キューの中身を0埋め
	for(i = 0; i <= SIZE - 1; i++){
		pQueue->data[i] = 0;
	}
	//初期化
	pQueue->head = 0;
	pQueue->tail = 0;
	pQueue->flag = EMPTY;
	printQueue(pQueue);
}


//enqueue関数
void enqueue(queue_t* pQueue, int value){
	printf("enQ(%d)\n", value);
	//キューがFullの処理
	if(pQueue->flag == FULL){
		printf("Full\n");
		return;
	}
	//キューがFullでないので、enqueue操作
	pQueue->data[pQueue->tail] = value;
	//リングバッファのため、tailが配列の終端だったら0にする
	if(pQueue->tail == SIZE - 1){
		pQueue->tail = 0;
	//終端でなければ、tailをインクリメント
	}else{
		pQueue->tail++;
	}
	//フラグの更新
	if(pQueue->tail == pQueue->head){
		pQueue->flag = FULL;
	}else{
		pQueue->flag = AVAILABLE;
	}
	printQueue(pQueue);
}

//dequeue関数
void dequeue(queue_t* pQueue){
	printf("deQ\n");
	//キューがEmptyの処理
	if(pQueue->flag == EMPTY){
		printf("Empty\n");
		return;
	}
	//キューがEmptyでなければ、dequeue操作
	pQueue->data[pQueue->head] = 0;
	//リングバッファのため、headが配列の終端だったら0にする
	if(pQueue->head == SIZE - 1){
		pQueue->head = 0;
	//終端でなければ、headをインクリメント
	}else{
		pQueue->head++;
	}
	//フラグの更新
	if(pQueue->tail == pQueue->head){
		pQueue->flag = EMPTY;
	}else{
		pQueue->flag = AVAILABLE;
	}
	printQueue(pQueue);
}

int main(){
	queue_t queue;
	queue_t* pQueue = &queue;
	
	initQueue(pQueue);
	dequeue(pQueue);
	enqueue(pQueue, 1);
	enqueue(pQueue, 2);
	enqueue(pQueue, 3);
	enqueue(pQueue, 4);
	enqueue(pQueue, 5);
	dequeue(pQueue);
	dequeue(pQueue);
	dequeue(pQueue);
	dequeue(pQueue);
	dequeue(pQueue);
	enqueue(pQueue, 1);
	enqueue(pQueue, 2);
	enqueue(pQueue, 3);
	enqueue(pQueue, 4);
	dequeue(pQueue);
	dequeue(pQueue);
	dequeue(pQueue);
	dequeue(pQueue);
	enqueue(pQueue, 1);
	dequeue(pQueue);
	dequeue(pQueue);
	enqueue(pQueue, 1);
	enqueue(pQueue, 2);
	enqueue(pQueue, 3);
	dequeue(pQueue);
	dequeue(pQueue);
	dequeue(pQueue);
	dequeue(pQueue);
	dequeue(pQueue);
	enqueue(pQueue, 1);
	enqueue(pQueue, 2);
	enqueue(pQueue, 3);
		
	return 0;
}

下記が実行結果になります。EMPTYとFULLの状態遷移、またenqueueとdequeueの動きも確認できます。
enqueueとdequeueをそれぞれ交互に繰り返して、リングバッファのデータ構造となっていることも確認できます。
（配列の終端までenqueueされた後、配列の先頭からenqueueされています）

 $ gcc queue.c -o queue
 $ ./queue
0 0 0 
deQ
Empty
enQ(1)
1 0 0 
enQ(2)
1 2 0 
enQ(3)
1 2 3 
enQ(4)
Full
enQ(5)
Full
deQ
0 2 3 
deQ
0 0 3 
deQ
0 0 0 
deQ
Empty
deQ
Empty
enQ(1)
1 0 0 
enQ(2)
1 2 0 
enQ(3)
1 2 3 
enQ(4)
Full
deQ
0 2 3 
deQ
0 0 3 
deQ
0 0 0 
deQ
Empty
enQ(1)
1 0 0 
deQ
0 0 0 
deQ
Empty
enQ(1)
0 1 0 
enQ(2)
0 1 2 
enQ(3)
3 1 2 
deQ
3 0 2 
deQ
3 0 0 
deQ
0 0 0 
deQ
Empty
deQ
Empty
enQ(1)
0 1 0 
enQ(2)
0 1 2 
enQ(3)
3 1 2

動作確認も兼ねていたので、少々main関数が長くなってしまいましたね。。

スポンサーリンク