C++ 이중 연결 리스트로 구현하는 우선순위 큐

정수형 데이터와 우선순위(priority) 값이 주어졌을 때, 주어진 우선순위에 따라 이중 연결 리스트(doubly linked list)를 구성하고 그 결과를 출력하는 것이 이 글의 목표입니다.

우선순위 큐(Priority Queue)란?

큐(Queue)는 먼저 삽입된 요소가 가장 먼저 제거되는 FIFO(First In, First Out) 방식의 자료구조입니다. 우선순위 큐는 큐의 한 종류로, 각 요소가 가진 우선순위에 따라 삽입과 삭제가 이루어집니다. 우선순위 큐는 일반 큐, 스택 또는 연결 리스트 등 다양한 자료구조로 구현할 수 있으며, 다음 규칙을 따릅니다.

우선순위가 가장 높은 데이터나 요소는 낮은 우선순위의 요소보다 먼저 처리됩니다.
두 요소의 우선순위가 같다면, 리스트에 추가된 순서대로 처리됩니다.

이중 연결 리스트 노드의 구성

우선순위 큐를 구현하기 위한 이중 연결 리스트의 노드는 다음과 같은 네 부분으로 이루어집니다.

Data — 정수 값을 저장합니다.
Next Address — 다음 노드의 주소를 저장합니다.
Previous Address — 이전 노드의 주소를 저장합니다.
Priority — 정수형 우선순위 값을 저장합니다. 값의 범위는 0~10이며, 0이 가장 높은 우선순위, 10이 가장 낮은 우선순위를 나타냅니다.

예제

입력 -

C++ 이중 연결 리스트로 구현하는 우선순위 큐

출력 -

C++ 이중 연결 리스트로 구현하는 우선순위 큐

알고리즘

시작
1단계 -> 구조체 Node 선언
    info, priority 변수 선언
    struct Node *prev, *next 포인터 선언
2단계 -> push(Node** fr, Node** rr, int n, int p) 함수
    Node* news = (Node*)malloc(sizeof(Node)) 할당
    news->info = n 대입
    news->priority = p 대입
    만약 *fr == NULL이라면,
        *fr = news
        *rr = news
        news->next = NULL
    그렇지 않고 p <= (*fr)->priority라면,
        news->next = *fr
        (*fr)->prev = news->next
        *fr = news
    그렇지 않고 p > (*rr)->priority라면,
        news->next = NULL
        (*rr)->next = news
        news->prev = (*rr)->next
        *rr = news
    그 외의 경우,
        Node* start = (*fr)->next
    start->priority > p인 동안 반복
        start = start->next
        (start->prev)->next = news
        news->next = start->prev
        news->prev = (start->prev)->next
        start->prev = news->next
3단계 -> peek(Node *fr) 함수
    fr->info 반환
4단계 -> isEmpty(Node *fr) 함수
    (fr == NULL) 반환
5단계 -> pop(Node** fr, Node** rr) 함수
    Node* temp = *fr
    res = temp->info
    (*fr) = (*fr)->next
    free(temp)
    만약 *fr == NULL이라면,
        *rr = NULL
    res 반환
6단계 -> main() 함수
    Node *front = NULL, *rear = NULL 선언 및 초기화
    push(&front, &rear, 4, 3) 호출
    push(&front, &rear, 3, 2) 호출
    push(&front, &rear, 5, 2) 호출
    push(&front, &rear, 5, 7) 호출
    push(&front, &rear, 2, 6) 호출
    push(&front, &rear, 1, 4) 호출
    pop(&front, &rear) 함수의 반환값 출력
    peek(front) 함수의 반환값 출력
종료

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
// 이중 연결 리스트 노드
struct Node {
    int info;
    int priority;
    struct Node *prev, *next;
};
// 새 노드 삽입
void push(Node** fr, Node** rr, int n, int p) {
    Node* news = (Node*)malloc(sizeof(Node));
    news->info = n;
    news->priority = p;
    // 연결 리스트가 비어 있는 경우
    if (*fr == NULL) {
        *fr = news;
        *rr = news;
        news->next = NULL;
    } else {
        // p가 프런트(front) 노드의 우선순위보다
        // 작거나 같으면 노드를 맨 앞에 삽입한다.
        if (p <= (*fr)->priority) {
            news->next = *fr;
            (*fr)->prev = news->next;
            *fr = news;
        } else if (p > (*rr)->priority) {
            news->next = NULL;
            (*rr)->next = news;
            news->prev = (*rr)->next;
            *rr = news;
        } else {
            // 새 노드를 삽입할 적절한 위치를 찾는다.
            Node* start = (*fr)->next;
            while (start->priority > p)
                start = start->next;
            (start->prev)->next = news;
            news->next = start->prev;
            news->prev = (start->prev)->next;
            start->prev = news->next;
        }
    }
}
// 맨 앞의 값 확인
int peek(Node *fr) {
    return fr->info;
}
bool isEmpty(Node *fr) {
    return (fr == NULL);
}
int pop(Node** fr, Node** rr) {
    Node* temp = *fr;
    int res = temp->info;
    (*fr) = (*fr)->next;
    free(temp);
    if (*fr == NULL)
        *rr = NULL;
    return res;
}
// main 함수
int main() {
    Node *front = NULL, *rear = NULL;
    push(&front, &rear, 4, 3);
    push(&front, &rear, 3, 2);
    push(&front, &rear, 5, 2);
    push(&front, &rear, 5, 7);
    push(&front, &rear, 2, 6);
    push(&front, &rear, 1, 4);
    printf("%d\n", pop(&front, &rear));
    printf("%d\n", peek(front));
    return 0;
}

실행 결과

5
3

첫 번째 출력 값은 pop() 함수가 프런트에서 제거한 요소의 값이며, 두 번째 출력 값은 peek() 함수가 제거 없이 확인한 프런트 요소의 값입니다. 이처럼 이중 연결 리스트를 활용하면 우선순위에 따라 요소를 정렬된 상태로 유지하면서 삽입과 삭제를 효율적으로 처리할 수 있습니다.