STEP 4.1A 配列でスタック

<問題> 配列によるスタック実装例。プログラムを読み、自分なりのコメント文をつけて解読してみてください。


<実行例>
 
a is pushed
b is pushed
c is pushed
top =  3
S[3] = c
S[2] = b
S[1] = a


c is poped
b is poped
top =  1
S[1] = a


d is pushed
d is poped
e is pushed
top =  2
S[2] = e
S[1] = a


ea


解答例

#include <stdio.h>
#define MAX 10

void pushdown(char x);
char popup(void);
void initialize(void);
int empty(void);

int top = 0; /* スタックの先頭の要素ポインタ。0のときは空を表す */
char S[MAX];

/* スタックにデータをプッシュ */
void pushdown(char x) {

   if (top < MAX) {
      top++;
      S[top] = x;
   } else {
      printf("Stack S overflows.\n");
   }
}

/* スタックからデータをポップ */
char popup(void) {
   if (top > 0) {
      top--;
      return (S[top + 1]);
   } else { /* top == 0のとき */
      printf("Stack S is empty.\n");
      return ('\0');
   }
}

/* スタックの初期化 */
void initialize(void) {
   int i;
   top = 0;
   for (i = 1; i < MAX; i++) {
      S[i] = '\0';
   }
}

/* スタックが空の状態かどうかを判定 yesなら1 */
int empty(void) {
   if (top == 0) {
      return (1);
   }
   return (0);
}

/* 定番の配列プリント用 */
void show(void) {
   int i;

   printf ("top = %2d\n", top);
   for (i = top; i > 0; i--)
      printf("S[%d] = %c \n", i, S[i]);
   printf("\n\n");
}

int main(void) {
   char x;

   initialize();

   printf("a is pushed \n");
   pushdown('a');
   printf("b is pushed \n");
   pushdown('b');
   printf("c is pushed \n");
   pushdown('c');
   show();

   x = popup();
   printf("%c is poped \n", x);
   x = popup();
   printf("%c is poped \n", x);
   show();


   printf("d is pushed \n");
   pushdown('d');
   x = popup();
   printf("%c is poped \n", x);
   printf("e is pushed \n");
   pushdown('e');

   show();

  /* popしながら内容をプリント。実行後はスタックは空になる */
   while (!empty()) {
      printf("%c", popup());
   }
   printf("\n");

   return (0);
}