큐 (Queue)
큐는 선입선출(FIFO, First-In-First-Out) 방식으로 작동하는 자료구조로
먼저 들어간 데이터가 먼저 나오는 구조로, 실생활에서 줄서기와 같은 상황을 떠올리면 쉽게 이해할 수 있습니다.
큐의 ADT (추상 자료형)
void QueueInit(Queue * pq);
// 큐 초기화
int QIsEmpty(Queue * pq);
// 큐가 비어 있는지 확인
void Enqueue(Queue * pq, Data data);
// 큐에 데이터 삽입
Data Dequeue(Queue * pq);
// 큐에서 데이터 삭제 및 반환
Data QPeek(Queue * pq);
// 큐에서 삭제하지 않고 데이터 반환큐의 구현
큐는 배열 기반과 연결 리스트 기반으로 구현할 수 있습니다.
배열 기반 큐
배열을 이용하여 큐를 구현할 수 있지만, 이 방식에서는 배열의 크기가 고정되어 있고, 데이터가 계속 추가되면 배열의 끝에 도달할 수 있습니다.
이때 배열이 남아 있더라도 새로운 데이터를 추가할 수 없는 문제가 생깁니다. 이와 같은 문제를 해결하기 위해 원형 큐가 존재합니다.
배열 기반 큐의 C 구현
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define QUEUE_LEN 100
typedef int Data;
typedef struct _queue {
int front;
int rear;
Data queArr[QUEUE_LEN];
} Queue;
void QueueInit(Queue * pq) {
pq->front = 0;
pq->rear = 0;
}
int QIsEmpty(Queue * pq) {
if (pq->front == pq->rear) return TRUE;
return FALSE;
}
void Enqueue(Queue * pq, Data data) {
if ((pq->rear + 1) % QUEUE_LEN == pq->front) {
printf("Queue is Full!\n");
return;
}
pq->rear = (pq->rear + 1) % QUEUE_LEN;
pq->queArr[pq->rear] = data;
}
Data Dequeue(Queue * pq) {
if (QIsEmpty(pq)) {
printf("Queue is Empty!\n");
exit(-1);
}
pq->front = (pq->front + 1) % QUEUE_LEN;
return pq->queArr[pq->front];
}연결 리스트 기반 큐
연결 리스트를 사용하면 큐의 크기 제한 없이 데이터를 동적으로 저장할 수 있습니다.
큐의 데이터가 동적으로 증가하고 감소하므로, 메모리를 효율적으로 사용할 수 있는 장점이 있습니다.
연결 리스트 기반 큐의 C 구현
#include <stdio.h>
#include <stdlib.h>
typedef int Data;
typedef struct _node {
Data data;
struct _node * next;
} Node;
typedef struct _lQueue {
Node * front;
Node * rear;
} Queue;
void QueueInit(Queue * pq) {
pq->front = NULL;
pq->rear = NULL;
}
int QIsEmpty(Queue * pq) {
if (pq->front == NULL) return TRUE;
return FALSE;
}
void Enqueue(Queue * pq, Data data) {
Node * newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = NULL;
if (QIsEmpty(pq)) {
pq->front = newNode;
pq->rear = newNode;
} else {
pq->rear->next = newNode;
pq->rear = newNode;
}
}
Data Dequeue(Queue * pq) {
if (QIsEmpty(pq)) {
printf("Queue is Empty!\n");
exit(-1);
}
Node * delNode = pq->front;
Data retData = delNode->data;
pq->front = pq->front->next;
free(delNode);
return retData;
}원형 큐 (Circular Queue)
원형 큐는 배열 기반 큐의 단점을 해결하는 구조입니다.
배열의 끝에 도달하면 다시 배열의 처음으로 돌아가 데이터가 저장되므로 배열의 공간을 효율적으로 사용할 수 있습니다.
원형 큐의 특징
- 큐가 비어 있는 상태와 가득 찬 상태를 구별하기 위해서, 큐 배열의 크기보다 하나 작은 크기만큼만 데이터가 저장됩니다.
- front와 rear가 계속 순환하므로 큐가 가득 차거나 비었는지 판단할 수 있어야 합니다.
원형 큐의 C 구현
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define QUEUE_LEN 100
typedef int Data;
typedef struct _cQueue {
int front;
int rear;
Data queArr[QUEUE_LEN];
} Queue;
void QueueInit(Queue * pq) {
pq->front = 0;
pq->rear = 0;
}
int QIsEmpty(Queue * pq) {
if (pq->front == pq->rear) return TRUE;
return FALSE;
}
void Enqueue(Queue * pq, Data data) {
if ((pq->rear + 1) % QUEUE_LEN == pq->front) {
printf("Queue is Full!\n");
return;
}
pq->rear = (pq->rear + 1) % QUEUE_LEN;
pq->queArr[pq->rear] = data;
}
Data Dequeue(Queue * pq) {
if (QIsEmpty(pq)) {
printf("Queue is Empty!\n");
exit(-1);
}
pq->front = (pq->front + 1) % QUEUE_LEN;
return pq->queArr[pq->front];
}논리 정리
-
큐는 데이터를 선입선출 방식으로 처리하는 자료구조로, 가장 먼저 들어온 데이터가 먼저 나가게 됩니다.
-
배열 기반 큐는 메모리 크기가 고정되며, 데이터 추가 시 배열의 끝에 도달하면 더 이상 삽입할 수 없는 단점이 있습니다.
-
연결 리스트 기반 큐는 동적 메모리 할당을 통해 크기 제한 없이 큐를 구현할 수 있어 유연합니다.
-
원형 큐는 배열 기반 큐의 단점을 해결하여 배열의 시작과 끝이 순환하며 메모리를 효율적으로 사용합니다.
큐의 사용 사례
큐는 작업 예약 시스템이나 데이터 처리 파이프라인과 같은 상황에서 자주 사용됩니다.
