实验二栈和队列的基本操作及其应用-Read.doc

实验二 栈和队列的基本操作及其应用 一、实验目的 1、掌握栈和队列的顺序存储结构和链式存储结构，以便在实际中灵活应用。 2、掌握栈和队列的特点，即后进先出和先进先出的原则。 3、掌握栈和队列的基本运算，如：入栈与出栈，入队与出队等运算在顺序存储结构和链式存储结构上的实现。 二、实验内容 1、问题描述 对于一个从键盘输入的字符串，判断其是否为回文。回文即正反序相同。如“abba”是回文，而“abab”不是回文。 2、基本要求 （1）数据从键盘读入； （2）输出要判断的字符串； （3）利用栈的基本操作对给定的字符串判断其是否是回文，若是则输出“Yes”，否则输出“No”。 3、代码附录 #include iostream.h #include malloc.h #include conio.h #include stdio.h #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 # define MAXQSIZE 100 # define OK 1 # define ERROR 0 typedef char QElemType; typedef char SElemType ; typedef struct SqStack { SElemType *base;//在栈构造之前和销毁之后，base的值为NULL SElemType *top;//栈顶指针 int stacksize;//当前已分配的存储空间，以元素为单位 }SqStack; typedef struct 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!endl; return (1); } int Push(SqStack S,SElemType e) //插入元素e为新的栈顶元素 { if(S.top-S.base S.stacksize) //栈满追加存储空间 { S.base=(SElemType *)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,SElemType 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=(Q