먼저 우선 순위 큐를 구현해 보아요.
우선 순위 큐를 앞에서 연결리스트를 이용해서 구현하기로 해요.
우선 순위 큐에는 래핑한 연결리스트와 비교 알고리즘이 필요해요.
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; }