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

演習4-2の解答

　前章で学習したbsearch 関数は、探索の対象となる配列の要素の型が任意であり、あるゆる型の配列からの探索が可能であった。このように、スタックの要素の型を任意にして、List 4-1と対応するすべての関数を作成せよ。
　このとき、Stack 型は以下のように宣言すること。

typedef struct {
    size_t   sz;        /* 要素の大きさ */
    int      max;       /* 最大の要素数 */
    int      ptr;       /* スタックポインタ */
    void     *stk;      /* スタック（の先頭要素へのポインタ） */
} Stack ;

　また、スタックの初期化を行う関数の形式は、以下のように、スタックに積むデータの大きさを与える。
　　Stack *StackAlloc (size_t size , int max );
　したがって、double型のスタックは、StackAlloc (sizeof(double), 100)などと呼び出すことになる。なお、プッシュやポップなどを行う関数の引数はvoidへのポインタ型となることに注意せよ。

/*
    演習4-2
    汎用スタック（あらゆる要素型に対応）
*/

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

/*--- スタックを実現する構造体 ---*/
typedef struct {
    size_t  sz;     /* 要素の大きさ */
    int     max;    /* 最大の要素数 */
    int     ptr;    /* スタックポインタ */
    void    *stk;   /* スタック（の先頭要素へのポインタ） */
} Stack;

/*--- スタックの初期化 ---*/
Stack *StackAlloc(size_t size, int max)
{
    Stack *s;

    if ((s = calloc(1, sizeof(Stack))) == NULL)
        return (s);
    if ((s->stk = calloc(max, size)) == NULL) {
        free(s);                                    /* 配列の確保に失敗 */
        return (NULL);
    }
    s->sz  = size;
    s->max = max;
    s->ptr = 0;
    return (s);
}

/*--- スタックの後始末 ---*/
void StackFree(Stack *s)
{
    if (s != NULL  &&  s->stk != NULL) {
        free(s->stk);
        free(s);
    }
}

/*--- スタックにデータをプッシュ ---*/
int StackPush(Stack *s, void *x)
{
    if (s->ptr >= s->max)
         return (-1);
    memcpy((char *)s->stk + s->ptr * s->sz, x, s->sz);
    s->ptr++;
    return (0);
}

/*--- スタックからデータをポップ ---*/
int StackPop(Stack *s, void *x)
{
    if (s->ptr <= 0)                            /* スタックは空 */
        return (-1);
    s->ptr--;
    memcpy(x, (char *)s->stk + s->ptr * s->sz, s->sz);
    return (0);
}

/*--- スタックからデータをピーク ---*/
int StackPeek(const Stack *s, void *x)
{
    if (s->ptr <= 0)                            /* スタックは空 */
        return (-1);
    memcpy(x, (char *)s->stk + s->ptr * s->sz, s->sz);
    return (0);
}

/*--- スタックの大きさ ---*/
int StackSize(const Stack *s)
{
    return (s->max);
}

/*--- スタックに積まれているデータ数 ---*/
int StackNo(const Stack *s)
{
    return (s->ptr);
}

/*--- スタックは空か ---*/
int StackIsEmpty(const Stack *s)
{
    return (s->ptr <= 0);
}

/*--- スタックは満杯か ---*/
int StackIsFull(const Stack *s)
{
    return (s->ptr >= s->max);
}

/*--- スタックを空にする ---*/
void StackClear(Stack *s)
{
    s->ptr = 0;
}

int main(void)
{
    Stack  *s;

    /* 最大100個プッシュできるdouble型スタック */
    if ((s = StackAlloc(sizeof(double), 100)) == NULL) {
        puts("スタックの確保に失敗しました。");
        return (1);
    }

    while (1) {
        int     m;
        double  x;

        printf("現在のデータ数：%d/%d\n", StackNo(s), StackSize(s));
        printf("(1) プッシュ　(2) ポップ　(0) 終了：");
        scanf("%d", &m);

        if (m == 0) break;

        switch (m) {
         case 1: printf("データ：");   scanf("%lf", &x);
                 if (StackPush(s, &x) == -1)
                    puts("スタックへのプッシュに失敗しました。");   break;

         case 2: if (StackPop(s, &x) == -1)
                    puts("ポップできません。");
                 else
                    printf("ポップしたデータは%fです。\n", x);      break;
        }
    }
    StackFree(s);

    return (0);
}

戻る