우선순위 큐(Priority Queue)란?
일반적인 큐(Queue)는 FIFO(First-In-First-Out, 선입선출) 방식으로 동작하는 자료구조입니다. 데이터의 삽입은 한쪽 끝인 후단(rear)에서 이루어지고, 삭제는 반대쪽 끝인 전단(front)에서 이루어지며, 가장 먼저 들어간 요소가 가장 먼저 삭제됩니다.
큐의 기본 연산은 다음과 같습니다.
- EnQueue(int data): 후단(rear)에 데이터를 삽입합니다.
- int DeQueue(): 전단(front)에서 데이터를 삭제합니다.
반면 우선순위 큐는 FIFO 규칙을 따르지 않습니다. 대신 각 요소는 긴급도(중요도)에 따라 우선순위를 가지며, 다음 규칙에 따라 처리됩니다.
- 우선순위가 높은 요소는 낮은 요소보다 먼저 처리됩니다.
- 우선순위가 같은 요소들은 FIFO(선입선출) 순서대로 처리됩니다.
클래스 설계
이번 예제에서 구현할 Priority_Queue 클래스의 동작 흐름은 다음과 같습니다.
시작
Priority_Queue 클래스는 아래 함수들을 포함한다.
insert(): 항목과 우선순위를 함께 큐에 삽입한다.
1) 큐가 비어 있으면 큐의 맨 앞에 데이터를 삽입한다.
2) 큐에 노드가 이미 존재하면, 새 노드를 우선순위가 같은 노드들 바로 뒤에,
그리고 새 노드보다 우선순위가 낮은 모든 노드들 앞에 삽입한다.
del(): 큐에서 항목을 삭제한다.
큐가 완전히 비어 있으면 underflow를 출력하고,
그렇지 않으면 전단(front) 요소를 삭제한 후 front를 갱신한다.
끝
C++ 구현 예제
아래 예제는 연결 리스트를 이용해 우선순위 큐를 구현한 것입니다. 각 노드는 데이터(info)와 우선순위(p)를 저장하며, 우선순위 값이 작을수록 먼저 처리됩니다.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
struct n // 노드 선언 {
int p;
int info;
struct n *l;
};
class Priority_Queue {
private:
// front 포인터 f를 선언하고 NULL로 초기화
n *f;
public:
Priority_Queue() // 생성자 {
f = NULL;
}
void insert(int i, int p) {
n *t, *q;
t = new n;
t->info = i;
t->p = p;
if (f == NULL || p < f->p) {
t->l = f;
f = t;
} else {
q = f;
while (q->l != NULL && q->l->p <= p)
q = q->l;
t->l = q->l;
q->l = t;
}
}
void del() {
n *t;
if (f == NULL) // 큐가 비어 있는 경우
cout<<"Queue Underflow\n";
else {
t = f;
cout<<"Deleted item is: "<<t->info<<endl;
f = f->l;
free(t);
}
}
void show() // 큐 출력 {
n *ptr;
ptr = f;
if (f == NULL)
cout<<"Queue is empty\n";
else {
cout<<"Queue is :\n";
cout<<"Priority Item\n";
while (ptr != NULL) {
cout<<ptr->p<<" "<<ptr->info<<endl;
ptr = ptr->l;
}
}
}
};
int main() {
int c, i, p;
Priority_Queue pq;
do { // 메뉴 선택에 따라 switch 연산 수행
cout<<"1.Insert\n";
cout<<"2.Delete\n";
cout<<"3.Display\n";
cout<<"4.Exit\n";
cout<<"Enter your choice : ";
cin>>c;
switch (c) {
case 1:
cout<<"Input the item value to be added in the queue : ";
cin>>i;
cout<<"Enter its priority : ";
cin>>p;
pq.insert(i, p);
break;
case 2:
pq.del();
break;
case 3:
pq.show();
break;
case 4:
break;
default:
cout<<"Wrong choice\n";
}
} while (c != 4);
return 0;
}
실행 결과
1.Insert 2.Delete 3.Display 4.Exit Enter your choice : 1 Input the item value to be added in the queue : 7 Enter its priority : 2 1.Insert 2.Delete 3.Display 4.Exit Enter your choice : 1 Input the item value to be added in the queue : 6 Enter its priority : 1 1.Insert 2.Delete 3.Display 4.Exit Enter your choice : 1 Input the item value to be added in the queue : 3 Enter its priority : 3 1.Insert 2.Delete 3.Display 4.Exit Enter your choice : 1 Input the item value to be added in the queue : 4 Enter its priority : 3 1.Insert 2.Delete 3.Display 4.Exit Enter your choice : 3 Queue is : Priority Item 1 6 2 7 3 3 3 4 1.Insert 2.Delete 3.Display 4.Exit Enter your choice : 4
코드 핵심 정리
- insert(): 새 노드를 알맞은 위치에 삽입하여 항상 우선순위 순서를 유지합니다. 최악의 경우 전체를 탐색해야 하므로 시간 복잡도는 O(n)입니다.
- del(): 전단(front)의 노드를 제거하므로 O(1) 시간에 수행됩니다.
- show(): 현재 큐에 담긴 모든 요소를 우선순위 순서대로 출력합니다.
실행 결과를 보면 우선순위 1의 값 6이 가장 먼저 위치하고, 같은 우선순위 3을 가진 3과 4는 삽입된 순서(선입선출)를 유지하는 것을 확인할 수 있습니다.
참고로 실무에서는 C++ 표준 라이브러리(STL)의 std::priority_queue를 사용하는 것이 일반적입니다. STL 버전은 내부적으로 힙(heap) 자료구조를 활용하여 삽입과 삭제를 O(log n) 시간에 처리할 수 있어 더 효율적입니다.