[자료구조] 큐 - 03 . 링크드 큐

[링크드 큐]

[링크드 큐]

=>각 노드는 앞 노드에 대한 포인터를 이용하여 구성되어 있기에 삽입은 새 노드의 포인터에 후단을 연결,

제거는 전단 바로 이후의 노드에서 전단에 대한 포인터를 거두는 것으로 끝난다 .

=>또한 용량의 제한이 벗어 가득 차 있는지에 대한 체크가 필요 없다 .

[링크드 큐가 순환 큐보다 우월한가 ? ]

=>성능은 순환큐가 더 빠르다 . 노드를 생성,삭제하기 위한 malloc()을 호출할 필요가 없기 때문 .

크기가 예측 가능하고 고성능이 필요한 버퍼와 같은 사례는 순환큐가 더 적절하다 .

 

[링크드 큐 구현하기]

[노드의 선언]

typedef struct tagNode
{
    char* Data;
    struct tagNode* NextNode;
}

[링크드 큐의 선언]

typedef struct tagLinkedQueue
{
    Node* Front;
    Node*Rear;
    int Count;
}LinkedQueue;

[링크드 큐의 생성]

void LQ_CreateQueue(LinkedQueue ** Queue)
{
    (*Queue)=(LinkedQueue*)malloc(sizeof(LinkedQueue));
    (*Queue)->Front=NULL;
    (*Queue)->Rear=NULL;
    (*Queue)->Count=0;
}

[링크드 큐의 소멸]

void LQ_DestroyQueue(LinkedQueue* Queue)
{
    while(!LQ_IsEmpty(Queue))
    {
    Node* Popped = LQ_Dueque(Queue));
    LQ_DestroyNode(Popped);
    }
    free(Queue);
}

[링크드 큐의 삽입(Enqueue)]

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++;
    }
}

[링크드 큐의 제거(Dequeue)]

Node* LQ_Dequeue(LinkedQueue * Queue)
{
    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;
}

[링크드 큐 구현하기]

[LQ.h]

#ifndef LQ
#define LQ

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

typedef struct tagNode
{
	char* Data;
	struct tagNode* NextNode;
}Node;

typedef struct tagLinkedQueue
{
	Node* Front;
	Node* Rear;
	int Capacity;
}LinkedQueue;

//큐 생성
void LQ_CreateQueue(LinkedQueue** Queue);

// 노드 생성
Node* LQ_CreateNode(const char* _Data);

//큐 삭제
void LQ_DestroyQueue(LinkedQueue* Queue);

//노드 삭제
void LQ_DestroyNode(Node* Destroy);

//삽입
void LQ_Enqueue(LinkedQueue* Queue, Node* NewNode);

//삭제
Node* LQ_Dequeue(LinkedQueue* Queue);

//비었는지
bool LQ_IsEmpty(LinkedQueue* Queue);

#endif // !LQ

[LQ.cpp]

#include "LQ.h"
//큐 생성
void LQ_CreateQueue(LinkedQueue** Queue)
{
	(*Queue) = (LinkedQueue*)malloc(sizeof(LinkedQueue));
	(*Queue)->Front = NULL;
	(*Queue)->Rear = NULL;
	(*Queue)->Capacity = 0;
}


// 노드 생성
Node* LQ_CreateNode(const char* _Data)
{
	Node* NewNode = (Node*)malloc(sizeof(Node));
	NewNode->NextNode = NULL;
	NewNode->Data = (char*)malloc(strlen(_Data) + 1);
	strcpy_s(NewNode->Data,strlen(_Data)+1, _Data);
	return NewNode;
}

//큐 삭제
void LQ_DestroyQueue(LinkedQueue* Queue)
{
	while (!LQ_IsEmpty(Queue))
	{
		Node* Popped = LQ_Dequeue(Queue);
		LQ_DestroyNode(Popped);
	}
	free(Queue);
}

//노드 삭제
void LQ_DestroyNode(Node* Destroy)
{
	free(Destroy->Data);
	free(Destroy);
}

//삽입
void LQ_Enqueue(LinkedQueue* Queue, Node* NewNode)
{
	if (Queue->Front == NULL)
	{
		Queue->Front = NewNode;		
	}
	else
	{
		Queue->Rear->NextNode = NewNode;
	}
	Queue->Rear = NewNode;
	Queue->Capacity++;
}

//삭제
Node* LQ_Dequeue(LinkedQueue* Queue)
{
	Node* Popped = Queue->Front;
	if (Queue->Front == Queue->Rear)
	{
		Queue->Front = NULL;
		Queue->Rear = NULL;
	}
	else
	{
		Queue->Front = Queue->Front->NextNode;
	}
	Queue->Capacity--;
	return Popped;
}

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

[Test.cpp]

#include "LQ.h"

int main(void)
{
	Node* Popped;
	LinkedQueue* Queue;

	LQ_CreateQueue(&Queue);

	LQ_Enqueue(Queue, LQ_CreateNode("abc"));
	LQ_Enqueue(Queue, LQ_CreateNode("def"));
	LQ_Enqueue(Queue, LQ_CreateNode("ghi"));
	LQ_Enqueue(Queue, LQ_CreateNode("jkl"));

	printf("Queue Size : %d\n", Queue->Capacity);

	while (!LQ_IsEmpty(Queue))
	{
		Popped=LQ_Dequeue(Queue);
		printf("Dequeue: %s\n",Popped->Data);
		LQ_DestroyNode(Popped);
	}
	LQ_DestroyQueue(Queue);
	return 0;
}