[Queue] Linked List 방식 환형 큐(환형 링크드 리스트)

앞서 설명한 Node 개념으로 Linked List 방식을 사용하여 간단한 환형 큐를 작성해 보았다.

개념적 이해를 돕고 보기 쉽게 아주 간단히 작성하기 위해 노드 중간 삽입 중간 삭제 등... 은 작성하지 않았다.

이정도 이해하고 구현할 수 있으면 충분히 응용해서 구현 가능 할 것이라 생각 된다.

#include <stdio.h>
#include <stdlib.h>

#define QUEUE_TEST							1



typedef struct CircularQueueNode
{
	int data;

	struct CircularQueueNode* Next;
	struct CircularQueueNode* Pre;
}CQNode;



#if QUEUE_TEST
CQNode* CreateNode(int i)
#else
CQNode* CreateNode()
#endif
{
	CQNode* NewNode = (CQNode*)malloc(sizeof(CQNode));

#if QUEUE_TEST
	NewNode->data = i;
#else
	NewNode->data = 0;
#endif

	NewNode->Next = NULL;
	NewNode->Pre = NULL;
	return NewNode;
}



void QueueBufInit(CQNode** Head, int QueueSize)
{
	int i=0;

	for(i=0; i<QueueSize; i++)
	{
#if QUEUE_TEST
		CQNode* NewNode = CreateNode(i+1);
#else
		CQNode* NewNode = CreateNode();
#endif

		if( (*Head) == NULL)
		{
			*Head = NewNode;
		}
		else
		{
			CQNode* Tail = (*Head);
			while(Tail->Next != NULL)
			{
				Tail->Next->Pre = Tail;
				Tail = Tail->Next;
			}

			Tail->Next = NewNode;
		}
	}

	CQNode* Tail = (*Head);
	while(Tail->Next != NULL)
	{
		Tail = Tail->Next;
	}

	(*Head)->Pre = Tail;
	Tail->Next = (*Head);
}


void DestroyNode(CQNode** Head)
{
	while((*Head)->Pre != NULL)
	{
		(*Head) = (*Head)->Pre;
		free((*Head)->Next);
	}
	free((*Head));
}


int main(void) {
	CQNode* Head = NULL;

	QueueBufInit(&Head, 3);

	int i, testCount = 10;

#if QUEUE_TEST
	for(i=0; i<testCount; i++)
	{
		printf("%d\n", Head->data);
		Head = Head->Next;
	}
#endif

	DestroyNode(&Head);

	system("PAUSE");

	return 0;
}