[c언어] 우선순위 큐의 구현

26 Dec 2023

c언어

우선순위 큐는 데이터를 저장하는 자료구조로, 각각의 데이터에 우선순위를 할당하여 우선순위에 따라 데이터를 처리하는데 사용됩니다. 이 게시물에서는 우선순위 큐를 C 언어로 구현하는 방법을 알아보겠습니다.

배열을 이용한 우선순위 큐 구현

우선순위 큐를 배열로 구현하는 가장 간단한 방법은 각 요소의 우선순위에 따라 정렬된 배열을 유지하는 것입니다. 그러면 삽입 시에는 적절한 위치에 요소를 삽입하고, 삭제 시에는 가장 높은 우선순위를 가진 요소를 제거하면 됩니다.

아래는 간단한 배열 기반 우선순위 큐의 구현 예시입니다.

#include <stdio.h>
#define MAX_SIZE 100

int queue[MAX_SIZE];
int rear = -1;

void enqueue(int value) {
    if (rear == MAX_SIZE - 1) {
        printf("Queue is full");
        return;
    }
    int i;
    for (i = rear; i >= 0; i--) {
        if (value > queue[i]) {
            queue[i + 1] = queue[i];
        } else {
            break;
        }
    }
    queue[i + 1] = value;
    rear++;
}

int dequeue() {
    if (rear == -1) {
        printf("Queue is empty");
        return -1;
    }
    int value = queue[rear];
    rear--;
    return value;
}

void display() {
    if (rear == -1) {
        printf("Queue is empty");
        return;
    }
    for (int i = 0; i <= rear; i++) {
        printf("%d ", queue[i]);
    }
    printf("\n");
}

int main() {
    enqueue(3);
    enqueue(5);
    enqueue(2);
    display(); // 출력: 5 3 2
    dequeue();
    display(); // 출력: 3 2
    return 0;
}

이 예제에서는 enqueue 함수를 통해 요소를 삽입하고, dequeue 함수를 통해 요소를 삭제합니다. display 함수는 현재 큐의 상태를 출력합니다.

연결리스트를 이용한 우선순위 큐 구현

또 다른 방법은 연결리스트를 사용하여 우선순위 큐를 구현하는 것입니다. 각 요소는 우선순위를 가지고 있는데, 새로운 요소를 삽입할 때 우선순위에 따라 연결리스트의 적절한 위치에 삽입하면 됩니다.

아래는 간단한 연결리스트 기반 우선순위 큐의 구현 예시입니다.

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node* next;
};

struct Node* front = NULL;

void enqueue(int value) {
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    new_node->data = value;
    if (front == NULL || value > front->data) {
        new_node->next = front;
        front = new_node;
    } else {
        struct Node* current = front;
        while (current->next != NULL && current->next->data > value) {
            current = current->next;
        }
        new_node->next = current->next;
        current->next = new_node;
    }
}

int dequeue() {
    if (front == NULL) {
        printf("Queue is empty");
        return -1;
    }
    struct Node* temp = front;
    int value = front->data;
    front = front->next;
    free(temp);
    return value;
}

void display() {
    if (front == NULL) {
        printf("Queue is empty");
        return;
    }
    struct Node* current = front;
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

int main() {
    enqueue(3);
    enqueue(5);
    enqueue(2);
    display(); // 출력: 5 3 2
    dequeue();
    display(); // 출력: 3 2
    return 0;
}

이 예제에서는 연결리스트를 사용하여 우선순위 큐를 구현했습니다. enqueue 함수를 통해 요소를 삽입하고, dequeue 함수를 통해 요소를 삭제합니다. display 함수는 현재 큐의 상태를 출력합니다.

우선순위 큐는 여러 다양한 응용 프로그램에 사용되며, 위에서 제시한 두 가지 방법 외에도 다양한 방법으로 구현될 수 있습니다. C 언어를 사용하여 우선순위 큐를 구현하는 것은 중요한 자료구조 이해를 위한 좋은 방법입니다.