栈和队列的基本操作及其应用

1、实验二 栈和队列的基本操作及其应用一、实验目的1、掌握栈和队列的顺序存储结构和链式存储结构，以便在实际中灵活应用。2、掌握栈和队列的特点，即后进先出和先进先出的原则。3、掌握栈和队列的基本运算，如：入栈与出栈，入队与出队等运算在顺序存储结构和链式存储结构上的实现。二、实验内容1、问题描述对于一个从键盘输入的字符串，判断其是否为回文。回文即正反序相同。如“abba”是回文，而“abab”不是回文。2、基本要求（1）数据从键盘读入；（2）输出要判断的字符串； （3）利用栈的基本操作对给定的字符串判断其是否是回文，若是则输出“Yes”，否则输出“No”。3、代码附录#include #include

2、 #include #include #define STACK_INIT_SIZE 100#define STACKINCREMENT 10# define MAXQSIZE 100# define OK 1# define ERROR 0typedef char QElemType;typedef char SElemType ;typedef struct SqStackSElemType *base;/在栈构造之前和销毁之后，base的值为NULLSElemType *top;/栈顶指针int stacksize;/当前已分配的存储空间，以元素为单位SqStack;typedef st

3、ruct SqQueue/构造队链 QElemType *base; int front; int rear;SqQueue;int InitStack(SqStack &S) /构造一个空栈S S.base=(SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType);if(!S.base)/存储分配失败 cout存储分配失败!endl; return (0);S.top =S.base ;S.stacksize =STACK_INIT_SIZE;cout已成功建立空栈S!S.stacksize) /栈满追加存储空间 S.base=(SEle

4、mType *)realloc(S.base,(S.stacksize+STACKINCREMENT*sizeof(SElemType); if(!S.base) cout存储空间已满!endl; return(0); S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *S.top+=e; return (1);int StackEmpty(SqStack &S) /若栈空返回OK否则返回error if(S.top=S.base) return(1); else return(0);int Pop(SqStack &S,SElemT

5、ype &e) /若栈不空则删除栈顶元素用e返回其值并返回OK否则返回error if(S.top=S.base) coutUnderflow!endl; return (0);e=*-S.top; return(1);int InitQueue(SqQueue &Q)/构造一个空队链Q Q.base=(QElemType *)malloc(MAXQSIZE*sizeof(QElemType); if(!Q.base) coutendl存储分配失败 ! ;/存储分配失败return (ERROR); Q.front=Q.rear=0;cout已成功建立队链Q!endl; return (OK)

6、; int EnQueue(SqQueue &Q,QElemType e)/插入元素e为Q的新的队尾元素 if(Q.rear+1)%MAXQSIZE=Q.front) coutErrer ! The SqQeueu is full ! ;return (ERROR); /存储分配失败 Q.baseQ.rear=e; Q.rear=(Q.rear+1)%MAXQSIZE; return (OK); int DeQueue(SqQueue &Q,QElemType &e)/若栈不空则删除Q的队头元素用e返回其值并返回OK否则返回error if(Q.front=Q.rear) coutendlEr

7、rer ! Its empty!;return (ERROR); e=Q.baseQ.front; Q.front=(Q.front+1)%MAXQSIZE; return (e); int Palindrome_Test()/判别输入的字符串是否回文序列,是则返回1,否则返回0 SqStack S; SqQueue Q; char a,b,c; InitStack(S);InitQueue(Q); cout请用键盘输入字符串并以结尾: endl; while(c=getchar()!=) Push(S,c);EnQueue(Q,c);/同时使用栈和队列两种结构 while(!StackEmpty(S) Pop(S,a);DeQueue(Q,b); if(a!=b) return ERROR; return OK; void main() cout回文判断程序endl=endl; if(Palindrome_Test() cout.该字符串是回文.!endl; else cout.该字符串不