キューについても復習がてら実装してみます。
スポンサーリンク
キューのデータ構造を実装
キューのデータ構造は配列で実現し、リングバッファにします。
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関数が長くなってしまいましたね。。
スポンサーリンク