큐(Queue) 데이터 구조 소개
컴퓨터 과학에서 큐(Queue)는 특정 규칙에 따라 데이터를 저장하고 관리하는 추상 데이터 타입입니다. 선형 자료구조의 일종으로, 데이터를 삽입하는 작업은 한쪽 끝에서만 이루어지고, 데이터를 삭제하는 작업은 다른 쪽 끝에서만 이루어지는 특징을 가집니다. 이러한 특성으로 인해 큐는 선입선출(First-In, First-Out, FIFO) 원칙을 따릅니다. 즉, 가장 먼저 큐에 들어온 데이터가 가장 먼저 나갑니다.
- 인큐(Enqueue): 데이터를 큐에 추가하는 작업으로, 이 작업이 일어나는 쪽을 후단(Rear) 또는 꼬리(Tail)라고 합니다.
- 디큐(Dequeue): 데이터를 큐에서 제거하는 작업으로, 이 작업이 일어나는 쪽을 전단(Front) 또는 머리(Head)라고 합니다.
큐의 실생활 활용 예시
큐의 개념은 우리 주변의 다양한 상황에서 찾아볼 수 있습니다. 예를 들어, 은행이나 병원과 같은 공공기관의 대기열 시스템이 대표적인 큐의 예시입니다. 손님들은 도착하는 순서대로 번호표를 뽑고 대기열에 추가됩니다. 창구나 진료실에서 서비스가 완료되면, 대기열의 가장 앞에 있는 손님부터 차례로 호명되어 서비스를 받게 됩니다. 이 과정에서 새로운 손님이 대기열의 가장 뒤에 합류하는 것은 '인큐' 작업에 해당하며, 서비스를 받을 차례가 되어 대기열에서 빠져나오는 것은 '디큐' 작업에 해당합니다. 항상 먼저 도착한 사람이 먼저 서비스를 받는다는 점에서 큐의 FIFO 원칙이 명확하게 적용됩니다.
C 언어를 이용한 큐 구현
큐는 배열이나 링크드 리스트를 사용하여 구현할 수 있습니다. 여기서는 동적 메모리 할당을 활용하는 단일 링크드 리스트 기반의 큐 구현 방법을 살펴보겠습니다.
큐 노드 구조 정의
큐를 구성하는 각 요소를 표현하는 노드 구조체를 먼저 정의합니다. 각 노드는 데이터를 저장하고 다음 노드를 가리키는 포인터를 가집니다.
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
typedef int DataPayload;
// 큐의 각 요소를 나타내는 노드 구조체
typedef struct QueueNode
{
DataPayload itemValue;
struct QueueNode* nextPtr;
} QueueNode;
큐 구조체 정의
큐 전체를 관리하기 위한 구조체입니다. 이 구조체는 큐의 전단(head)과 후단(tail)을 가리키는 포인터, 그리고 큐에 현재 저장된 요소의 개수를 포함합니다. 요소의 개수를 포함함으로써 큐의 크기를 O(1) 시간 복잡도로 알 수 있게 됩니다.
// 큐 자체를 관리하는 구조체
typedef struct MyQueue
{
QueueNode* frontPtr; // 큐의 첫 번째 노드를 가리킴 (전단)
QueueNode* rearPtr; // 큐의 마지막 노드를 가리킴 (후단)
int currentSize; // 큐에 저장된 요소의 개수
} MyQueue;
큐 초기화
새로운 큐를 사용하기 전에 전단과 후단 포인터를 NULL로 설정하고, 크기를 0으로 초기화하는 함수입니다.
void InitializeQueue(MyQueue* qRef)
{
assert(qRef != NULL);
qRef->frontPtr = NULL;
qRef->rearPtr = NULL;
qRef->currentSize = 0;
}
큐 소멸
큐가 더 이상 필요 없을 때, 할당된 모든 노드 메모리를 해제하고 큐를 초기 상태로 되돌리는 함수입니다.
void DeallocateQueue(MyQueue* qRef)
{
assert(qRef != NULL);
QueueNode* tempNode = qRef->frontPtr;
while (tempNode != NULL)
{
QueueNode* nextToFree = tempNode->nextPtr;
free(tempNode);
tempNode = nextToFree;
}
qRef->frontPtr = NULL;
qRef->rearPtr = NULL;
qRef->currentSize = 0;
}
데이터 인큐 (Enqueue)
큐의 후단에 새로운 데이터를 추가하는 연산입니다. 새 노드를 생성하고 데이터를 저장한 후, 현재 후단 노드의 다음으로 연결합니다. 큐가 비어있을 때는 전단과 후단 모두 새 노드를 가리키게 합니다.
void Enqueue(MyQueue* qRef, DataPayload value)
{
assert(qRef != NULL);
QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
if (newNode == NULL)
{
fprintf(stderr, "메모리 할당 실패!\n");
exit(EXIT_FAILURE);
}
newNode->itemValue = value;
newNode->nextPtr = NULL;
if (qRef->rearPtr == NULL) // 큐가 비어있는 경우
{
qRef->frontPtr = newNode;
qRef->rearPtr = newNode;
}
else // 큐에 요소가 있는 경우
{
qRef->rearPtr->nextPtr = newNode;
qRef->rearPtr = newNode;
}
qRef->currentSize++;
}
데이터 디큐 (Dequeue)
큐의 전단에서 데이터를 제거하는 연산입니다. 큐가 비어있지 않음을 확인하고, 전단 노드를 제거합니다. 만약 제거 후 큐가 비게 되면 후단 포인터도 NULL로 설정합니다.
void Dequeue(MyQueue* qRef)
{
assert(qRef != NULL);
if (qRef->frontPtr == NULL) // 큐가 비어있으면 아무것도 할 수 없음
{
fprintf(stderr, "오류: 큐가 비어있습니다. 디큐할 수 없습니다.\n");
return;
}
QueueNode* oldFront = qRef->frontPtr;
qRef->frontPtr = oldFront->nextPtr;
free(oldFront);
if (qRef->frontPtr == NULL) // 마지막 요소가 제거되어 큐가 비게 된 경우
{
qRef->rearPtr = NULL;
}
qRef->currentSize--;
}
큐 전단 요소 조회
큐의 전단에 있는 데이터를 반환하지만, 큐에서 제거하지는 않습니다. 큐가 비어있지 않음을 전제로 합니다.
DataPayload PeekFront(MyQueue* qRef)
{
assert(qRef != NULL);
assert(qRef->frontPtr != NULL); // 큐가 비어있지 않음을 가정
return qRef->frontPtr->itemValue;
}
큐 후단 요소 조회
큐의 후단에 있는 데이터를 반환하지만, 큐에서 제거하지는 않습니다. 큐가 비어있지 않음을 전제로 합니다.
DataPayload PeekRear(MyQueue* qRef)
{
assert(qRef != NULL);
assert(qRef->rearPtr != NULL); // 큐가 비어있지 않음을 가정
return qRef->rearPtr->itemValue;
}
큐가 비어있는지 확인
큐에 데이터가 전혀 없는지 여부를 반환합니다.
bool IsQueueEmpty(MyQueue* qRef)
{
assert(qRef != NULL);
return qRef->frontPtr == NULL; // 또는 qRef->currentSize == 0;
}
큐의 현재 크기 반환
큐에 저장된 요소의 총 개수를 반환합니다.
int GetQueueCurrentSize(MyQueue* qRef)
{
assert(qRef != NULL);
return qRef->currentSize;
}