자료구조란 무엇인가?
자료구조(Data Structure)는 데이터를 체계적이고 효율적인 방식으로 조직화하여 모아 놓은 것을 의미합니다. 자료구조는 크게 두 가지 유형으로 나눌 수 있습니다.
선형 자료구조(Linear Data Structure) – 데이터가 일렬로 나열된 형태로 저장됩니다. 대표적인 예로 배열, 구조체, 스택, 큐, 연결 리스트 등이 있습니다.
비선형 자료구조(Nonlinear Data Structure) – 데이터가 계층적인 형태로 저장됩니다. 대표적인 예로 트리, 그래프, 집합, 테이블 등이 있습니다.
큐(Queue)란?
큐는 선형 자료구조의 하나로, 삽입(insertion)은 뒤쪽 끝(rear)에서 이루어지고 삭제(deletion)는 앞쪽 끝(front)에서 이루어집니다.
큐의 핵심 원리는 FIFO(First In First Out, 선입선출)입니다. 즉, 가장 먼저 들어간 데이터가 가장 먼저 나오게 되며, 줄을 서서 순서를 기다리는 일상의 대기열과 같은 동작 방식입니다.
주요 연산
- 삽입(Insert) – 큐에 새로운 요소를 추가합니다.
- 삭제(Delete) – 큐에서 기존 요소를 제거합니다.
예외 상황
큐 오버플로우(Queue Overflow) – 이미 가득 찬 큐에 요소를 삽입하려고 시도할 때 발생합니다.
큐 언더플로우(Queue Underflow) – 비어 있는 큐에서 요소를 삭제하려고 시도할 때 발생합니다.
삽입 알고리즘
다음은 큐에 요소를 삽입하는 insert() 알고리즘입니다.
1단계: 큐 오버플로우 여부를 먼저 확인합니다.
if (r == n)
printf("Queue overflow")2단계: 오버플로우가 아니라면 큐에 요소를 삽입하고 rear 값을 증가시킵니다.
q[r] = item r++
C 언어 구현 예제
다음은 큐에 요소를 삽입하는 전체 C 프로그램입니다.
#include <stdio.h>
#define MAX 50
void insert();
int array[MAX];
int rear = - 1;
int front = - 1;
main(){
int add_item;
int choice;
while (1){
printf("1.Insert element to queue \n");
printf("2.Display elements of queue \n");
printf("3.Quit \n");
printf("Enter your choice : ");
scanf("%d", &choice);
switch (choice){
case 1:
insert();
break;
case 2:
display();
break;
case 3:
exit(1);
default:
printf("Wrong choice \n");
}
}
}
void insert(){
int add_item;
if (rear == MAX - 1)
printf("Queue Overflow \n");
else{
if (front == - 1)
/*If queue is initially empty */
front = 0;
printf("Inset the element in queue : ");
scanf("%d", &add_item);
rear = rear + 1;
array[rear] = add_item;
}
}
void display(){
int i;
if (front == - 1)
printf("Queue is empty \n");
else{
printf("Queue is : \n");
for (i = front; i <= rear; i++)
printf("%d ", array[i]);
printf("\n");
}
}실행 결과
위 프로그램을 컴파일하여 실행하면 다음과 같은 결과가 출력됩니다.
1.Insert element to queue 2.Display elements of queue 3.Quit Enter your choice: 1 Inset the element in queue: 34 1.Insert element to queue 2.Display elements of queue 3.Quit Enter your choice: 1 Inset the element in queue: 24 1.Insert element to queue 2.Display elements of queue 3.Quit Enter your choice: 2 Queue is: 34 24 1.Insert element to queue 2.Display elements of queue 3.Quit Enter your choice: 3
메뉴에서 1을 선택하면 큐에 요소를 삽입하고, 2를 선택하면 현재 큐에 저장된 모든 요소를 화면에 출력하며, 3을 선택하면 프로그램이 종료됩니다. 위 실행 결과에서 34와 24를 차례대로 삽입한 뒤 큐를 출력하면 입력한 순서 그대로 "34 24"가 출력되는 것을 확인할 수 있습니다. 이는 큐의 핵심 특성인 FIFO(선입선출) 방식이 그대로 적용되었음을 보여줍니다.