Ｃでキュー構造を自作してみた

Ｃ言語でキュー構造（FIFO(First In First Out) : 先入先出）を自作してみました。

やりたいこと

queue.h

#ifndef QUEUE_H_
#define QUEUE_H_

/* キュー構造体 */
typedef struct queue* Queue;

/* コンストラクタ */
Queue newQueue(void);

/* キューに要素を追加する */
void enqueue(Queue, void*);

/* キューから要素を取り出す */
void* dequeue(Queue);

#endif /* QUEUE_H_ */

---

配列を用いる

（ヘッダファイルに#define CAPACITY (256)を追加。数字の部分は任意）

• キュー構造体定義

queue.c

#include <stdlib.h>
#include "queue.h"

/* キュー構造 */
struct queue{
    void* value[CAPACITY+1];
	size_t front; //先頭要素の添字
	size_t back; //末尾要素の添字
};

---

• コンストラクタ

/*
 * キューのコンストラクタ
 */
Queue newQueue(void){
	//メモリ確保
	Queue queue=(Queue)malloc(sizeof(struct queue));
	if(!queue){//メモリ確保失敗
		abort();
	}

	//キューの先頭と末尾の添字を0にセットする
    queue->front=0;
	queue->back=0;
	return queue;
}

---

• キューに要素を追加

/*
 * キューの末尾に要素を追加
 * queue : キュー
 * value : 追加するデータ
 */
void enqueue(Queue queue, void* value){
    //要素が追加できない場合はエラー
    if(queue->back==CAPACITY && queue->front==0){
        abort();
    }else if(queue->back-queue->front==-1){
        abort();
    }
    
	//ノードにデータをセット
    queue->value[queue->back++]=value;
    if(queue->back>CAPACITY){
        queue->back%=(CAPACITY+1);
    }
}

---

• キューから要素を取り出す

/*
 * キューの先頭から要素を取り出す
 * queue : キュー
 * 返却値 : 取り出すデータ
 */
void* dequeue(Queue queue){
    //要素が空ならNULLを返す
    if(queue->front==queue->back){
        return NULL;
    }

    //取得した値を返す
    void value=queue->value[queue->front++];
    if(queue->front>CAPACITY){
        queue->front%=(CAPACITY+1);
    }
    return value;
}

---

自己参照構造体を用いる

• キュー構造体定義

queue.c

#include <stdlib.h>
#include "queue.h"

/* ノード */
typedef struct node{
	void* value; //データ
	struct node* next; //次のデータの格納位置を示すポインタ
}Node;

/* キュー構造 */
struct queue{
	Node* front; //先頭ノードへのポインタ
	Node* back; //末尾ノードへのポインタ
};

---

• コンストラクタ

/*
 * キューのコンストラクタ
 */
Queue newQueue(void){
	//メモリ確保
	Queue queue=(Queue)malloc(sizeof(struct queue));
	if(!queue){//メモリ確保失敗
		abort();
	}

	//キューの先頭ノードと末尾ノードをNULLにセットする
	queue->front=NULL;
	queue->back=NULL;
	return queue;
}

---

• キューに要素を追加

/*
 * キューの末尾に要素を追加
 * queue : キュー
 * value : 追加するデータ
 */
void enqueue(Queue queue, void* value){
	//メモリ確保
	Node* node=(Node*)malloc(sizeof(Node));
	if(!node){//メモリ確保失敗
		abort();
	}

	//ノードにデータをセット
	node->value=value;

	//新しいノードの次はNULL
	node->next=NULL;

	//末尾ノードの次は新しいノード
	if(queue->back){
		queue->back->next=node;
	}

	//末尾ノードは新しいノード
	queue->back=node;

	//空だった場合、先頭ノードは新しいノードを指す
	if(!queue->front){
		queue->front=node;
	}
}

---

• キューから要素を取り出す

/*
 * キューの先頭から要素を取り出す
 * queue : キュー
 * 返却値 : 取り出すデータ
 */
void* dequeue(Queue queue){
	//要素が空ならNULLを返す
	if(!queue->front){
		return NULL;
	}

	//先頭ノードを取得
	Node* node=queue->front;

	//返却値を取得
	void* value=node->value;

	//キューの先頭を繋ぎ替える
	queue->front=node->next;

	//空になった場合、キューの末尾はNULL
	if(!queue->front){
		queue->back=NULL;
	}

	//旧先頭ノードを解放
	free(node);

	//取得した値を返す
	return value;
}