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

戻る  

演習4-4の解答

一般にデックと呼ばれる両方向待ち行列（deque／double ended Deque）は、下図に示すように、先頭と末尾に対して、データの追加・削除が行えるデータ構造である。両方向待ち行列を表すためのデータ型Deque と、それを操作するための関数群を作成せよ。

/*
    演習4-4
    デックの実現例
*/

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

/*--- デックを実現する構造体 ---*/
typedef struct {
    int  max;       /* デックのサイズ */
    int  num;       /* 現在の要素数 */
    int  front;     /* 先頭要素カーソル */
    int  rear;      /* 末尾要素カーソル */
    int  *que;      /* デック（の先頭要素へのポインタ） */
} Deque;

/*--- デックの初期化 ---*/
int DequeAlloc(Deque *q, int max)
{
    q->num = q->front = q->rear = 0;
    if ((q->que = calloc(max, sizeof(int))) == NULL) {
        q->max = 0;                             /* 配列の確保に失敗 */
        return (-1);
    }
    q->max = max;
    return (0);
}

/*--- デックの後始末 ---*/
void DequeFree(Deque *q)
{
    if (q->que != NULL) {
        free(q->que);                           /* 配列を解放 */
        q->max = q->num = q->front = q->rear = 0;
    }
}

/*--- デックにデータを先頭側からエンデック ---*/
int DequeFenque(Deque *q, int x)
{
    if (q->num >= q->max)
        return (-1);                            /* デックは満杯 */
    else {
        q->num++;
        if (--q->front < 0)
            q->front = q->max - 1;
        q->que[q->front] = x;
        return (0);
    }
}

/*--- デックにデータを末尾側からエンデック ---*/
int DequeRenque(Deque *q, int x)
{
    if (q->num >= q->max)
        return (-1);                            /* デックは満杯 */
    else {
        q->num++;
        q->que[q->rear++] = x;
        if (q->rear == q->max)
            q->rear = 0;
        return (0);
    }
}

/*--- デックからデータを先頭側からデデック ---*/
int DequeFdeque(Deque *q, int *x)
{
    if (q->num <= 0)                            /* デックは空 */
        return (-1);
    else {
        q->num--;
        *x = q->que[q->front++];
        if (q->front == q->max)
            q->front = 0;
        return (0);
    }
}

/*--- デックからデータを末尾側からデデック ---*/
int DequeRdeque(Deque *q, int *x)
{
    if (q->num <= 0)                            /* デックは空 */
        return (-1);
    else {
        q->num--;
        if (--q->rear < 0)
            q->rear = q->max - 1;       
        *x = q->que[q->rear];
        return (0);
    }
}

/*--- デックの大きさ ---*/
int DequeSize(const Deque *q)
{
    return (q->max);
}

/*--- デックに蓄えられているデータ数 ---*/
int DequeNo(const Deque *q)
{
    return (q->num);
}

/*--- デックは空か ---*/
int DequeIsEmpty(const Deque *q)
{
    return (q->num <= 0);
}

/*--- デックは満杯か ---*/
int DequeIsFull(const Deque *q)
{
    return (q->num >= q->max);
}

int main(void)
{
    Deque  que;

    if (DequeAlloc(&que, 100) == -1) {
        puts("デックの確保に失敗しました。");
        return (1);
    }
    while (1) {
        int  m, x;

        printf("現在のデータ数：%d/%d\n", DequeNo(&que), DequeSize(&que));
        printf("(1) 先頭からエンデック 　(2) 末尾からエンデック　(3) 先頭からデデック　(4) 末尾からデデック　(0) 終了：");
        scanf("%d", &m);

        if (m == 0) break;

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

         case 2: printf("データ：");   scanf("%d", &x);
                 if (DequeRenque(&que, x) == -1)
                    puts("データのエンデックに失敗しました。");     break;

         case 3: if (DequeFdeque(&que, &x) == -1)
                    puts("デデックできません。");
                 else
                    printf("デデックしたデータは%dです。\n", x);    break;

         case 4: if (DequeRdeque(&que, &x) == -1)
                    puts("デデックできません。");
                 else
                    printf("デデックしたデータは%dです。\n", x);    break;
        }
    }
    DequeFree(&que);

    return (0);
}

戻る