우선순위 큐란 무엇인가?
우선순위 큐(Priority Queue)는 각 요소에 부여된 우선순위(priority)에 따라 삽입과 삭제가 이루어지는 특수한 형태의 큐입니다. 여기서 우선순위는 일반적으로 0부터 10 사이의 정수 값으로 표현되며, 0이 가장 높은 우선순위, 10이 가장 낮은 우선순위를 의미합니다.
우선순위 큐의 두 가지 기본 규칙
- 우선순위가 높은 데이터나 요소가 낮은 우선순위의 요소보다 먼저 처리됩니다.
- 두 요소의 우선순위가 같다면, 리스트에 추가된 순서대로 처리됩니다(선입선출, FIFO).
우선순위 큐의 구현 방법
우선순위 큐는 스택(Stack), 큐(Queue), 연결 리스트(Linked List) 등 다양한 자료구조를 활용하여 구현할 수 있습니다. 이 글에서는 큐 자료구조를 기반으로 한 구현 방법을 소개하며, 대표적인 구현 방식은 다음 두 가지입니다.
방법 1: 하나의 배열로 여러 우선순위 큐 관리하기
첫 번째 방법은 우선순위마다 하나의 큐를 유지하고, 이 여러 개의 큐를 하나의 배열에 저장하는 방식입니다. 각 큐는 프론트(Front)와 리어(Rear)라는 두 개의 포인터를 가집니다.
일반적으로 큐에서는 Rear 포인터가 요소를 삽입할 때 사용되며, 요소가 삽입될 때마다 1씩 증가합니다. 반면 Front 포인터는 요소를 삭제할 때 사용되며, 요소가 제거될 때마다 위치가 갱신됩니다. 또한 두 포인터의 위치만 확인하면 큐에 저장된 요소의 개수도 파악할 수 있습니다.
다만 이러한 표현 방식에서는 새로운 요소를 삽입할 공간을 확보하기 위해 포인터를 이동시켜야 하므로, 시간과 공간 측면 모두에서 복잡성이 커진다는 단점이 있습니다.
방법 2: 각 우선순위별로 별도의 큐 관리하기
두 번째 방법은 각 우선순위마다 별도의 큐를 생성하는 방식입니다. 모든 큐는 원형 배열(circular array)로 구현되며, 역시 Front와 Rear 두 개의 포인터 변수를 가집니다.
지정된 우선순위 번호를 가진 요소는 해당 우선순위의 큐에 삽입되고, 삭제 시에는 항상 가장 높은 우선순위를 가진 큐에서 요소가 제거됩니다. 여기서 가장 낮은 정수 값(0)이 가장 높은 우선순위를 나타낸다는 점에 유의하세요.
참고: 각 큐의 크기가 모두 동일하다면, 여러 개의 1차원 배열을 만드는 대신 하나의 2차원 배열을 사용하는 것이 더 효율적입니다.
삽입(Insert) 연산 알고리즘
아래는 우선순위 큐에 새로운 데이터를 지정된 우선순위와 함께 삽입하는 의사 코드(pseudocode)입니다. 오버플로우 검사 후 해당 우선순위 큐의 Rear 위치에 데이터를 저장합니다.
insert(queue, data, priority)
IF (queue->Rear[priority] == MAX-1 AND queue->Front[priority] == 0)
OR (queue->Rear[priority] + 1 == queue->Front[priority])
Print "Overflow"
END
IF queue->Rear[priority] == MAX-1
Set queue->Rear[priority] = 0
ELSE
Set queue->Rear[priority] = queue->Rear[priority] + 1
END
Set queue->CQueue[priority][queue->Rear[priority]] = data
IF queue->Front[priority] == -1
Set queue->Front[priority] = 0
END
END
삭제(Delete) 연산 알고리즘
삭제 연산은 가장 높은 우선순위(priority = 0)부터 차례대로 탐색하면서, 비어 있지 않은 첫 번째 큐의 Front 위치에 있는 값을 꺼내는 방식으로 동작합니다. 모든 큐가 비어 있다면 언더플로우(Underflow)를 출력합니다.
delete(queue)
Set flag = 0, priority = 0
WHILE priority <= MAX-1
IF NOT queue->Front[priority] == -1
Set flag = 1
Set value = queue->CQueue[priority][queue->Front[priority]]
IF queue->Front[priority] == queue->Rear[priority]
Set queue->Front[priority] = queue->Rear[priority] = -1
ELSE
IF queue->Front[priority] == MAX-1
Set queue->Front[priority] = 0
ELSE
Set queue->Front[priority] = queue->Front[priority] + 1
END
END
Break
END
Set priority = priority + 1
END
IF flag == 0
Print "Underflow"
ELSE
Return value
END
END
마무리
우선순위 큐는 운영체제의 프로세스 스케줄링, 네트워크 패킷 처리, 다익스트라 최단 경로 알고리즘 등 다양한 분야에서 활용되는 핵심 자료구조입니다. C/C++에서는 위와 같이 배열 기반으로 직접 구현할 수도 있고, C++ STL에서 제공하는 std::priority_queue를 활용하면 더욱 간편하게 사용할 수 있습니다. 실전 프로젝트에서는 데이터의 크기와 삽입·삭제 빈도를 고려하여 적절한 구현 방식을 선택하는 것이 중요합니다.