Queue(연결리스트)

1. Queue를 연결리스트로 구현

Queue는 연결리스트로 구현하기가 아주 용이합니다. 배열로 구현했을 때 보다 장점이 되게 많습니다. Enqueue와 Dequeue가 배열 못지않게 빠릅니다. 거기다가 메모리도 배열보다 효율적으로 사용합니다. 따라서 많은 사람들은 Queue를 연결리스트로 구현하는 것을 선호하는 편입니다.

헤더파일

LinkedQueue.h

#ifndef LINKED_QUEUE_H
#define LINKED_QUEUE_H
#define _CRT_SECURE_NO_WARNINGS

#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 Count;
}LinkedQueue;

void LQ_CreateQueue(LinkedQueue** Queue);
void LQ_DestroyQueue(LinkedQueue* Queue);

Node* LQ_CreateNode(char* NewData);
void LQ_DestroyNode(Node* _Node);

void LQ_Enqueue(LinkedQueue* Queue, Node* NewNode);
Node* LQ_Dequeue(LinkedQueue* Queue);

int LQ_IsEmpty(LinkedQueue* Queue);

#endif

단방향 연결리스트로 구현을 했고, Rear를 추가해서 연결리스트의 마지막 노드의 주소값을 저장하는 모습입니다. 그리고 Count로 노드의 개수도 세줍니다. Front와 Rear가 둘 다 존재하기 때문에, Enqueue와 Dequeue를 할 때 노드를 찾으러 다닐 수고도 덜었습니다.

void LQ_CreateQueue(LinkedQueue** Queue); -> Queue리스트 생성함수
void LQ_DestroyQueue(LinkedQueue* Queue); -> Queue리스트 삭제함수

Node* LQ_CreateNode(char* NewData); -> Node 생성함수
void LQ_DestroyNode(Node* _Node); -> Node 삭제함수

void LQ_Enqueue(LinkedQueue* Queue, Node* NewNode); -> Enqueue함수
Node* LQ_Dequeue(LinkedQueue* Queue); -> Dequeue함수

int LQ_IsEmpty(LinkedQueue* Queue); -> 리스트가 비어있는지 알려주는 함수

소스파일

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_DestroyQueue(LinkedQueue* Queue) {
	while (!LQ_IsEmpty(Queue)) {
		Node* Popped = LQ_Dequeue(Queue);
		LQ_DestroyNode(Popped);
	}

	//큐를 자유 저장소에서 할당 해제
	free(Queue);
}

Node* LQ_CreateNode(char* NewData) {
	Node* NewNode = (Node*)malloc(sizeof(Node));
	NewNode->Data = (char*)malloc(strlen(NewData) + 1);

	strcpy(NewNode->Data, NewData); //데이터를 저장한다.

	NewNode->NextNode = NULL; //다음 노드에 대한 포인터는 NULL로 초기화한다.

	return NewNode;
}

void LQ_DestroyNode(Node* _Node) {
	free(_Node->Data);
	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);
}

함수를 하나 하나 보겠습니다.

LQ_CreateQueue

void LQ_CreateQueue(LinkedQueue** Queue) {
	//큐를 자유 저장소에 생성
	(*Queue) = (LinkedQueue*)malloc(sizeof(LinkedQueue)); -> Queue리스트 동적할당
	(*Queue)->Front = NULL; -> Front 초기화
	(*Queue)->Rear = NULL; -> Rear 초기화
	(*Queue)->Count = 0; -> Count 초기화
}

LQ_DestroyQueue

void LQ_DestroyQueue(LinkedQueue* Queue) {
	while (!LQ_IsEmpty(Queue)) { // 큐가 비어있지 않다면
		Node* Popped = LQ_Dequeue(Queue); -> Queue리스트에 노드를 다 Dequeue한다
		LQ_DestroyNode(Popped); -> Node 동적 할당 해제
	}

	//큐를 자유 저장소에서 할당 해제
	free(Queue); -> Queue 동적 할당 해제
}

LQ_CreateNode

Node* LQ_CreateNode(char* NewData) {
	Node* NewNode = (Node*)malloc(sizeof(Node)); -> 노드 동적할당
	NewNode->Data = (char*)malloc(strlen(NewData) + 1); -> Data가 문자열이므로 Data(문자열) 동적할당

	strcpy(NewNode->Data, NewData); -> 데이터를 저장한다.

	NewNode->NextNode = NULL; -> 다음 Node에 대한 포인터는 NULL로 초기화한다.

	return NewNode; -> 만든 Node반환
}

LQ_Enqueue

void LQ_Enqueue(LinkedQueue* Queue, Node* NewNode) {
	if (Queue->Front == NULL) { -> Queue가 비어있다면
		Queue->Front = NewNode; -> Front에 NewNode의 주소값 저장
		Queue->Rear = NewNode; -> Rear에 NewNode의 주소값 저장
		Queue->Count++; -> Count 1 증가
	}
	else { -> Queue가 비어있지 않다면
		Queue->Rear->NextNode = NewNode; -> 끝의 Node의 NextNode에 NewNode 주소값 저장
		Queue->Rear = NewNode; -> Rear에 NewNode의 주소값으로 초기화
		Queue->Count++; -> Count 1 증가
	}
}

LQ_Dequeue

Node* LQ_Dequeue(LinkedQueue* Queue) {
	//LQ_Dequeue() 함수가 반환할 최상위 노드
	Node* Front = Queue->Front; -> 맨 앞의 Node의 주소값 저장

	if (Queue->Front->NextNode == NULL) { -> Node가 1개라면
		Queue->Front = NULL; -> Front와 Rear에 NULL대입
		Queue->Rear = NULL;
	}
	else { -> Node가 여러개라면
		Queue->Front = Queue->Front->NextNode; -> Front에 2번째 Node의 주소값 저장
	}

	Queue->Count--; -> Count 1 감소

	return Front; -> 저장해둔 맨앞에 노드 반환
}

LQ_IsEmpty

int LQ_IsEmpty(LinkedQueue* Queue) {
	return (Queue->Front == NULL); -> Front가 NULL이면 1 아니면, 0 반환
}

실행예시

적절한 main함수를 구현해서 실행해보겠습니다.
LinkedQueueMain.c

#include "LinkedQueue.h"

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

	LQ_CreateQueue(&Queue);

	LQ_Enqueue(Queue, LQ_CreateNode("abc"));
	LQ_Enqueue(Queue, LQ_CreateNode("def"));
	LQ_Enqueue(Queue, LQ_CreateNode("efg"));
	LQ_Enqueue(Queue, LQ_CreateNode("hij"));

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

	while (LQ_IsEmpty(Queue) == 0) {
		Popped = LQ_Dequeue(Queue);

		printf("Dequeue: %s\n", Popped->Data);

		LQ_DestroyNode(Popped);
	}

	LQ_DestroyQueue(Queue);

	return 0;
}

결과

Queue Size : 4
Dequeue: abc
Dequeue: def
Dequeue: efg
Dequeue: hij