堆栈基本操作3

题目要求：

1、设栈采用顺序存储结构（用动态数组），请编写栈的各种基本操作的实现函数，并存放在头文件test7.h中。同时建立一个验证操作实现的主函数文件test7.cpp，编译并调试程序，直到正确运行。  
提示：
⑴ 栈的动态数组顺序存储结构可定义如下：
struct Stack {
    ElemType *stack ;   // 存栈元素
    int top;              // 栈顶指示器
    int MaxSize;            // 栈的最大长度
};
⑵ 栈的基本操作可包括：
① void InitStack (Stack &S);    //构造一个空栈 S
② int EmptyStack (Stack S);   //若栈S为空栈返回1，否则返回0
③ void Push(Stack &S, ElemType item);   //元素 item进栈
④ ElemType Pop(Stack &S);    //栈S的栈顶元素出栈并返回
⑤ ElemType Peek(Stack S);   //取栈S的当前栈顶元素并返回
⑥ void ClearStack (Stack &S);   //清除栈s，使成为空栈

2、应用：写一函数，判断给定的字符串是否中心对称。如字符串“abcba”、“abccba”均为中心对称，字符串“abcdba”不中心对称。要求利用test7.h中已实现的有关栈的基本操作函数来实现。请把该函数添加到文件test7.cpp中的主函数前，并在主函数中添加相应语句进行测试。函数原型如下：
int IsReverse(char *s)   //判断字符串S是否中心对称，是返回1，否则返回0

Test7.h的代码如下：

struct Stack {
    ElemType *stack ;   // 存栈元素
    int top;            // 栈顶指示器
    int MaxSize;            // 栈的最大长度
};
void InitStack (Stack &S)        //初始化堆栈
{         
S.MaxSize=10;
S.stack=(ElemType *) malloc(S.MaxSize *sizeof(ElemType));   //申请动态空间
if (!S.stack) {                             //假如空间分配失败
       cerr<<"动态分配失败!"<<endl;
       exit(1);
}
S.top=-1;                                    //栈顶指示
}

int EmptyStack (Stack S)         //判断是否是空栈
{
return S.top == -1;
}

void Push(Stack &S, ElemType item)    //把元素压入堆栈
{
if(S.top == S.MaxSize-1){    //若栈满，扩大两倍空间
   S.stack = (ElemType *) realloc( S.stack, 2*S.MaxSize*sizeof(ElemType) ); //继续申请空间
   S.MaxSize= 2*S.MaxSize;  
}
S.top ++;       
S.stack[S.top ] = item;
}

ElemType Pop(Stack &S)              //栈S的栈顶元素出栈并返回
{        
if (S.top==-1)           
{
   cerr<<"栈已空无数据元素出栈！"<<endl;
   exit(1);
}
S.top--;
return S.stack[S.top+1];
}

ElemType Peek( Stack S )        //取栈S的当前栈顶元素并返回
{         
if (S.top==-1)              //栈已空
{
   cerr<<"栈已空无数据元素出栈！"<<endl;
   exit(1);
}
return S.stack[S.top];
}

void ClearStack( Stack &S )     //销毁堆栈
{        
if (S.stack)
{
   free(S.stack);         //释放空间
   S.stack = NULL;
}
S.top = -1;
S.MaxSize = 0;
}

Test7.cpp 的代码如下：

#include <iostream.h>
#include <stdlib.h>
typedef char ElemType;
#include "test7.h"
int IsReverse(char *s)
{
Stack t;
InitStack(t);     //初始化堆栈
int i,j,res=1,x=0;
while(s[x]!='\0'){
   x++;
if(EmptyStack(t))
   for(j=0;j<x;j++)
    Push(t,s[j]);
}
cout<<"出栈字符为:"<<Peek(t)<<endl;
for(i=0;i<x/2;i++){
   if(s[i]==Pop(t))
    continue;
   else{
    res=0;
    break;
   }
   return res;         //返回标志
}
   ClearStack(t);
}
void main()
{
char a[80];            //定义数组
int i=0;
cout<<"输入字符串,以#为结束:"<<endl;
cin>>a[0];
while(a[i]!='#'){
   i++;
   cin>>a[i];         //输入线性表
}
a[i]='\0';            //线形表末尾
if(IsReverse(a))
   cout<<"字符串中心对称"<<endl;
else
   cout<<"字符串非中心对称"<<endl;
}