정수 형태의 데이터와 우선순위(priority) 값을 입력받아, 주어진 우선순위에 따라 연결 리스트를 구성하고 그 결과를 출력하는 것이 이번 글의 목표입니다.
우선순위 큐란 무엇인가?
큐(Queue)는 FIFO(First In, First Out, 선입선출) 방식의 자료구조로, 가장 먼저 삽입된 요소가 가장 먼저 제거됩니다. 반면 우선순위 큐(Priority Queue)는 각 요소가 지닌 우선순위에 따라 삽입과 삭제가 이루어지는 큐의 한 종류입니다. 우선순위 큐는 큐, 스택 또는 연결 리스트 자료구조를 활용하여 구현할 수 있으며, 다음과 같은 규칙을 따릅니다.
- 우선순위가 높은 데이터나 요소일수록 우선순위가 낮은 데이터보다 먼저 실행됩니다.
- 두 요소의 우선순위가 같다면, 리스트에 추가된 순서대로 실행됩니다.
연결 리스트 노드의 구성
우선순위 큐를 구현하기 위한 연결 리스트의 노드는 세 부분으로 이루어집니다.
- Data(데이터) – 정수 값을 저장합니다.
- Address(주소) – 다음 노드의 주소를 저장합니다.
- Priority(우선순위) – 정수 형태의 우선순위 값을 저장합니다. 0~10 범위를 가지며, 0이 가장 높은 우선순위, 10이 가장 낮은 우선순위를 의미합니다.
예제
입력
출력
알고리즘
시작
Step 1-> struct node 구조체 선언
data, priority 변수 선언
struct node* next 포인터 선언
Step 2-> Node* newNode(int d, int p) 함수
Node* temp = (Node*)malloc(sizeof(Node)) 로 메모리 할당
temp->data = d 설정
temp->priority = p 설정
temp->next = NULL 설정
temp 반환
Step 3-> int peek(Node** head) 함수
(*head)->data 반환
Step 4-> void pop(Node** head) 함수
Node* temp = *head 설정
(*head) = (*head)->next 설정
free(temp) 로 메모리 해제
Step 5-> void push(Node** head, int d, int p) 함수
Node* start = (*head) 설정
Node* temp = newNode(d, p) 생성
만약 (*head)->priority > p 라면,
temp->next = *head 설정
(*head) = temp 설정
그렇지 않으면
start->next != NULL && start->next->priority < p 인 동안 반복
start = start->next
temp->next = start->next 설정
start->next = temp 설정
Step 6-> int isEmpty(Node** head) 함수
(*head) == NULL 여부 반환
Step 7-> int main() 함수
Node* pq = newNode(7, 1) 생성
push(&pq, 1, 2) 호출
push(&pq, 3, 3) 호출
push(&pq, 2, 0) 호출
(!isEmpty(&pq)) 인 동안 반복
peek(&pq) 의 결과 출력
pop(&pq) 호출
종료
C언어 구현 예제 코드
#include <stdio.h>
#include <stdlib.h>
// 우선순위 노드 구조체
typedef struct node {
int data;
int priority;
struct node* next;
} Node;
Node* newNode(int d, int p) {
Node* temp = (Node*)malloc(sizeof(Node));
temp->data = d;
temp->priority = p;
temp->next = NULL;
return temp;
}
int peek(Node** head) {
return (*head)->data;
}
void pop(Node** head) {
Node* temp = *head;
(*head) = (*head)->next;
free(temp);
}
void push(Node** head, int d, int p) {
Node* start = (*head);
Node* temp = newNode(d, p);
if ((*head)->priority > p) {
temp->next = *head;
(*head) = temp;
} else {
while (start->next != NULL &&
start->next->priority < p) {
start = start->next;
}
// 리스트의 끝에 도달했거나
// 삽입해야 할 위치를 찾은 경우
temp->next = start->next;
start->next = temp;
}
}
// 큐가 비어 있는지 확인하는 함수
int isEmpty(Node** head) {
return (*head) == NULL;
}
// main 함수
int main() {
Node* pq = newNode(7, 1);
push(&pq, 1, 2);
push(&pq, 3, 3);
push(&pq, 2, 0);
while (!isEmpty(&pq)) {
printf("%d ", peek(&pq));
pop(&pq);
}
return 0;
}
실행 결과
2 7 1 3
실행 결과를 살펴보면, 가장 높은 우선순위(0)를 가진 데이터 2가 첫 번째로 출력되고, 이후 우선순위 1의 7, 우선순위 2의 1, 우선순위 3의 3 순서로 출력되는 것을 확인할 수 있습니다.
시간 복잡도 정리
- peek / pop – 항상 가장 앞의 노드만 참조하거나 제거하므로 O(1)의 시간 복잡도를 가집니다.
- push – 새 노드의 삽입 위치를 찾기 위해 리스트를 순회해야 하므로 최악의 경우 O(n)의 시간 복잡도를 가집니다.
이처럼 연결 리스트 기반의 우선순위 큐는 조회와 삭제가 빠르다는 장점이 있지만, 삽입 시 순회 비용이 발생한다는 점을 고려하여 상황에 맞게 활용하는 것이 좋습니다.