큐(Queue)는 여러 개의 요소를 담는 추상 자료구조로, FIFO(First In First Out, 선입선출) 방식으로 동작합니다. 즉, 가장 먼저 삽입된 요소가 가장 먼저 삭제되며, 반대로 말하면 가장 최근에 추가된 요소가 마지막에 제거됩니다.
다음은 연결 리스트(Linked List)를 이용해 큐를 구현하는 C++ 프로그램입니다.
예제 코드
#include <iostream>
using namespace std;
struct node {
int data;
struct node *next;
};
struct node* front = NULL;
struct node* rear = NULL;
struct node* temp;
void Insert() {
int val;
cout<<"Insert the element in queue : "<<endl;
cin>>val;
if (rear == NULL) {
rear = (struct node *)malloc(sizeof(struct node));
rear->next = NULL;
rear->data = val;
front = rear;
} else {
temp=(struct node *)malloc(sizeof(struct node));
rear->next = temp;
temp->data = val;
temp->next = NULL;
rear = temp;
}
}
void Delete() {
temp = front;
if (front == NULL) {
cout<<"Underflow"<<endl;
return;
}
else
if (temp->next != NULL) {
temp = temp->next;
cout<<"Element deleted from queue is : "<<front->data<<endl;
free(front);
front = temp;
} else {
cout<<"Element deleted from queue is : "<<front->data<<endl;
free(front);
front = NULL;
rear = NULL;
}
}
void Display() {
temp = front;
if ((front == NULL) && (rear == NULL)) {
cout<<"Queue is empty"<<endl;
return;
}
cout<<"Queue elements are: ";
while (temp != NULL) {
cout<<temp->data<<" ";
temp = temp->next;
}
cout<<endl;
}
int main() {
int ch;
cout<<"1) Insert element to queue"<<endl;
cout<<"2) Delete element from queue"<<endl;
cout<<"3) Display all the elements of queue"<<endl;
cout<<"4) Exit"<<endl;
do {
cout<<"Enter your choice : "<<endl;
cin>>ch;
switch (ch) {
case 1: Insert();
break;
case 2: Delete();
break;
case 3: Display();
break;
case 4: cout<<"Exit"<<endl;
break;
default: cout<<"Invalid choice"<<endl;
}
} while(ch!=4);
return 0;
}실행 결과
위 프로그램을 실행하면 다음과 같은 결과를 확인할 수 있습니다.
1) Insert element to queue 2) Delete element from queue 3) Display all the elements of queue 4) Exit Enter your choice : 1 Insert the element in queue : 4 Enter your choice : 1 Insert the element in queue : 3 Enter your choice : 1 Insert the element in queue : 5 Enter your choice : 2 Element deleted from queue is : 4 Enter your choice : 3 Queue elements are : 3 5 Enter your choice : 7 Invalid choice Enter your choice : 4 Exit
코드 상세 설명
1. Insert() 함수 – 요소 삽입
Insert() 함수는 큐에 새로운 요소를 삽입하는 역할을 합니다. rear 포인터가 NULL이라면 큐가 비어 있는 상태이므로 노드를 하나 생성해 값을 저장하고, front와 rear가 모두 이 노드를 가리키도록 합니다. 큐에 이미 요소가 있다면 rear 뒤에 새 노드를 연결한 뒤 rear를 새 노드로 갱신합니다.
void Insert() {
int val;
cout<<"Insert the element in queue : "<<endl;
cin>>val;
if (rear == NULL) {
rear = (struct node *)malloc(sizeof(struct node));
rear->next = NULL;
rear->data = val;
front = rear;
} else {
temp=(struct node *)malloc(sizeof(struct node));
rear->next = temp;
temp->data = val;
temp->next = NULL;
rear = temp;
}
}2. Delete() 함수 – 요소 삭제
Delete() 함수는 큐에서 요소를 삭제합니다. front가 NULL이면 큐가 비어 있다는 뜻으로, 이를 언더플로(Underflow) 상황이라고 합니다. 큐에 요소가 하나뿐이라면 해당 요소를 삭제한 후 front와 rear를 모두 NULL로 초기화합니다. 그 외의 경우에는 front가 가리키는 요소를 삭제하고, front를 다음 노드로 이동시킵니다.
void Delete() {
temp = front;
if (front == NULL) {
cout<<"Underflow"<<endl;
return;
} else
if (temp->next != NULL) {
temp = temp->next;
cout<<"Element deleted from queue is : "<<front->data<<endl;
free(front);
front = temp;
} else {
cout<<"Element deleted from queue is : "<<front->data<<endl;
free(front);
front = NULL;
rear = NULL;
}
}3. Display() 함수 – 전체 출력
Display() 함수는 큐의 모든 요소를 화면에 출력합니다. front와 rear가 모두 NULL이면 큐가 비어 있음을 알리고 종료하며, 그렇지 않으면 temp 변수를 활용한 while 루프를 통해 각 노드의 데이터를 순서대로 출력합니다.
void Display() {
temp = front;
if ((front == NULL) && (rear == NULL)) {
cout<<"Queue is empty"<<endl;
return;
}
cout<<"Queue elements are: ";
while (temp != NULL) {
cout<<temp->data<<" ";
temp = temp->next;
}
cout<<endl;
}4. main() 함수 – 메뉴 처리
main() 함수는 사용자에게 메뉴를 보여주고, 삽입·삭제·출력 중 원하는 작업을 선택하도록 합니다. switch 문을 통해 선택값에 따라 적절한 함수를 호출하며, 잘못된 번호를 입력하면 "Invalid choice" 메시지를 출력합니다. 사용자가 4번(종료)을 선택할 때까지 do-while 루프가 계속 반복됩니다.
int main() {
int ch;
cout<<"1) Insert element to queue"<<endl;
cout<<"2) Delete element from queue"<<endl;
cout<<"3) Display all the elements of queue"<<endl;
cout<<"4) Exit"<<endl;
do {
cout<<"Enter your choice : "<<endl;
cin>>ch;
switch (ch) {
case 1: Insert();
break;
case 2: Delete();
break;
case 3: Display();
break;
case 4: cout<<"Exit"<<endl;
break;
default: cout<<"Invalid choice"<<endl;
}
} while(ch!=4);
return 0;
}마무리 및 참고 사항
이처럼 연결 리스트를 활용하면 배열 기반 큐와 달리 크기 제한 없이 유동적으로 큐를 운영할 수 있습니다. 다만 위 코드는 C 스타일의 malloc과 free를 사용하고 있는데, C++에서는 new와 delete를 사용하는 것이 더 안전하고 관례에 맞습니다. 또한 실무에서는 메모리 누수를 방지하기 위해 소멸자에서 남아 있는 노드를 모두 해제하는 것이 좋습니다.