[c언어] 우선순위 큐

26 Dec 2023

c언어

우선순위 큐(priority queue)는 데이터에 우선순위를 부여하여, 우선순위가 가장 높은 데이터가 가장 먼저 나가는 자료구조입니다. c언어에서 우선순위 큐는 배열 또는 연결 리스트를 사용하여 구현할 수 있습니다. 여기서는 배열을 사용한 우선순위 큐의 구현 예제를 소개하겠습니다.

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

#include <stdio.h>

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int size;
} PriorityQueue;

void initialize(PriorityQueue *q) {
    q->size = 0;
}

void enqueue(PriorityQueue *q, int value) {
    if (q->size >= MAX_SIZE) {
        printf("Queue is full\n");
        return;
    }
    int i;
    for (i = q->size - 1; i >= 0; i--) {
        if (q->data[i] > value) {
            q->data[i+1] = q->data[i];
        } else {
            break;
        }
    }
    q->data[i+1] = value;
    q->size++;
}

int dequeue(PriorityQueue *q) {
    if (q->size == 0) {
        printf("Queue is empty\n");
        return -1;
    }
    int value = q->data[q->size-1];
    q->size--;
    return value;
}

int main() {
    PriorityQueue q;
    initialize(&q);
    enqueue(&q, 3);
    enqueue(&q, 1);
    enqueue(&q, 2);
    printf("%d\n", dequeue(&q));  // 1
    printf("%d\n", dequeue(&q));  // 2
    printf("%d\n", dequeue(&q));  // 3
    printf("%d\n", dequeue(&q));  // Queue is empty, -1
    return 0;
}

위의 예제 코드에서는 배열을 사용하여 우선순위 큐를 구현하였습니다. enqueue 함수에서는 새로운 값을 적절한 위치에 삽입하고, dequeue 함수에서는 가장 높은 우선순위를 가진 데이터를 꺼냅니다.

이와 같이 c언어에서 우선순위 큐를 구현할 때는 배열을 활용하여 데이터를 삽입하고 삭제하는 방식으로 구현할 수 있습니다.

결론

c언어를 사용하여 우선순위 큐를 구현할 때는 배열을 사용하여 데이터의 우선순위에 따라 삽입과 삭제를 수행할 수 있습니다. 이를 통해 우선순위에 따라 데이터를 효율적으로 처리할 수 있습니다.

참고 문헌: geeksforgeeks.org - Priority Queue using Arrays