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

戻る  

演習4-1の解答

一つの配列を共有して二つのスタックを実現するためのデータ構造および関数群を作成せよ。図のように配列の先頭側と末尾側の両側を利用すること。

/*
    演習4-1
    両頭スタックの実現例
*/

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

enum {StackA, StackB};

/*--- 両頭スタックを実現する構造体 ---*/
typedef struct {
    int  max;       /* スタックのサイズ（Ａ・Ｂの合計） */
    int  ptrA;      /* スタックポインタＡ */
    int  ptrB;      /* スタックポインタＢ */
    int  *stk;      /* スタック（の先頭要素へのポインタ） */
} Stack;

/*--- スタックの初期化 ---*/
int StackAlloc(Stack *s, int max)
{
    s->ptrA = 0;
    s->ptrB = max - 1;
    if ((s->stk = calloc(max, sizeof(int))) == NULL) {
        s->max = 0;                             /* 配列の確保に失敗 */
        return (-1);
    }
    s->max = max;
    return (0);
}

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

/*--- スタックにデータをプッシュ ---*/
int StackPush(Stack *s, int sw, int x)
{
    if (s->ptrA >= s->ptrB + 1)
         return (-1);
    switch (sw) {
     case StackA: s->stk[s->ptrA++] = x; break;
     case StackB: s->stk[s->ptrB--] = x; break;
    }
    return (0);
}

/*--- スタックからデータをポップ ---*/
int StackPop(Stack *s, int sw, int *x)
{
    switch (sw) {
     case StackA: 
        if (s->ptrA <= 0)                           /* スタックは空 */
            return (-1);
        *x = s->stk[--s->ptrA];
        break;
     case StackB:
        if (s->ptrB >= s->max - 1)                  /* スタックは空 */
            return (-1);
        *x = s->stk[++s->ptrB];
        break;
    }
    return (0);
}

/*--- スタックからデータをピーク ---*/
int StackPeek(const Stack *s, int sw, int *x)
{
    switch (sw) {
     case StackA: 
        if (s->ptrA <= 0)                           /* スタックは空 */
            return (-1);
        *x = s->stk[s->ptrA - 1];
        break;
     case StackB:
        if (s->ptrB >= s->max - 1)                  /* スタックは空 */
            return (-1);
        *x = s->stk[s->ptrB + 1];
        break;
    }
    return (0);
}

/*--- スタックの大きさ（Ａ・Ｂの合計） ---*/
int StackSize(const Stack *s)
{
    return (s->max);
}

/*--- スタックに積まれているデータ数 ---*/
int StackNo(const Stack *s, int sw)
{
    return ((sw == StackA) ? s->ptrA : s->max - s->ptrB - 1);
}

/*--- スタックは空か ---*/
int StackIsEmpty(const Stack *s, int sw)
{
    return ((sw == StackA) ? (s->ptrA <= 0) : (s->ptrB >= s->max - 1));
}

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

/*--- スタックを空にする ---*/
void StackClear(Stack *s, int sw)
{
    switch (sw) {
     case StackA: s->ptrA = 0;          break;
     case StackB: s->ptrB = s->max - 1; break;
    }
}

int main(void)
{
    Stack  s;

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

        printf("スタックのデータ数（Ａ:%d／Ｂ:%d）\n", 
                    StackNo(&s, StackA), StackNo(&s, StackB));
        printf("(1)Ａにプッシュ　(2)Ａからポップ　(3)Ｂにプッシュ　(4)Ｂからポップ　(0) 終了：");
        scanf("%d", &m);

        if (m == 0) break;

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

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

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

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

    return (0);
}

戻る