//用棧判斷是否回文
#include <stdio.h>
#include<stdlib.h>
#define True 1
#define False 0
#define LEN sizeof(ElemType)
#define Stack_InitSize 100
#define Stack_Increment 30

typedef char ElemType;

struct SqStack
{
ElemType *base;
ElemType *top; 
int stacksize;
};

/*構造一個空棧*/
SqStack* InitStack(struct SqStack *S)
{
S=(SqStack*)malloc(sizeof(SqStack));
S->base = (ElemType *)malloc(Stack_InitSize*LEN);
if(!S->base)
return S ;
S->top = S->base;
S->stacksize = Stack_InitSize;
return S;
}

/*銷毀一個棧*/
void DestroyStack(struct SqStack *S)
{
while(S->top!=S->base)
S->top--;
free(S->base);
free(S);
}

/*將棧里面的元素清空*/
void ClearStack(struct SqStack *S)
{
while(S->top!=S->base)
S->top--;
}

/*判斷是否為空棧*/
int IsEmpty(struct SqStack *S)
{
if(S->top==S->base)
return 1;
else
return 0;
}

/*按出棧順序打印這個棧*/
void Print(struct SqStack *S)
{
ElemType *p;
p = S->top;
while(p!=S->base)
{
p--;
printf("%d ",*p);
}
printf("\n");
p=NULL;
}

/*向棧里壓入數據e*/
void Push(struct SqStack *S,ElemType e)
{
if(S->top - S->base >= S->stacksize) /*棧滿，重新分配更大的空間*/
{
S->base = (ElemType *)realloc(S->base,(S->stacksize+Stack_Increment)*LEN);
S->top = S->base + S->stacksize;
S->stacksize += Stack_Increment;
}
*S->top = e;
S->top++;
return;
}

/*彈出棧頂元素*/
void Pop(struct SqStack *S)
{
if(S->top==S->base)
return ;
S->top--;
}

/*返回棧頂元素*/
char GetTop(struct SqStack *S)
{
ElemType *p = S->top;
if(S->top==S->base)
{
//printf("The stack is empty!");
return False;
}
return *(--p);
}
void main()
{
  SqStack *a;
  SqStack *c;
  char b;
  int i=0;
  a=InitStack(a);
  printf("Please put your datas into this stack!\n");
  scanf("%c",&b);
  while(b!='#')
  {
    Push(a,b);
	i++;
	scanf("%c",&b);
}
  c=InitStack(c);
  int j=0;
  while(j<i/2)
  {
	  Push(c,GetTop(a));
	  Pop(a);
	  j++;
  }
  if(i%2!=0) Pop(a);
  while(!IsEmpty(a) && !IsEmpty(c))
	  if(GetTop(a)!=GetTop(c)) 
	  {printf("This is not a reversion!\n");
	  break;}
	  else 
	  {
		  Pop(a);
		  Pop(c);
	  }
if(IsEmpty(a) && IsEmpty(c)) 
printf("This stack is a reversion!\n");
ClearStack(a);
ClearStack(c);
 DestroyStack(a);
  DestroyStack(c);
}