연결 리스트(Linked List)를 사용하여 큐(Queue)를 구현하면 배열 기반 구현에서 발생할 수 있는 큐 오버플로우(Queue Overflow)와 큐 언더플로우(Queue Underflow) 문제를 효과적으로 방지할 수 있습니다. 연결 리스트는 동적 메모리 할당을 기반으로 하기 때문에 큐의 크기 제한 없이 유연하게 데이터를 관리할 수 있습니다.
C 프로그래밍 언어에서 연결 리스트를 활용한 큐에서 수행되는 주요 연산은 다음과 같습니다.
- 삽입(Insert)
- 삭제(Delete)
삽입(Insertion)
새로운 노드를 큐의 뒤쪽(rear)에 추가하는 삽입 연산의 문법은 다음과 같습니다.
문법
&item :
Newnode = (node*) mallac (sizeof (node));
newnode ->data = item;
newnode ->link = NULL;
if ((front = = NULL) || (rear = = NULL)){
front= newnode;
rear = newnode;
}else{
Rear->link = newnode;
rear = newnode;
}
위 코드는 먼저 새 노드에 메모리를 할당하고 데이터를 저장한 뒤, 큐가 비어 있는 경우 front와 rear를 모두 새 노드로 설정합니다. 큐에 이미 요소가 있다면 기존 rear 노드의 링크를 새 노드에 연결하고 rear 포인터를 갱신합니다.
삭제(Deletion)
큐의 앞쪽(front)에서 요소를 제거하는 삭제 연산의 문법은 다음과 같습니다.
문법
if ((front= = NULL))
printf("Deletion is not possible, Queue is empty");
else{
temp = front;
front = front ->link;
free (temp);
}
먼저 큐가 비어 있는지 확인한 후, 비어 있지 않다면 front 노드를 임시 포인터에 저장하고 front를 다음 노드로 이동시킨 뒤 기존 노드의 메모리를 해제합니다.
출력(Display)
큐에 저장된 모든 요소를 화면에 출력하는 연산의 문법은 다음과 같습니다.
문법
while (front! = NULL){
printf("%d", front ->data);
front = front->link;
}전체 프로그램
다음은 연결 리스트를 사용하여 큐를 구현한 C 프로그램입니다. 삽입(enqueue), 삭제(dequeue), 출력(display), front 요소 확인 기능을 메뉴 형태로 제공합니다.
#include <stdio.h>
#include <stdlib.h>
struct node{
int info;
struct node *ptr;
}*front,*rear,*temp,*front1;
int frontelement();
void enq(int data);
void deq();
void display();
void create();
int count = 0;
void main(){
int no, ch, e;
printf("\n 1 - Enqueue");
printf("\n 2 - Dequeue");
printf("\n 3 - Display");
printf("\n 4 - Exit");
printf("\n 5-front");
create();
while (1){
printf("\n Enter choice : ");
scanf("%d", &ch);
switch (ch){
case 1:
printf("Enter data : ");
scanf("%d", &no);
enq(no);
break;
case 2:
deq();
break;
case 3:
display();
break;
case 4:
exit(0);
break;
case 5:
e = frontelement();
if (e != 0)
printf("Front element : %d", e);
else
printf("\n No front element in Queue");
break;
default:
printf("Wrong choice, Try again ");
break;
}
}
}
void enq(int data){
if (rear == NULL){
rear = (struct node *)malloc(1*sizeof(struct node));
rear->ptr = NULL;
rear->info = data;
front = rear;
}else{
temp=(struct node *)malloc(1*sizeof(struct node));
rear->ptr = temp;
temp->info = data;
temp->ptr = NULL;
rear = temp;
}
count++;
}
void display(){
front1 = front;
if ((front1 == NULL) && (rear == NULL)){
printf("Queue is empty");
return;
}
while (front1 != rear){
printf("%d ", front1->info);
front1 = front1->ptr;
}
if (front1 == rear)
printf("%d", front1->info);
}
void deq(){
front1 = front;
if (front1 == NULL){
printf("\n Error");
return;
}
else
if (front1->ptr != NULL){
front1 = front1->ptr;
printf("\n Dequeued value : %d", front->info);
free(front);
front = front1;
}else{
printf("\n Dequeued value : %d", front->info);
free(front);
front = NULL;
rear = NULL;
}
count--;
}
int frontelement(){
if ((front != NULL) && (rear != NULL))
return(front->info);
else
return 0;
}
실행 결과
위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.
1 - Enque
2 - Deque
3 – Display
4 - Exit
5 - Front element
Enter choice: 1
Enter data: 14
Enter choice: 1
Enter data: 85
Enter choice: 1
Enter data: 38
Enter choice: 5
Front element: 14
Enter choice: 3
14 85 38
Enter choice: 2
Dequed value: 14
Enter choice: 3
Enter choice: 4
실행 결과를 보면 14, 85, 38 순서로 데이터를 삽입한 후 front 요소인 14가 정상적으로 확인되고, 삭제 연산 수행 시 가장 먼저 들어간 14가 제거되는 것을 알 수 있습니다. 이는 큐의 FIFO(First In, First Out) 특성이 연결 리스트 기반 구현에서도 그대로 유지됨을 보여줍니다.