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

演習4-3の解答

　上記のアイディアに基づいて、キューを実現するプログラムを作成せよ。
　なお、キューを実現するための型は、以下に示すQueue 型を利用するものとして、List 4-2（p.114）に示す関数に対応する関数をすべて作成すること。

typedef struct {
    int  max ;       /* 最大の要素数 */
    int  ptr ;       /* 現在の要素数 */
    int  *que ;      /* キュー（の先頭要素へのポインタ） */
} Queue ;

/*
    演習4-3
    キューの実現例
*/

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

/*--- キューを実現する構造体 ---*/
typedef struct {
    int  max;       /* キューのサイズ */
    int  ptr;       /* 現在の要素数 */
    int  *que;      /* キュー（の先頭要素へのポインタ） */
} Queue;

/*--- キューの初期化 ---*/
int QueueAlloc(Queue *q, int max)
{
    q->ptr = 0;
    if ((q->que = calloc(max, sizeof(int))) == NULL) {
        q->max = 0;                             /* 配列の確保に失敗 */
        return (-1);
    }
    q->max = max;
    return (0);
}

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

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

/*--- キューからデータをデキュー ---*/
int QueueDeque(Queue *q, int *x)
{
    if (q->ptr <= 0)                            /* キューは空 */
        return (-1);
    else {
        int  i;
        *x = q->que[0];
        for (i = 0; i < q->ptr; i++)
            q->que[i] = q->que[i+1];
        q->ptr--;
        return (0);
    }
}

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

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

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

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

int main(void)
{
    Queue  que;

    if (QueueAlloc(&que, 100) == -1) {
        puts("キューの確保に失敗しました。");
        return (1);
    }
    while (1) {
        int  m, 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("%d", &x);
                 if (QueueEnque(&que, x) == -1)
                    puts("データのエンキューに失敗しました。");     break;

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

    return (0);
}

戻る