#ifndef boolean_H
#define boolean_H
#define true 1
#define false 0
#define boolean unsigned char
#endif

#include <stdio.h>
#include "boolean.h"
#ifndef STATIK_STACK_H
#define   STATIK_STACK_H

#define Nil 0
#define MaxEl 50

typedef int infotype;
typedef int address;
typedef struct
    {
      infotype T [MaxEl];
      address TOP;
    } Stack;

/***************************KONSTRUKTOR*************************/
void CreateEmpty (Stack *S);
/*I.S. Sembarang
  F.S. Membuat sebuah stack S yang kosong berkapasitas MaxEl
  jadi indeksnya antara 1..MaxEl
  Ciri stack kosong : TOP bernilai Nil */

/**********************Predikat Untuk test keadaan KOLEKSI***********************/
boolean IsEmpty (Stack S);
/*Mengirim true jika Stack kosong */

boolean IsFull (Stack S);
/*Mengirim true jika array penampung nilai elemen stack penuh*/

/*********************OPERATOR*********************/
void Push (Stack *S, infotype X);
/*Menambahkan X sebagai elemen Stack S.
  I.S. S mungkin kosong, tabel penampung elemen stack TIDAK penuh
  F.S. X menjadi TOP yang baru, TOP bertambah 1 */

void Pop (Stack *S, infotype *X);
/*Menghapus X dari Stack S.
  I.S. S tidak kosong
  F.S. X adalah nilai elemen TOP yang lama, TOP berkurang 1 */

void ShowS (Stack S);

#endif

#include <stdio.h>
#include "stack.h"

/***************************KONSTRUKTOR*************************/
void CreateEmpty (Stack *S)
/*I.S. Sembarang
  F.S. Membuat sebuah stack S yang kosong berkapasitas MaxEl
  jadi indeksnya antara 1..MaxEl
  Ciri stack kosong : TOP bernilai Nil */
{
   (*S).TOP=Nil;
}

/**********************Predikat Untuk test keadaan KOLEKSI***********************/
boolean IsEmpty (Stack S)
/*Mengirim true jika Stack kosong */
{
   return (S.TOP==Nil);
}

boolean IsFull (Stack S)
/*Mengirim true jika array penampung nilai elemen stack penuh*/
{
   return (S.TOP>=MaxEl);
}

/*********************OPERATOR*********************/
void Push (Stack *S, infotype X)
/*Menambahkan X sebagai elemen Stack S.
  I.S. S mungkin kosong, tabel penampung elemen stack TIDAK penuh
  F.S. X menjadi TOP yang baru, TOP bertambah 1 */
{
   if(!IsFull (*S)){
      (*S).TOP++;
      (*S).T[(*S).TOP-1]=X;
   }
}

void Pop (Stack *S, infotype *X)
/*Menghapus X dari Stack S.
  I.S. S tidak kosong
  F.S. X adalah nilai elemen TOP yang lama, TOP berkurang 1 */
{
   if(!IsEmpty (*S)){
      *X=(*S).T[(*S).TOP-1];
      (*S).TOP--;
   }
}

void ShowS (Stack S){
   Stack ST;
   infotype X;
   CreateEmpty (&ST);
   printf("|");
   if(!IsEmpty (S)){
      while(!IsEmpty (S)){
         Pop (&S, &X);
         Push (&ST, X);
      }
      while(!IsEmpty (ST)){
         printf("%d",ST.T[ST.TOP-1]);
         Pop (&ST, &X);
      }
   }
   printf("\n");
}

#include <stdio.h>
#include "stack.h"

void ShowStacks();
void MovePiece();
void MoveTower();

int main() {
   Stack S[3];
   int n,i;
   
   printf("n = ");
   scanf("%d",&n);
   for(i=1;i<=3;i++){
      CreateEmpty (&S[i]);
   }
   for(i=n;i>=1;i--){
      Push (&S[1], i);
   }
   ShowStacks(S);
   MoveTower(S,n,1,3);
   printf("Done.");
    return 0;
}

void ShowStacks(Stack S[3]){
   int i;
   for(i=1;i<=3;i++){
      ShowS (S[i]);
   }
   printf("\n");
   getch();
}

void MovePiece(Stack S[3],int si,int sf){
   infotype X;
   Pop (&S[si], &X);
   Push (&S[sf], X);
   ShowStacks(S);
}

void MoveTower(Stack S[3],int m,int si,int sf){
   if(m==1){
      MovePiece(S,si,sf);
   }else{
      MoveTower(S,m-1,si,6-si-sf);
      MovePiece(S,si,sf);
      MoveTower(S,m-1,6-si-sf,sf);
   }
}