实验三栈和队列的应用1、实验目的（1）熟练掌握栈和队列的结构以及这两种数据结构的特点、栈与队列的基本操作。

（2）能够在两种存储结构上实现栈的基本运算，特别注意栈满和栈空的判断条件及描述方法；（3）熟练掌握链队列和循环队列的基本运算，并特别注意队列满和队列空的判断条件和描述方法；（4）掌握栈和队列的应用；2、实验内容1）栈和队列基本操作实现（1）栈的基本操作：采用顺序存储或链式存储结构（数据类型自定义），实现初始化栈、判栈是否为空、入栈、出栈、读取栈顶元素等基本操作，栈的存储结构自定义。

（2）队列的基本操作：实现循环队列或链队列的初始化、入队列、出队列、求队列中元素个数、判队列空等操作，队列的存储结构自定义。

2）栈和队列的应用（1）利用栈的基本操作将一个十进制的正整数转换成二进制数据，并将其转换结果输出。

提示：利用栈的基本操作实现将任意一个十进制整数转化为R进制整数算法为：十进制整数X和R作为形参初始化栈只要Ｘ不为0重复做下列动作将x%R入栈X=X/R只要栈不为空重复做下列动作栈顶出栈输出栈顶元素(2) 利用栈的基本操作对给定的字符串判断其是否是回文，若是则输出“Right”，否则输出“Wrong”。

(3) 假设循环队列中只设rear（队尾）和quelen（元素个数据）来分别表示队尾元素的位置和队中元素的个数，写出相应的入队和出队程序。

（4）选作题：编写程序实现对一个输入表达式的括号配对。

3、实验步骤（1）理解栈的基本工作原理；（2）仔细分析实验内容，给出其算法和流程图；（3）用C语言实现该算法；（4）给出测试数据，并分析其结果；（5）在实验报告册上写出实验过程。

4、实验帮助算法为：1) 定义栈的顺序存取结构2) 分别定义栈的基本操作（初始化栈、判栈为空、出栈、入栈等）3) 定义一个函数用来实现上面问题：十进制整数X和R作为形参初始化栈只要X不为0重复做下列动作将X % R入栈X=X/R只要栈不为空重复做下列动作栈顶出栈输出栈顶元素5、算法描述（1））初始化栈S (创建一个空栈S)void initstack(sqstack *S){ S->base=(ElemType *)malloc(INITSIZE*sizeof(ElemType));if(!S->base) exit (-1);S->top=0; /*空栈标志*/S->stacksize = INITSIZE;}(2) 获取栈顶元素int gettop(sqstack S,ElemType *e) //顺序钱{if ( S.top==0 ) /* 栈空 */{ printf(“Stack is empty!\n”);return 0;}*e= S.base[top-1];return 1;}void gettop(STACK S , ElemType *e) //链式栈{ if ( S.top==NULL ){ printf(“Stack is empty”);exit(0);}else *e=S.top->data ;}（(3) 进栈 (在栈顶插入新的元素x)int push ( sqstack *S , ElemType x )//顺序钱{ if (S->top == S->stacksize){ S->base= (ElemType *)realloc(S->base,(S->stacksize+1)*sizeof(ElemType)); if(!S->base) exit(-1);S->stacksize++;}S->base[S->top++] = x;return 1 ;}void push ( STACK *S , ElemType e )//链式栈{ linkstack *p;p=( linkstack *) malloc( sizeof ( linkstack ) );if ( !p ) exit(0) ;p->data = e;p->next = S->top;S->top = p;}(4) 出栈 (取出S栈顶的元素值交给e)int pop(sqstack *S, ElemType *e) //顺序钱{if (S.top==0){ printf(“Stack is empty”);return 0;}*e=S->base [-- S->top ] ;return 1;}void pop(STACK *S, ElemType *e) //链式栈{if ( S->top==NULL ){ printf(“Stack is empty”);exit(0); }else{ *e=S->top->data;p=S->top;S->top= p -> next;free(p);}}(5) 判断栈S是否为空int stackempty(sqstack S){ if (S.top==0)return 1 ;elsereturn 0 ; }（6）符序列逆置输出void ReverseRead( ){STACK S; //定义一个栈结构Schar ch;initstack(&S); //初始化栈while ((ch=getchar())!=’\n’)//从键盘输入字符，直到输入换行符为止 push(&S,ch); //将输入的每个字符入栈while (!stackempty(S))//依次退栈并输出退出的字符{pop( &S , ch ) ;putchar ( ch ) ;}putchar(‘\n’);}（7）数制转换void Decimal_Binary ( ){int N; STACK S; //定义栈结构Sinitstack ( &S ) ; //初始化栈Sscanf(“%d”,&N); //输入十进制正整数scanf(“%d”,&r); //输入正整数r (进制) while (N>0){push( &S , N%2 ); //余数入栈N /= r; //被除数除以r，得到新的被除数}while ( !stackempty(S) )//依次从栈中弹出每一个余数，并输出之 {pop( &S , N );printf(“%d”, N );}（8）检验表达式中的括号匹配情况typedef char ElemType;int Check( ){ STACK S; //定义栈结构Schar ch;initstack(&S); //初始化栈Swhile ((ch=getchar())!=’\n’)//以字符序列的形式输入表达式 If ( ch==‘(’||ch==‘[’|| ch==‘{’) push(&S,ch); //遇左括号入栈//下面是遇右括号的情况（三种）else if( ch== ‘)’ )if (stackempty ( S ) )retrun 0;else{pop(&S,&ch);if ( ch!= ‘(’ )return 0;}else if (ch== ‘]’)if ( stackempty(S) )retrun0;else{pop( &S,&ch) ;if ( ch!= ‘[’ )return 0;}else if ( ch== ‘}’ )if (stackempty(S) )retrun 0;else{pop(&S,&ch);if ( ch!= ‘{’ )return 0;}else continue;if ( stackempty(S) )return 1;elsereturn 0;}（9）Status EvaluateExpression(OperandType &result){InitStack(OPND);InitStack(OPTR);Push(OPTR ,’#’);c=getchar();while( (c!=‘#’) && (GetTop(OPTR)!=‘#’) ){if (!In(c,OP){Push(OPND,c);c=getchar();}elseswitch(compare(c,GetTop(OPTR))){case ‘>’ : Push(OPTR , c);c=getchar();break;case ‘=’: Pop(OPTR);c=getchar();break;case ‘<’ : temat=P op(OPTR);b=Pop();a=Pop();result=Operate(a,temat,b);Push(OPND,result);break;} //switch}//whileresult=GetTop(OPND);}//EvaluateExpression（10）队列初始化操作void initqueue(linkqueue *LQ){LQ->front=LQ->rear=(qlink *) malloc(sizeof(qlink));if(!q->front) exit (0);LQ->front->next=LQ->rear->next=NULL; //初始化队头队尾指针}（11）入队操作void enqueue(linkqueue *LQ, ElemType x)//链队列{ qlink *p;p=(qlink * )malloc(sizeof(qlink));p–>data=x;p–>next=NULL;LQ->rear–>next=p;LQ->rear=p;}int enqueue (cqueue *cq, ElemType x)//循环队列{ if((cq->rear+1)%MAXCSIZE == cq->front) return 0;cq->base[cq->rear]=x; //插入x值到队尾cq->rear=(cq->rear+1)%MAXCSIZE; //队尾指针循环后移return 1 ; }（12）出队操作int dequeue ( linkqueue *LQ, ElemType *e) //链队列{ linkqueue *p;if( emptyqueue(Q) ) return 0;p=LQ->front->next;*e=p–>data;LQ->front->next=p–>next;if( LQ->rear == p )LQ->rear=LQ->front;free(p);return OK;}int dequeue (cqueue *cq, ElemType *e) //循环队列{ if ( cq->rear== cq->front ) return 0 ; //队空*e=cq->base[cq->front] ; //e值带回出队元素的值cq->front=(cq->front+1)%MAXCSIZE; //队头指针循环后移return 1 ; }。