实验二：栈与队列
实验目的：使学生深入了解栈与队列的特性，以便在实际背景下灵活运用他们，同时还将巩固这两种结构的构造方法。
实验题目：
1. 检测表达式中{},[],()扩号匹配算法.
2.检测字符串是否回文的算法
栈与队列
代码如下（示例）：
#include "stdio.h"
#include "string.h"
#include "malloc.h"
#define STACK_INIT_SIZE 30
#define STACKINCREMENT 10
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
typedef char SElemType;
typedef struct
{ SElemType *base;
SElemType *top;
int stacksize;
} SqStack;
//-----------初始化栈------------
Status InitStack(SqStack &S)
{ S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!S.base) return ERROR;
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}
//--------------压栈----------------
Status Push(SqStack &S,SElemType e)
{ if(S.top-S.base>=S.stacksize)
{S.base=(SElemType
)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));
// if(!S->base) exit (OVERFLOW);
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
return OK;
}
//------------------出栈------------------
Status Pop(SqStack &S,SElemType *e)
{ if (S.top==S.base) return ERROR;
*e=*--S.top;
return OK;
}
Status StackEmpty(SqStack S)
{ return (S.base==S.top);
}
//--------------取栈顶元素----------------
Status GetTop(SqStack S,SElemType *e)
{ if(StackEmpty(S)) return ERROR;
*e=*(S.top-1);
return OK;
}
//---------括号区配-----------------
int pair(char *s)
{ int i;
char e;
SqStack T;
InitStack(T);
for(i=0;i<(int)strlen(s);i++)
{ if (s[i]=='('||s[i]=='[') Push(T,s[i]);
if (s[i]==')')
{ if(!GetTop(T,&e)) return ERROR;
else if (e=='(') Pop(T,&e);
else return ERROR;
}
if (s[i]==']')
{ if(!GetTop(T,&e)) return ERROR;
else if(e=='[') Pop(T,&e);
else return ERROR;
}
}
return (StackEmpty(T));
}
//--------------回文-----------------------
int Ishuiwen(char *s)
{ SqStack T;
int i,l;
char c;
InitStack(T);
l=(int)strlen(s);
for(i=0;i
Push(T,s[i]);
while(!StackEmpty(T))
{ Pop(T,&c);
if(c!=s[l-i]) return ERROR;
i--;
}
return OK;
}
//--------------主函数------------
int main()
{
//验证部分
char s[80],d;
gets(s);
d=Ishuiwen(s);
if(d) printf("YES");
else printf("NO");
return 0;
