[#3] Queue

 

Queue란?

먼저 온 차례대로 줄을 세우는 방식을 코드로 구성한 것을 의미한다. 먼저들어가고 먼저 나오는 FIFO(First in First Out) 방식 또는 선입선출 자료구조를 뜻한다.

 

 

 

---

 

순환 큐

배열의 공간 하나를 비워두고 후단이 배열의 끝을 알 수 있게끔 만든 자료구조이다.   

속도가 빠르고 메모리의 공간이 한정적일 때 사용이 유리하다.

 

---

 

링크드 리스트 큐

연결리스트의 노드를 활용한 큐이다. 

 

LinkedListQueue.h

#ifndef LINKEDLISTQUEUE_H
#define LINKEDLISTQUEUE
#pragma warning(disable:4996)
#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;   // Node의 개수를 가짐
} LinkedQueue;

void LQ_CreateQueue(LinkedQueue** Queue); // Queue 생성
void LQ_DestroyQueue(LinkedQueue* Queue); // Queue 파괴 - Queue에 존재하는 모든 Node를 해제 후 Queue 파괴

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

void LQ_Enqueue(LinkedQueue* Queue, Node* NewNode);
// Queue에 노드 삽입
// Node 생성과 동시 Queue에 Enqueue 를 하는 경우 LQ_Enqueue(Queue,LQ_CreateNode("XXX"))

Node* LQ_Dequeue(LinkedQueue* Queue);
// Queue에 Dequeue 수행
// Dequeue와 동시 Dequeue된 Node를 파괴하려면
// LQ_DestroyNode(LQ_Dequeue(Queue))

int LQ_IsEmpty(LinkedQueue* Queue); // Queue가 비어있는 여부 확인.

void LQ_PrintQueue(LinkedQueue* Queue); // Queue의 모든 노드들의 데이터를 출력 - 자체제작

#endif

 

LinkedListQueue.cpp

#include "LinkedListQueue.h"
#pragma warning(disable:4996)
// Queue 생성
void LQ_CreateQueue(LinkedQueue** Queue) {
	(*Queue) = (LinkedQueue*)malloc(sizeof(LinkedQueue));

	(*Queue)->Front = NULL;
	(*Queue)->Rear = NULL;
	(*Queue)->Count = 0;

}
// Queue 파괴 - Queue에 존재하는 모든 Node를 해제 후 Queue 파괴
void LQ_DestroyQueue(LinkedQueue* Queue) {
	while (!(LQ_IsEmpty(Queue))) {
		Node* Dequeued = LQ_Dequeue(Queue);
		LQ_DestroyNode(Dequeued);
	}
	free(Queue);
}

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

	NewNode->NextNode = NULL;

	return NewNode;
}
void LQ_DestroyNode(Node* _Node) {
	free(_Node->Data);
	free(_Node);
}

// Queue에 노드 삽입
// Node 생성과 동시 Queue에 Enqueue 를 하는 경우 LQ_Enqueue(Queue,LQ_CreateNode("XXX"))
void LQ_Enqueue(LinkedQueue* Queue, Node* NewNode) {
	// 큐에 노드가 없을 경우
	if (LQ_IsEmpty(Queue))
	{
		// 전단과 후단 모두 NewNode를 가리키게 한다.
		Queue->Front = NewNode;
		Queue->Rear = NewNode;
	}
	else
	{
		// Rear의 링크를 조정한다.
		// 기존 Rear의 NextNode를 NewNode로 바꾸고
		// Rear는 새로운 NewNode를 가리키게 함.

		Queue->Rear->NextNode = NewNode;
		Queue->Rear = NewNode;
	}

	// 수행후 노드의 개수를 증가
	(Queue->Count)++;
	printf("  - Data : %s - Node Enqueued....\n", NewNode->Data);
	printf("  - Current Queue->Count = %d\n", Queue->Count);
}

// Queue에 Dequeue 수행
// Dequeue와 동시 Dequeue된 Node를 파괴하려면
// LQ_DestroyNode(LQ_Dequeue(Queue))
Node* LQ_Dequeue(LinkedQueue* Queue) {
	Node* Front = Queue->Front; // Front가 가리키는 Node를 저장

	// Queue노드가 한개 남았을시
	if (Queue->Front->NextNode == NULL)
	{
		// Queue의 Front와 Rear를 NULL로 .. Front == NULL -> Empty 상태
		Queue->Front = NULL;
		Queue->Rear = NULL;
	}
	else
	{
		Queue->Front = Queue->Front->NextNode;
	}
	(Queue->Count)--;
	printf("  - Data : %s - Node Dequeue....\n", Front->Data);
	printf("  - Current Queue->Count = %d\n", Queue->Count);
	return Front;
}

// Queue가 비어있는 여부 확인.
int LQ_IsEmpty(LinkedQueue* Queue) {
	return (Queue->Front == NULL);
}


// Queue의 모든 노드들의 데이터를 출력 - 자체제작
void LQ_PrintQueue(LinkedQueue* Queue) {
	Node* Printed = Queue->Front;

	printf(" *** Current Queue's Nodes *** \n");
	while (Printed != NULL)
	{
		printf("  %s  ->", Printed->Data);
		Printed = Printed->NextNode;
	}
	printf("\n");
	printf("\n");
}

 

 

• Queue->Rear->NextNode = NewNode;
  Queue->Rear = NewNode;
  처음에 이해하는데 애를 좀 먹은 구간이다. 첫 행의 구간은 Rear의 다음 노트를 그 다음 노트로 가리키게 해서 front의 다음 노드가 새로운 데이터의 노드가 되게끔 변경해주는 행이고, 밑에는 현재 후단의 노드 자체를 새로운 노드로 가리키게 하는 구문이다.

 

 

main.cpp

#pragma warning(disable:4996)
#include "LinkedListQueue.h"


int main() {
	LinkedQueue* Queue;

	LQ_CreateQueue(&Queue); // 큐 생성

	// Enqueue 확인
	LQ_Enqueue(Queue, LQ_CreateNode((char*)"AA"));
	LQ_Enqueue(Queue, LQ_CreateNode((char*)"BB"));
	printf("Queue->Front : %s\n", Queue->Front->Data);
	printf("Queue->Rear  : %s\n", Queue->Rear->Data);
	printf("Queue->Rear->NextNode  : %s\n", Queue->Rear->NextNode->Data);

	LQ_PrintQueue(Queue);

	return 0;
}

 

---