優先度付きキュー | Programming Place Plus　アルゴリズムとデータ構造編【データ構造】　第１０章

// priority_queue.c

#include "priority_queue.h"
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "ppps_int_heap.h"

static void* xmalloc(size_t size);


struct PriorityQueue_tag {
    PPPSIntHeap  heap;
};


/*
    優先度付きキューを作る
*/
PriorityQueue priority_queue_create(size_t size)
{
    struct PriorityQueue_tag* queue = xmalloc( sizeof(struct PriorityQueue_tag) );
    queue->heap = ppps_int_heap_create( size );

    return queue;
}

/*
    優先度付きキューを削除する
*/
void priority_queue_delete(PriorityQueue queue)
{
    ppps_int_heap_delete( queue->heap );
    free( queue );
}

/*
    優先度付きキューに要素を入れる
*/
void priority_queue_enqueue(PriorityQueue queue, int value)
{
    bool ret = ppps_int_heap_insert( queue->heap, value );
    assert( ret );
}

/*
    優先度付きキューから要素を取り出す
*/
int priority_queue_dequeue(PriorityQueue queue)
{
    int value;
    bool ret = ppps_int_heap_remove_root( queue->heap, &value );
    assert( ret );

    return value;
}

/*
    優先度付きキューが空かどうか調べる
*/
bool priority_queue_is_empty(PriorityQueue queue)
{
    return ppps_int_heap_getsize( queue->heap ) == 0;
}



/*
    エラーチェック付きの malloc関数
*/
void* xmalloc(size_t size)
{
    void* p = malloc( size );
    if( p == NULL ){
        fputs( "メモリ割り当てに失敗しました。", stderr );
        exit( EXIT_FAILURE );
    }
    return p;
}

// priority_queue.h

#ifndef PRIORITY_QUEUE_H_INCLUDED
#define PRIORITY_QUEUE_H_INCLUDED

#include <stdbool.h>
#include <stddef.h>


/*
    優先度付きキュー型
*/
typedef struct PriorityQueue_tag* PriorityQueue;


/*
    優先度付きキューを作る

    引数：
        size:   格納できる要素数
    戻り値：
        作成された優先度付きキュー。
        使い終わったら、priority_queue_delete関数に渡して削除する。
*/
PriorityQueue priority_queue_create(size_t size);

/*
    優先度付きキューを削除する

    引数：
        queue:  優先度付きキュー
*/
void priority_queue_delete(PriorityQueue queue);

/*
    優先度付きキューに要素を入れる

    引数：
        queue:  優先度付きキュー
        value:  入れる要素
*/
void priority_queue_enqueue(PriorityQueue queue, int value);

/*
    優先度付きキューから要素を取り出す

    引数：
        queue:  優先度付きキュー
    戻り値：
        取り出された要素
*/
int priority_queue_dequeue(PriorityQueue queue);

/*
    優先度付きキューが空かどうか調べる

    引数：
        queue:  優先度付きキュー
    戻り値：
        優先度付きキューが空であれば true を返し、空でなければ false を返す。
*/
bool priority_queue_is_empty(PriorityQueue queue);


#endif

// main.c

#include <stdio.h>
#include "priority_queue.h"

int main(void)
{
    PriorityQueue queue = priority_queue_create( 16 );

    priority_queue_enqueue( queue, 5 );
    priority_queue_enqueue( queue, 3 );
    priority_queue_enqueue( queue, 7 );
    priority_queue_enqueue( queue, 2 );
    priority_queue_enqueue( queue, 9 );

    while( !priority_queue_is_empty(queue) ){
        printf( "%d\n", priority_queue_dequeue(queue) );
    }

    priority_queue_delete( queue );

    return 0;
}