Cirqular Queue

지난번 글에서 원형 큐에 대해 알아봤다. 원형 큐는 배열로 저장하는 큐의 단점을 보완하기 위해 구현한 것으로 데이터의 맨 앞과 뒤의 인덱스를 기억하여 선형 배열을 마치 원형인 것처럼 사용하는 자료구조였다. 이번 글에서는 실제로 원형 큐를 어떻게 구현하였는지 소개한다.

구현한 방법

지금까지 구현한 자료구조는 모두 동적 배열을 사용하였으나 이번 원형 큐는 공간이 부족할 때마다 새로운 공간을 동적으로 할당 받지 않는다. 데이터를 저장할 공간이 부족한 순간은 front와 rear의 값에 달려 있는데 새로 공간을 할당 받으면 배열의 마지막 인덱스에서 공간이 늘어나므로 결국 데이터를 옮겨야 하는 상황이 생기기 때문이다. 물론 공간이 부족한 것보다 낫겠지만 구현하기에 복잡해진다.

내가 구현한 프로젝트는 DataType.h, CircularQueue.h, CircularQueue.c, main.c 네 개의 소스 파일로 구성된다.

DataType.h

배열에 저장되는 요소인 구조체 Element에 대한 정의가 포함된 파일이다. 이전과 바뀐 내용은 없다.

#pragma once
#define TRUE 1
#define FALSE 0

typedef struct Element {		// 배열 요소의 자료형 정의
	int age;
	char* name;
} Element;

CircularQueue.h

원형 큐에 대한 구조체 정의와 관련된 추상 자료형(ADT)이 존재하는 파일이다.

#pragma once
#include "DataType.h"
#define MAX_LEN 8

typedef struct {
	Element* arr;
	int front;	// 맨 처음 데이터의 인덱스
	int rear;	// 맨 뒤 데이터의 인덱스
} CircularQueue;

이전 게시물인 '원형 큐 알아보기'와의 통일성을 위해 배열의 크기인 MAX_LEN의 값을 8로 정했다.

typedef void (*PrintFunc)(Element* e);

CircularQueue* CQueCreate();
int CQueIsEmpty(CircularQueue* cqueue);
int CQueEnqueue(CircularQueue* cqueue, Element e);
int CQueDequeue(CircularQueue* cqueue, Element* e);
int CQuePeek(CircularQueue* cqueue, Element* e);
void CQuePrint(CircularQueue* cqueue, PrintFunc func);
void CQueDestroy(CircularQueue* cqueue);

이전 게시물처럼 포인터 함수 PrintFunc는 구조체 Element의 정의가 바뀔 때를 대비하여 선언하였다.

원형 큐와 관련된 함수 이름은 이전에 구현한 큐의 함수 이름에 Circular의 C를 붙여 구분하였다.

CircularQueue.c

원형 큐와 관련된 함수가 정의되는 파일이다.

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

메모리 동적 할당을 위해 stdlib.h, 출력 함수를 위해 stdio.h, 그리고 구현할 함수의 프로토타입과 구조체 CircularQueue에 대한 정의를 포함한 CircularQueue.h 파일을 포함해 주었다.

CircularQueue* CQueCreate()

구조체 CircularQueue를 동적 할당 받아 멤버 변수들을 초기화한 후 포인터 형을 반환해주는 함수이다.

CircularQueue* CQueCreate()
{
	CircularQueue* cqueue = (CircularQueue*)malloc(sizeof(CircularQueue));
	if (cqueue != NULL) {
		cqueue->arr = (Element*)malloc(sizeof(Element) * MAX_LEN);
		if (cqueue->arr == NULL) {
			free(cqueue);
			return NULL;
		}
		else
			cqueue->front = cqueue->rear = 0;	// front와 rear의 값이 같으면 원형 큐는 비어 있음
	}
	return cqueue;
}

int CQueIsEmpty(CircularQueue* cqueue)

원형 큐에 데이터가 존재하는지 검사하는 함수이다.

int CQueIsEmpty(CircularQueue* cqueue)
{
	if (cqueue->front == cqueue->rear ) return TRUE;
	else return FALSE;
}

front와 rear의 값이 같으면 비어 있는 것으로 간주한다.

int CQueEnqueue(CircularQueue* cqueue, Element e)

원형 큐에 데이터를 추가하는 함수이다.

int CQueEnqueue(CircularQueue* cqueue, Element e)
{
	int tmp = (cqueue->rear + 1) % MAX_LEN;	// 데이터를 추가했을 때 rear의 값을 미리 계산합니다.
	if (cqueue != NULL && tmp != cqueue->front) {	// tmp의 값이 front의 값과 같다면 배열이 이미 차있는 상태입니다.
		cqueue->arr[cqueue->rear] = e;
		cqueue->rear = tmp;	// 다시 계산할 필요 없이 tmp의 값을 대입합니다.
        	printf("{ %d, %s } 저장 완료\n", e.age, e.name);
		return TRUE;
	}
    	printf("데이터를 저장할 수 없습니다. 공간이 부족합니다.\n");
	return FALSE;
}

변수 tmp를 이용해 rear의 값을 먼저 증가시켜보고 그 값이 front와 같아진다면 현재 배열에 데이터를 추가할 공간이 없는 것이므로 FALSE를 반환한다.

int CQuePeek(CircularQueue* cqueue, Element* e)

원형 큐에서 가장 앞에 있는 데이터를 읽어오는 함수이다.

int CQuePeek(CircularQueue* cqueue, Element* e)
{
	if ((!CQueIsEmpty(cqueue))) {
		*e = cqueue->arr[cqueue->front];
		return TRUE;
	}
	return FALSE;
}

데이터를 읽을 뿐 배열에서 삭제하진 않는다. 따라서 front의 값도 변화하지 않는다.

int CQueDequeue(CircularQueue* cqueue, Element* e)

원형 큐에서 데이터를 꺼내온 후 삭제하는 함수이다. 실제로 값을 지우진 않고 front의 값을 증가시켜 없는 데이터로 취급한다.

int CQueDequeue(CircularQueue* cqueue, Element* e)
{
	if (CQuePeek(cqueue, e)) {
		cqueue->front = (cqueue->front + 1) % MAX_LEN;
		return TRUE;
	}
	return FALSE;
}

CQuePeek 함수와 거의 유사하므로 코드의 반복을 줄이고자 함수를 재사용하였다. CQuePeek 함수가 반환하는 값에 따라 CQueDequeue 함수의 반환 값이 결정되며, 추가로 CQueDequeue 함수는 배열에서 데이터를 삭제해야 하므로 front의 값을 수정하는 과정을 추가했다.

void CQuePrint(CircularQueue* cqueue, PrintFunc func)

원형 큐에 저장된 데이터를 모두 출력하는 함수이다. 포인터 함수 PrintFunc를 활용한다.

void CQuePrint(CircularQueue* cqueue, PrintFunc func)
{
	if (!(CQueIsEmpty(cqueue))) {
		printf("Elements in Circular Queue are:\n");
		int i = cqueue->front;
		while (i != cqueue->rear) {
			Element tmp = cqueue->arr[i];
			func(&tmp);
			i = (i + 1) % MAX_LEN;
		}
	}
}

void CQueDestroy(CircularQueue* cqueue)

할당 받았던 메모리를 반환하는 함수이다.

void CQueDestroy(CircularQueue* cqueue)
{
	if (cqueue != NULL) {
		free(cqueue->arr);
		free(cqueue);
	}
}

main.c

소스 코드

구현한 원형 큐를 테스트해보기 위해 작성한 소스 파일이다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include "CircularQueue.h"
#include "vld.h"

void printNameAge(Element* e)
{
	if (e != NULL)
		printf("Name: %s\tAge: %d\n", e->name, e->age);
}

int main(void)
{
	CircularQueue* cqueue = CQueCreate();
	if (cqueue == NULL) return;
	printf("\n\t[CQueIsEmpty()]큐가 비어 있나요? %s\n", CQueIsEmpty(cqueue) ? "true" : "false");
	
	Element e1 = { 24, "김철수" };
	Element e2 = { 23, "박영희" };
	Element e3 = { 21, "이진우" };
	Element e4 = { 45, "홍길동" };
	Element e5 = { 24, "김승규" };
	Element e6 = { 24, "박성겸" };
	Element e7 = { 24, "진우진" };
	Element e8 = { 24, "문도언" };
	Element e9 = { 24, "한윤학" };
	Element e10 = { 24, "이현택" };

	printf("\n\n\t[CQueEnqueue()]데이터 추가\n\n");
	CQueEnqueue(cqueue, e1);
	CQueEnqueue(cqueue, e2);
	CQueEnqueue(cqueue, e3);
	CQueEnqueue(cqueue, e4);
	CQueEnqueue(cqueue, e5);
	CQueEnqueue(cqueue, e6);
	CQueEnqueue(cqueue, e7);
	CQueEnqueue(cqueue, e8);
	CQueEnqueue(cqueue, e9);
	CQueEnqueue(cqueue, e10);

	printf("\n\n\t[CQueIsEmpty()]큐가 비어 있나요? %s\n", CQueIsEmpty(cqueue) ? "true" : "false");

	printf("\n\n\t[CQuePeek()]가장 먼저 나오는 데이터 출력\n\n");
	Element tmp;
	CQuePeek(cqueue, &tmp);
	printNameAge(&tmp);

	printf("\n\n\t[CQuePrint()]Queue의 모든 요소 출력\n\n");
	CQuePrint(cqueue, printNameAge);

	printf("\n\n\t[CQueDequeue()]데이터 세 개 삭제 후 다시 세 개 추가\n\n");
	Element tmp2;
	for (int i = 0; i < 3; i++)
		CQueDequeue(cqueue, &tmp2);
	printf("데이터 세 개 삭제 후 상태\n");
	CQuePrint(cqueue, printNameAge);

	printf("\n확보된 공간에 데이터 세 개 추가\n");
	CQueEnqueue(cqueue, e8);
	CQueEnqueue(cqueue, e9);
	CQueEnqueue(cqueue, e10);
	printf("\n현재 상태 출력\n");
	CQuePrint(cqueue, printNameAge);

	printf("\n\n\t큐가 빌 때까지 모든 요소 꺼내어 출력\n\n");
	while (CQueIsEmpty(cqueue) != TRUE) {
		Element tmp3;
		CQueDequeue(cqueue, &tmp3);
		printNameAge(&tmp3);
	}
	printf("\n\t[CQueIsEmpty()]큐가 비어 있나요? %s\n", CQueIsEmpty(cqueue) ? "true" : "false");

	printf("\n\n\t[CQueDestroy()]큐의 메모리 해제\n\n");
	CQueDestroy(cqueue);
	return 0;
}

모든 함수를 테스트 하는 방향으로 작성했다. 또한 내부적으로 바뀌었을 뿐 큐의 기능을 그대로 수행해야 하므로 지난번 구현한 큐와 비슷하게 구성하였다. 추가로 테스트하고자 하는 함수의 이름을 출력하였다.

실행 결과

실행 결과는 아래와 같다.

Visual Leak Detector read settings from: C:\Program Files (x86)\Visual Leak Detector\vld.ini
Visual Leak Detector Version 2.5.1 installed.

        [CQueIsEmpty()]큐가 비어 있나요? true


        [CQueEnqueue()]데이터 추가

{ 24, 김철수 } 저장 완료
{ 23, 박영희 } 저장 완료
{ 21, 이진우 } 저장 완료
{ 45, 홍길동 } 저장 완료
{ 24, 김승규 } 저장 완료
{ 24, 박성겸 } 저장 완료
{ 24, 진우진 } 저장 완료
데이터를 저장할 수 없습니다. 공간이 부족합니다.
데이터를 저장할 수 없습니다. 공간이 부족합니다.
데이터를 저장할 수 없습니다. 공간이 부족합니다.


        [CQueIsEmpty()]큐가 비어 있나요? false


        [CQuePeek()]가장 먼저 나오는 데이터 출력

Name: 김철수    Age: 24


        [CQuePrint()]Queue의 모든 요소 출력

Elements in Circular Queue are:
Name: 김철수    Age: 24
Name: 박영희    Age: 23
Name: 이진우    Age: 21
Name: 홍길동    Age: 45
Name: 김승규    Age: 24
Name: 박성겸    Age: 24
Name: 진우진    Age: 24


        [CQueDequeue()]데이터 세 개 삭제 후 다시 세 개 추가

데이터 세 개 삭제 후 상태
Elements in Circular Queue are:
Name: 홍길동    Age: 45
Name: 김승규    Age: 24
Name: 박성겸    Age: 24
Name: 진우진    Age: 24

확보된 공간에 데이터 세 개 추가
{ 24, 문도언 } 저장 완료
{ 24, 한윤학 } 저장 완료
{ 24, 이현택 } 저장 완료

현재 상태 출력
Elements in Circular Queue are:
Name: 홍길동    Age: 45
Name: 김승규    Age: 24
Name: 박성겸    Age: 24
Name: 진우진    Age: 24
Name: 문도언    Age: 24
Name: 한윤학    Age: 24
Name: 이현택    Age: 24


        큐가 빌 때까지 모든 요소 꺼내어 출력

Name: 홍길동    Age: 45
Name: 김승규    Age: 24
Name: 박성겸    Age: 24
Name: 진우진    Age: 24
Name: 문도언    Age: 24
Name: 한윤학    Age: 24
Name: 이현택    Age: 24

        [CQueIsEmpty()]큐가 비어 있나요? true


        [CQueDestroy()]큐의 메모리 해제

No memory leaks detected.
Visual Leak Detector is now exiting.

C:\Users\Hotaek\Desktop\2학년 여름\DS_Review\3_Queue\CircularQueue\CircularQueue\Debug\CircularQueue.exe(프로세스 23912 개)이(가) 종료되었습니다(코드: 0개).
이 창을 닫으려면 아무 키나 누르세요...