자료구조(Data Structure)란 데이터를 체계적으로 조직화하여 관리하는 집합을 의미합니다. 자료구조는 크게 두 가지 유형으로 나눌 수 있습니다.
- 선형 자료구조(Linear Data Structure) – 데이터가 일렬로 순차적으로 배열되는 구조입니다. 예: 배열(Array), 구조체(Structure), 스택(Stack), 큐(Queue), 연결 리스트(Linked List)
- 비선형 자료구조(Nonlinear Data Structure) – 데이터가 계층적(Hierarchical)으로 구성되는 구조입니다. 예: 트리(Tree), 그래프(Graph), 집합(Set), 테이블(Table)
큐(Queue)란?
큐는 선형 자료구조의 한 종류로, 뒤쪽(Rear) 끝에서 요소를 삽입하고 앞쪽(Front) 끝에서 요소를 삭제하는 구조입니다. 실생활에서 줄을 서서 차례를 기다리는 모습과 유사하여 '대기열'이라고도 부릅니다.
큐의 핵심 원리는 FIFO(First In First Out, 선입선출) 방식입니다. 즉, 가장 먼저 들어간 데이터가 가장 먼저 나오게 됩니다.
주요 연산
- 삽입(Insert / Enqueue) – 큐에 새로운 요소를 추가하는 연산입니다.
- 삭제(Delete / Dequeue) – 큐에서 요소를 제거하는 연산입니다.
예외 상황
- 큐 오버플로(Queue Overflow) – 이미 가득 찬 큐에 요소를 삽입하려고 시도할 때 발생합니다.
- 큐 언더플로(Queue Underflow) – 비어 있는 큐에서 요소를 삭제하려고 시도할 때 발생합니다.
핵심 알고리즘
1. 삽입(Insertion) 알고리즘
먼저 큐 오버플로 여부를 확인합니다.
if (r==n)
printf ("Queue overflow")오버플로가 아니라면 큐에 요소를 삽입합니다.
q[r] = item r++
2. 삭제(Deletion) 알고리즘
먼저 큐 언더플로 여부를 확인합니다.
if (f==r)
printf ("Queue under flow")언더플로가 아니라면 큐에서 요소를 삭제합니다.
item = q[f] f++
3. 출력(Display) 알고리즘
먼저 큐가 비어 있는지 확인합니다.
if (f==r)
printf("Queue is empty")비어 있지 않다면 앞쪽 인덱스 'f'부터 뒤쪽 인덱스 'r'까지 모든 요소를 출력합니다.
for(i=f; i<r; i++)
printf ("%d", q[i]);C 프로그램 구현
다음은 배열을 사용하여 큐를 구현한 C 프로그램입니다.
#include<limits.h>
#include<stdio.h>
#include <stdlib.h>
struct Queue {
int front, rear, size;
unsigned capacity;
int* array;
};
struct Queue* createQueue(unsigned capacity){
struct Queue* queue = (struct Queue*)malloc(
sizeof(struct Queue));
queue->capacity = capacity;
queue->front = queue->size = 0;
queue->rear = capacity - 1;
queue->array = (int*)malloc(
queue->capacity * sizeof(int));
return queue;
}
// 큐가 가득 찬 경우
int isFull(struct Queue* queue){
return (queue->size == queue->capacity);
}
// 큐가 비어 있는 경우
int isEmpty(struct Queue* queue){
return (queue->size == 0);
}
void Equeue(struct Queue* queue, int item){
if (isFull(queue))
return;
queue->rear = (queue->rear + 1)
% queue->capacity;
queue->array[queue->rear] = item;
queue->size = queue->size + 1;
printf("%d entered into queue\n", item);
}
int Dqueue(struct Queue* queue){
if (isEmpty(queue))
return INT_MIN;
int item = queue->array[queue->front];
queue->front = (queue->front + 1)
% queue->capacity;
queue->size = queue->size - 1;
return item;
}
// 큐의 맨 앞(front) 요소 확인 함수
int front(struct Queue* queue){
if (isEmpty(queue))
return INT_MIN;
return queue->array[queue->front];
}
// 큐의 맨 뒤(rear) 요소 확인 함수
int rear(struct Queue* queue){
if (isEmpty(queue))
return INT_MIN;
return queue->array[queue->rear];
}
int main(){
struct Queue* queue = createQueue(1000);
Equeue(queue, 100);
Equeue(queue, 200);
Equeue(queue, 300);
Equeue(queue, 400);
printf("%d is deleted element from queue\n\n",
Dqueue(queue));
printf("1st item in queue is %d\n", front(queue));
printf("last item in queue %d\n", rear(queue));
return 0;
}실행 결과
위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.
100 entered into queue 200 entered into queue 300 entered into queue 400 entered into queue 100 is deleted element from queue 1st item in queue is 200 last item in queue 400
실행 결과를 보면 FIFO(선입선출) 원리에 따라 가장 먼저 삽입된 100이 가장 먼저 삭제되었으며, 현재 큐의 맨 앞 요소는 200, 맨 뒤 요소는 400임을 확인할 수 있습니다.