본문 바로가기
컴퓨터/자료구조

[C언어] 링크드 리스트로 구현한 int 저장형 큐 예제

by Luyin 2013. 11. 4.

'뇌를 자극하는 알고리즘' 의 링크드 큐 부분을 그대로 복사하여 int형에 맞게 수정한 것입니다.


LinkedQueue.h (헤더파일)

#ifndef LINKED_QUEUE_H #define LINKED_QUEUE_H #include <stdio.h> #include <stdlib.h> typedef struct tagNode { int Data; struct tagNode* NextNode; }Node; typedef struct tagLinkedQueue { Node* Front; Node* Rear; int Count; }LinkedQueue; void LQ_CreateQueue(LinkedQueue** Queue); void LQ_DestoryQueue(LinkedQueue** Queue); Node* LQ_CreateNode(int NewData); void LQ_DestoryNode(Node* _Node); void LQ_Enqueue(LinkedQueue* Queue, Node* NewNode); Node* LQ_Dequeue(LinkedQueue* Queue); int LQ_IsEmpty(LinkedQueue* Queue); #endif



LinkedQueue.c (헤더 구현파일)

#include <"LinkedQueue.h"

void LQ_CreateQueue(LinkedQueue** Queue)
{
	/* 큐를 자유 저장소에 생성 */
	(*Queue) = (LinkedQueue*)malloc(sizeof(LinkedQueue));
	(*Queue)->Front = NULL;
	(*Queue)->Rear = NULL;
	(*Queue)->Count = 0;
}
void LQ_DestoryQueue(LinkedQueue* Queue)
{
	while(!LQ_IsEmpty(Queue))
	{
		Node* Popped = LQ_Dequeue(Queue);
		LQ_DestoryNode(Popped);
	}
	/*	큐를 자유 저장소에서 해제 */
	free(Queue);
}
Node* LQ_CreateNode(int NewData)
{
	Node* NewNode = (Node*)malloc(sizeof(Node));

	NewNode->Data = NewData;	/* 데이터를 저장한다. */

	NewNode->NextNode = NULL;	/* 다음 노드에 대한 포인터는 NULL로 초기화한다. */
	
	return NewNode;	/* 노드의 주소를 반환한다. */
}
void LQ_DestoryNode(Node* _Node)
{
	free(_Node);
}
void LQ_Enqueue(LinkedQueue* Queue, Node* NewNode)
{
	if(Queue->Front == NULL)
	{
		Queue->Front = NewNode;
		Queue->Rear = NewNode;
		Queue->Count++;
	}else{
		Queue->Rear->NextNode = NewNode;
		Queue->Rear = NewNode;
		Queue->Count++;
	}
}
Node* LQ_Dequeue(LinkedQueue* Queue)
{
	/* LQ_Dequeue() 함수가 반환할 최상위 노드 */
	Node* Front = Queue->Front;

	if(Queue->Front->NextNode == NULL)
	{
		Queue->Front = NULL;
		Queue->Rear = NULL;
	}else{
		Queue->Front = Queue->Front->NextNode;
	}

	Queue->Count--;

	return Front;
}
int LQ_IsEmpty(LinkedQueue* Queue)
{
	return (Queue->Front == NULL);
}


Test_LinkedQueue.c
#include "LinkedQueue.h"

int main(void)
{
	Node* Popped;

	LinkedQueue* Queue;

	
	LQ_CreateQueue(&Queue);

	LQ_Enqueue(Queue, LQ_CreateNode(123));
	LQ_Enqueue(Queue, LQ_CreateNode(456));
	LQ_Enqueue(Queue, LQ_CreateNode(789));
	LQ_Enqueue(Queue, LQ_CreateNode(101));
	
	printf("Queue Size : %d\n\n", Queue->Count);
	
	while(LQ_IsEmpty(Queue) == 0)
	{
		Popped = LQ_Dequeue(Queue);
		printf("Dequeue: %d \n\n", Popped->Data);
		LQ_DestoryNode(Popped);
	}

	LQ_DestoryQueue(Queue);

	return 0;
}