Ｃ言語によるアルゴリズムとデータ構造

戻る  

演習4-5の解答

typedef struct {
    size_t  sz ;         /* 要素の大きさ */
    int     max ;        /* キューのサイズ */
    int     num ;        /* 現在の要素数 */
    int     front ;      /* 先頭要素カーソル */
    int     rear ;       /* 末尾要素カーソル */
    void    *que ;       /* キュー（の先頭要素へのポインタ） */
} Queue ;

/*
    演習4-5
    汎用キュー（あらゆる要素型に対応）
*/

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

/*--- キューを実現する構造体 ---*/
typedef struct {
    size_t  sz;         /* 要素の大きさ */
    int     max;        /* キューのサイズ */
    int     num;        /* 現在の要素数 */
    int     front;      /* 先頭要素カーソル */
    int     rear;       /* 末尾要素カーソル */
    void    *que;       /* キュー（の先頭要素へのポインタ） */
} Queue;

/*--- キューの初期化 ---*/
Queue *QueueAlloc(size_t size, int max)
{
    Queue   *q;

    if ((q = calloc(1, sizeof(Queue))) == NULL)
        return (q);
    if ((q->que = calloc(max, size)) == NULL) {
        free(q);                                    /* 配列の確保に失敗 */
        return (NULL);
    }
    q->sz = size;
    q->max = max;
    q->num = q->front = q->rear = 0;
    return (q);
}

/*--- キューの後始末 ---*/
void QueueFree(Queue *q)
{
    if (q != NULL  &&  q->que != NULL) {
        free(q->que);                           /* 配列を解放 */
        free(q);
    }
}

/*--- キューにデータをエンキュー ---*/
int QueueEnque(Queue *q, void *x)
{
    if (q->num >= q->max)
        return (-1);                            /* キューは満杯 */
    else {
        q->num++;
        memcpy((char *)q->que + q->rear * q->sz, x, q->sz);
        q->rear++;
        if (q->rear == q->max)
            q->rear = 0;
        return (0);
    }
}

/*--- キューからデータをデキュー ---*/
int QueueDeque(Queue *q, void *x)
{
    if (q->num <= 0)                            /* キューは空 */
        return (-1);
    else {
        q->num--;
        memcpy(x, (char *)q->que + q->front * q->sz, q->sz);
        q->front++;
        if (q->front == q->max)
            q->front = 0;
        return (0);
    }
}

/*--- キューの大きさ ---*/
int QueueSize(const Queue *q)
{
    return (q->max);
}

/*--- キューに蓄えられているデータ数 ---*/
int QueueNo(const Queue *q)
{
    return (q->num);
}

/*--- キューは空か ---*/
int QueueIsEmpty(const Queue *q)
{
    return (q->num <= 0);
}

/*--- キューは満杯か ---*/
int QueueIsFull(const Queue *q)
{
    return (q->num >= q->max);
}

int main(void)
{
    Queue  *que;

    /* 最大100個エンキューできるdouble型キュー */
    if ((que = QueueAlloc(sizeof(double), 100)) == NULL) {
        puts("キューの確保に失敗しました。");
        return (1);
    }

    while (1) {
        int     m;
        double  x;

        printf("現在のデータ数：%d/%d\n", QueueNo(que), QueueSize(que));
        printf("(1) エンキュー　(2) デキュー　(0) 終了：");
        scanf("%d", &m);

        if (m == 0) break;

        switch (m) {
         case 1: printf("データ：");   scanf("%lf", &x);
                 if (QueueEnque(que, &x) == -1)
                    puts("データのエンキューに失敗しました。");     break;

         case 2: if (QueueDeque(que, &x) == -1)
                    puts("デキューできません。");
                 else
                    printf("デキューしたデータは%lfです。\n", x);   break;
        }
    }
    QueueFree(que);

    return (0);
}

戻る