자료구조란 무엇인가?
자료구조(Data Structure)는 데이터를 체계적이고 구조화된 형태로 조직적으로 관리하는 방식을 의미합니다. 자료구조는 크게 두 가지 유형으로 나눌 수 있습니다.
선형 자료구조(Linear Data Structure) − 데이터가 일렬로 순차적으로 배치되는 구조입니다. 대표적인 예로는 배열(Array), 구조체(Structure), 스택(Stack), 큐(Queue), 연결 리스트(Linked List)가 있습니다.
비선형 자료구조(Nonlinear Data Structure) − 데이터가 계층적 형태로 배치되는 구조입니다. 대표적인 예로는 트리(Tree), 그래프(Graph), 집합(Set), 테이블(Table)이 있습니다.
큐(Queue)란?
큐는 선형 자료구조의 한 종류로, 데이터의 삽입은 뒤쪽(rear)에서 이루어지고 삭제는 앞쪽(front)에서 이루어집니다.
큐는 FIFO(First In First Out, 선입선출) 방식으로 동작합니다. 즉, 먼저 들어간 데이터가 가장 먼저 나오게 됩니다.
주요 연산
- 삽입(Insert) − 큐에 새로운 요소를 추가합니다.
- 삭제(Delete) − 큐에서 요소를 제거합니다.
예외 상황
큐 오버플로우(Queue Overflow) − 이미 가득 찬 큐에 요소를 삽입하려고 할 때 발생합니다.
큐 언더플로우(Queue Underflow) − 비어 있는 큐에서 요소를 삭제하려고 할 때 발생합니다.
핵심 알고리즘
1. 삽입(insert) 알고리즘
- 먼저 큐 오버플로우 여부를 확인합니다.
if (r == n)
printf("Queue overflow")- 오버플로우가 아니라면, 큐에 요소를 삽입합니다.
q[r] = item r++
2. 삭제(delete) 알고리즘
- 먼저 큐 언더플로우 여부를 확인합니다.
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 <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.Delete an element from queue\n");
printf("3.Display elements of queue \n");
printf("4.Quit \n");
printf("Enter your choice : ");
scanf("%d", &choice);
switch (choice){
case 1:
insert();
break;
case 2:
delete();
case 3:
display();
break;
case 4:
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");
}
}
void delete(){
if (front == - 1 || front > rear){
printf("Queue Underflow \n");
return ;
}
else{
printf("Element deleted from queue is : %d\n",array[front]);
front = front + 1;
}
}실행 결과
위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다. 메뉴 번호를 입력하여 원하는 동작을 수행할 수 있습니다.
1.Insert element to queue 2.Delete an element from queue 3.Display elements of queue 4.Quit Enter your choice: 1 Inset the element in queue: 12 1.Insert element to queue 2.Delete an element from queue 3.Display elements of queue 4.Quit Enter your choice: 1 Inset the element in queue: 23 1.Insert element to queue 2.Delete an element from queue 3.Display elements of queue 4.Quit Enter your choice: 1 Inset the element in queue: 34 1.Insert element to queue 2.Delete an element from queue 3.Display elements of queue 4.Quit Enter your choice: 2 Element deleted from queue is: 12 Queue is: 23 34 1.Insert element to queue 2.Delete an element from queue 3.Display elements of queue 4.Quit Enter your choice: 2 Element deleted from queue is: 23 Queue is: 34 1.Insert element to queue 2.Delete an element from queue 3.Display elements of queue 4.Quit Enter your choice: 4