第8章栈和队列第8章栈和队列8.1栈假设栈S=(a1，a2，...，an)，可以形象描述为右图所示形式：a1是栈底元素；an是栈顶元素；入栈指插入数据元素；出栈指删除数据元素；栈的常用运算置空栈—SetNull(S)，完成对栈的初始化。判断栈空—Empty(S)，若栈S为空则返回真，否则返回假。进栈——Push(S，e)，在栈S的栈顶插入数据元素e。出栈—Pop(S)，删除栈S的栈顶数据元素，并将数据元素返回。取栈顶元素—GetTop(S)，取栈S的栈顶数据元素，并把数据元素返回。该操作完成后，栈的状态不变。栈的存储结构有两种：顺序存储结构采用顺序表存储的栈称为顺序栈。链式存储结构。采用单链表存储的栈称为链栈。8.1.1栈的顺序存储表示——顺序栈定义栈的顺序存储结构定义为：typedefstruct{datatypeelements[maxsize]；intTop；}seqstack；其中：maxsize是栈的容量。datatype是栈中数据元素的数据类型。Top指示当前栈顶位置，空栈Top值为-1。栈底位置为0。0顺序栈运算的实现栈初始化voidInitS(seqstack*&S){S=(seqstack*)malloc(sizeof(seqstack));S->Top=-1;}置空栈voidSetNuLLS(seqstack*S){S->Top=-1；}判断栈是否为空intEmptyS(seqstack*s){if(S->Top>=0)return(0)；//栈非空，返回0elsereturn(1)；//栈空，返回1}求栈中元素个数intLengthS(seqstack*S){return(S->Top+1);}进栈intPushS(seqstack*S,datatypee){if(S->Top>=maxsize-1){print(“StackOverflow”)；return0；}//上溢else{S->Top++；S->elements[S->Top]=e；return1；}}出栈intPopS(seqstack*S,datatype&e){if(EmptyS(S)){print(“StackUnderflow”)；return0；}//下溢else{e=S->elements[S->Top];S->Top--;return1；}}取栈顶元素intGetTopS(seqstack*S,datatype&e){if(EmptyS(S)){print(“StackUnderflow”)；return0；}//下溢else{e=S->elements[S->Top];return1；}}8.1.2栈的链式存储结构——链栈定义栈的链式存储结构称为链栈。它是运算受限的单链表，其插入和删除操作仅在表头进行。链栈定义如下：typedefstructNode{datatypeelement;structNode*next;}linkstack;linkstack*top;链栈示意图如右图栈顶是top指针，它惟一地确定一个链栈。当top等于NULL时，该链栈为空栈。链栈运算进栈：voidPushL(linkstack*top,datatypee){linkstack*p;p=(linkstack*)malloc(sizeof(linkstack));p->element=e;p->next=top;top=p;}//链栈不存在上溢的问题出栈：intPopL(linkstack*top,datatype&x){if(top==NULL){print(“Stackisunderflow”);return0;}//下溢else{x=top->element;top=top->next;return1;}}8.1.3栈的应用数制转换十进制N和其它进制数（二、八、十六进制）的转换，基于下列原理:采用除基数取余的方法。例如(1348)10=(2504)8，其运算过程如下：nndiv8nmod8134816841682102125202采用栈存放余数，入栈顺序：4、0、5、2，出栈顺序：2、5、0、4。算法：输入一个非负十进制整数，输出任意进制数（二、八、十六进制）voidConversion(){InitStack(s);scanf(“%d,%d”,&N,&base);//输入十进制数和基数N1=N;while(N1！=0){Push(s,N1%base);//余数入栈N1=N1/base;}while(!EmptyStack(s)){e=Pop(s);//余数出栈if(e>9)printf(“%c”,e+55);//将余数