Queue
이 글은 기존에 다룬 Dynamic Array에 대한 개념과 소스 코드를 포함하고 있습니다.
이에 대한 정보가 필요하다면 아래를 참고해주세요. 아래 링크에서 Ctrl+F로 필요한 함수만 찾아볼 수 있습니다.
[Data Structure] 동적 배열(Dynamic Array) 구현하기 (새 창)
Queue란?
큐(Queue)는 먼저 들어온 데이터가 먼저 나가는 선입선출(FIFO: First-In, First-Out) 형태의 자료구조이다.
큐가 사용되는 예로는 프린터의 인쇄 대기열, CPU 작업 스케쥴링 등이 있다. 스택의 예시 설명에는 언급하지 않았지만 나중에 트리를 구현할 때 순환 구조를 채택하는 대신 큐나 스택을 사용하여 구현할 수도 있다. 트리 진도 때 작성할 예정이다.
구현 방법
이번에도 스택과 마찬가지로 이전에 구현한 Dynamic Array를 활용하여 큐를 구현할 것이다. 따라서 큐는 구조체로 정의되며 멤버 변수로는 Dynamic Array와 인덱스를 가리키는 int형 변수 두 가지로 구성된다.
기존의 DataType.h, DynamicArray.c, DynamicArray.h 그리고 main.c를 제외하면 Queue.h와 Queue.c 총 2개의 헤더/C파일이 추가되었다.
DataType.h의 내용은 수정하지 않았으며, DynamicArray의 배열은 기존엔 포인터로 이루어진 배열 즉, 이중 포인터로 선언하였으나 이번에는 편의상 배열로 선언하였다. 따라서 동적 배열에 주소 값이 저장되지 않고 요소의 데이터가 직접 저장되는 방식으로 변경되었다.
DynamicArray.h
동적 배열에 대한 코드는 Element* 배열(이중포인터)에서 Element 배열로 바뀌고 이에 관련된 부분이 사소하게 수정된 것이 있으나 이에 대한 모든 내용을 글로 작성할 필요는 없는 것 같다.
다만 이번에 DynamicArray.h에 추가된 내용이 있다. 함수 포인터에 대한 정의이다.
typedef void(*PrintFunc)(Element* e);반환 값을 void, 매개 변수를 Element*로 받는 함수를 PrintFunc라 정의하였다. 그 이유는 이러한 함수 없이 스택을 몇 번 활용해보니 데이터를 출력하는데 불편함이 있었기 때문이다. 문제 상황에 따라 DataType.h의 Element에 대한 정의가 바뀌면 출력 방법도 바뀌어야 하기 때문이다.
이러한 함수 포인터를 정의하면 데이터를 출력할 때 Element를 출력할 수 있는 함수를 main.c에서 정의하여 QuePrint(queue, func) 형태로 호출하면 되기 때문이다.
추가할 부분이 있는 것은 마찬가지이지 않느냐고 생각할 수 있지만 Queue의 코드 자체를 수정하는 것과 Queue의 코드를 수정하지 않고 출력할 수 있는 방법을 제공하여 출력이 가능하게 하는 것은 같지 않다.
Queue.h를 사용하는 개발자는 Queue의 코드에 접근할 필요 없이 자신의 용도에 맞는 출력 함수를 정의해 전달하기만 하면 된다.
Queue.h
큐의 추상 자료형(ADT)에 대한 헤더 파일이다. 구조체 Queue에 대한 정의와 필요한 함수에 대한 프로토 타입을 포함한다.
#pragma once
#include "DynamicArray.h"
typedef struct {
DynamicArray* darr;
int index; // 데이터를 직접 가리키는 변수
} Queue;
Queue* QueCreate();
int QueIsEmpty(Queue* queue);
int QueEnqueue(Queue* queue, Element e);
int QueDequeue(Queue* queue, Element* e);
int QuePeek(Queue* queue, Element* e);
void QuePrint(Queue* queue, PrintFunc func);
void QueDestroy(Queue* queue);Queue.c
Queue.h의 함수가 실제로 정의되는 파일이다. 함수 별로 살펴보도록 한다.
헤더 파일
#include <stdlib.h>
#include "Queue.h"동적 할당과 관련된 함수가 필요하기 때문에 stdlib.h를 include해준다. Queue.h도 필요하다.
Queue* QueCreate()
큐를 생성하는 함수이다. Queue가 요구하는 메모리만큼을 할당 받은 후 할당에 성공하면 createDA() 함수를 호출하여 동적 배열도 할당 받는다.
Queue* QueCreate()
{
Queue* queue = (Queue*)malloc(sizeof(Queue));
if (queue != NULL) {
queue->darr = createDA();
if (queue->darr == NULL) {
free(queue);
return NULL;
}
else
queue->index = -1; // 이 값이 -1이면 큐는 비어 있는 것으로 취급
}
return queue;
}만약 큐는 할당 받았지만 큐를 구성하는 동적 배열을 할당 받지 못했다면 큐를 메모리에서 해제한 뒤에 NULL 값을 반환한다.
QueIsEmpty(Queue* queue)
큐가 비어있는지 검사하는 함수이다.
int QueIsEmpty(Queue* queue)
{
if (queue->index == -1 && queue != NULL) return TRUE;
else return FALSE;
}index는 큐의 데이터를 직접 가리키는 값이기 때문에 이 값이 -1이라면 데이터는 저장되지 않은 것으로 취급한다.
QueEnqueue(Queue* queue, Element e)
큐에 데이터를 저장하는 함수
int QueEnqueue(Queue* queue, Element e)
{
if (queue != NULL) {
if (DAAdd(queue->darr, e)) {
queue->index++;
return TRUE;
}
}
return FALSE;
}동적 배열을 활용하기 때문에 DAAdd() 함수를 호출하여 데이터를 추가한다.
QueDequeue(Queue* queue, Element* e)
큐에서 데이터를 꺼내오는 함수이다. 함수를 호출할 때 꺼낸 데이터를 저장할 변수의 주소를 전달하여 그 위치에 값을 복사한다.
int QueDequeue(Queue* queue, Element* e)
{
if (queue != NULL && QueIsEmpty(queue) != TRUE) {
if (DAGet(queue->darr, 0, e)) {
for (int i = 0; i < queue->index; i++) {
Element tmp;
DAGet(queue->darr, i + 1, &tmp);
DAPut(queue->darr, i, tmp);
}
queue->index--;
return TRUE;
}
}
return FALSE;
}큐는 가장 먼저 저장된 데이터가 가장 먼저 나가야 한다. 따라서 배열 가장 앞의 데이터를 삭제해야 하는데 이를 구현하기 위해 for 문을 통해 배열의 1번째 인덱스를 0번째로, 2번째 인덱스를 1번째로 한 칸씩 당겨와준다.
데이터의 삭제가 있을 때마다 한 칸씩 그것도 포인터가 아니라 데이터 자체를 옮기기 때문에 속도가 느려질 수 밖에 없다. 이에 대한 개선 방법으로 다음 포스팅에서 원형 큐 (Circular Queue)에 대해 알아볼 것이다. 원형 큐를 사용하면 데이터를 매번 한 칸씩 옮겨줄 필요가 없다.
QuePeek(Queue* queue, Element* e)
QueDequeue와 유사하나 데이터를 삭제하지 않고 읽기만 하는 함수이다.
int QuePeek(Queue* queue, Element* e)
{
if (QueIsEmpty(queue) != TRUE) {
if (DAGet(queue->darr, 0, e))
return TRUE;
}
return FALSE;
}QuePrint(Queue* queue, PrintFunc func)
큐에 저장된 데이터를 모두 출력하는 함수이다.
큐이기 때문에 저장된 순서대로 출력한다.
void QuePrint(Queue* queue, PrintFunc func)
{
if (QueIsEmpty(queue) != TRUE) {
Element tmp;
for (int i = 0; i <= queue->index; i++) {
DAGet(queue->darr, i, &tmp);
func(&tmp);
}
}
}QueDestroy(Queue* queue)
동적 할당 받은 큐를 메모리에서 해제하는 함수이다.
void QueDestroy(Queue* queue)
{
if (queue != NULL) {
DADestroy(queue->darr);
free(queue);
}
}역시 DynamicArray.h의 함수를 활용하여 구성하는 것이 바람직하다.
마치며
자료 구조를 처음 배울 때에 느꼈던 점이 생각난다.
자료 구조를 배우기 전까진 '문제 해결을 위한 프로그래밍'이었는데, 자료 구조를 구현하는 일은 '문제 해결을 위한 준비를 위한 프로그래밍' 같은 느낌이었다.
자료 구조를 활용하여 문제를 해결하는 것은 결국 개발자이고, 그렇다면 내가 하는 일은 (나를 포함한) 다른 개발자를 위한 프로그래밍이었다. 그들이 편하게 자료 구조를 사용할 수 있도록 여러 인터페이스를 제공하고 발생할 수 있는 오류를 예측하고, 함수의 정상 작동 여부를 return 값으로 반환하고, 주석을 작성하는 등의 일을 했다.
그런 과정에서 내가 프로그래밍 할 때 C언어의 include던 Python의 import 키워드를 사용하여 불러오는 라이브러리나 프레임워크가 이런 식으로 만들어지겠다는 생각을 할 수 있었다.
