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が格納されます。
キューの実装
queue_sample.c
#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したメモリ上には次のデータを格納できません。
これを解決できるように改良してみるのも良いでしょう。