9.2.1 우선 순위 큐 구현

먼저 우선 순위 큐를 구현해 보아요.

우선 순위 큐를 앞에서 연결리스트를 이용해서 구현하기로 해요.

우선 순위 큐에는 래핑한 연결리스트와 비교 알고리즘이 필요해요.

typedef struct _PriorityQueue PriQueue;
typedef int (*Compare)(Element el1,Element el2);
struct _PriorityQueue
{
    LinkedList *list;
    Compare compare;
};

우선 순위 큐를 동적으로 생성하고 해제하는 메서드를 제공하기로 해요.

PriQueue *New_PriorityQueue(Compare compare);
void Delete_PriQueue(PriQueue *pq);

우선 순위 큐에 데이터를 보관하고 꺼내는 메서드와 비었는지 판별하는 함수를 제공하세요.

void PriQueue_Put(PriQueue *pq, Element data);
Element PriQueue_Get(PriQueue *pq);
int PriQueue_IsEmpty(PriQueue *pq);

다음은 PriorityQueue.h 파일의 소스 내용입니다.

#pragma once
#include "LinkedList.h"

typedef struct _PriorityQueue PriQueue;
typedef int (*Compare)(Element el1,Element el2);
struct _PriorityQueue
{
    LinkedList *list;
    Compare compare;
};
PriQueue *New_PriorityQueue(Compare compare);
void Delete_PriQueue(PriQueue *pq);
void PriQueue_Put(PriQueue *pq, Element data);
Element PriQueue_Get(PriQueue *pq);
int PriQueue_IsEmpty(PriQueue *pq);

먼저 우선 순위 큐를 동적으로 생성하는 함수를 작성하기로 해요.

PriQueue *New_PriorityQueue(Compare compare)
{

동적으로 메모리 할당한 후에 래핑할 연결리스트를 생성하고 알고리즘을 멤버에 설정하세요.

    PriQueue *pq = (PriQueue *)malloc(sizeof(PriQueue));
    pq->list = New_LinkedList();
    pq->compare = compare;
    return pq;
}

해제하는 함수에서는 래핑한 연결리스트를 해제한 후에 자신의 메모리를 해제하세요.

void Delete_PriQueue(PriQueue *pq)
{
    Delete_LinkedList(pq->list);
    free(pq);
}

우선 순위 큐에 보관하는 기능을 구현해 보아요.

void PriQueue_Put(PriQueue *pq, Element data)
{

래핑한 연결리스트에 어디에 보관할 지 찾아야겠죠.

먼저 연결리스트의 시작과 끝을 얻어오세요.

    Link seek = LinkedList_Begin(pq->list);
    Link end = LinkedList_End(pq->list);
    for(    ;seek != end; seek=seek->next)
    {
        if(pq->compare(seek->data, data)>=0)
        {

만약 비교 알고리즘으로 보관한 데이터가 새로운 데이터보다 크거나 같은 곳이 원하는 위치예요.

            break;
        }
    }

위치를 찾았으면 찾은 위치 앞에 보관하세요.

    LinkedList_Insert(pq->list,seek,data);
}

이번에는 우선 순위 큐에서 꺼내는 함수를 작성하세요.

이 부분은 일반 큐와 구현이 같아요.

Element PriQueue_Get(PriQueue *pq)
{    
    Link begin;
    if(PriQueue_IsEmpty(pq))
    {
        return 0;
    }
    begin = LinkedList_Begin(pq->list);
    LinkedList_Erase(pq->list,begin);
    return begin->data;
}

비었는지 확인하는 함수도 일반 큐와 같습니다.

int PriQueue_IsEmpty(PriQueue *pq)
{
    return pq->list->usage == 0;
}

다음은 PriorityQueue.c 파일의 소스 내용입니다.

#include "PriorityQueue.h"
#include <malloc.h>
#include <memory.h>
PriQueue *New_PriorityQueue(Compare compare)
{
    PriQueue *pq = (PriQueue *)malloc(sizeof(PriQueue));
    pq->list = New_LinkedList();
    pq->compare = compare;
    return pq;
}
void Delete_PriQueue(PriQueue *pq)
{
    Delete_LinkedList(pq->list);
    free(pq);
}
void PriQueue_Put(PriQueue *pq, Element data)
{
    Link seek = LinkedList_Begin(pq->list);
    Link end = LinkedList_End(pq->list);
    for(    ;seek != end; seek=seek->next)
    {
        if(pq->compare(seek->data, data)>0)
        {
            break;
        }
    }
    LinkedList_Insert(pq->list,seek,data);
}
Element PriQueue_Get(PriQueue *pq)
{    
    Link begin;
    if(PriQueue_IsEmpty(pq))
    {
        return 0;
    }
    begin = LinkedList_Begin(pq->list);
    LinkedList_Erase(pq->list,begin);
    return begin->data;
}
int PriQueue_IsEmpty(PriQueue *pq)
{
    return pq->list->usage == 0;
}