STEP 4.1B 構造体でスタック
(演習問題2.1)

<問題> スタック配列とtop変数をメンバーとする構造体(1つ)によるスタック実装例。プログラムを読み、自分なりのコメント文をつけて解読してみてください。


<実行例> (4.1Aと同じものです)S[0]はプリントしない
 
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

教科書と同じように、分割コンパイル
stack.h 共有情報
stack.c 関数定義
0401b.c main関数

gcc -c stack.c
gcc -c 0401b.c
gcc -o 0401b stack.o 0401b.o



解答例

以下、stack.h

#include <stdio.h>
#include <stdlib.h>
#define MAX 256 /* 配列256 */

/* 以下、スタック構造体。1つだけmainで作成する */
/* topは、スタックの先頭 */
typedef struct{
   char data[MAX]; /* スタックの配列 */
   int top; /* topを示すポインター。最初は0 */
} Stack;

void pushdown (Stack *S, char x);
char popup (Stack *S);
void initialize (Stack *S);
int empty (Stack *S);

void show (Stack *S); /* Stackを頭から表示する関数 追加*/


以下、stack.c
#include "stack.h"

/* xを、data[]に、pushし、top変数を更新する */
void pushdown (Stack *S, char x) {
   if(S -> top < MAX){
      S -> top++;
      S -> data[S->top] = x;
   } else {
      printf ("Stack S overflows.\n");
   }
}

/* データをpop top変数を更新する */
char popup (Stack *S) {
   if(S -> top > 0){
      S -> top--;
      return(S->data[S->top+1]);
   } else {
      printf ("Stack S is empty.\n");
      return('\0');
   }
}

/* 初期化 */
void initialize (Stack *S) {
   S -> top = 0;
}

/* Stackが空かどうかを判定。空なら1 */
int empty(Stack *S) {
   if(S -> top == 0) {
      return(1);
   }
   return(0);
}

/* 構造体中のdata配列の内容を表示 */
void show (Stack *S) {
   int i;
   printf ("top = %2d\n", S -> top);
   for(i = S -> top; i > 0; i--) {
      printf("stack[%d] = %c \n", i, S -> data[i]);
   }
   printf("\n");
}


以下、0401b.c

#include "stack.h"
int main(void){
   char x;
   Stack S;

   initialize(&S);
   printf("a is pushed \n");
   pushdown(&S,'a');
   printf("b is pushed \n");
   pushdown(&S,'b');
   printf("c is pushed \n");
   pushdown(&S,'c');

   show(&S);

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

   show(&S);


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

   show(&S);

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