资源描述：
《数据结构讲义第3章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第三章栈和队列栈和队列是操作受限的线性表，在计算机科学和程序设计中有广泛的应用。3.1栈3.2栈的应用举例3.3栈与递归3.4队列3.1.1栈的定义栈（stack）是限定在表的同一端进行插入或删除操作的线性表。进行插入或删除操作的一端称为栈顶(top)，另一端称为栈底(bottom)。当表中没有元素时称为空栈。3.1栈a1a2...an栈顶栈底进栈出栈图3.1栈3.1.1栈的定义栈的操作特性：后进先出（lastinfirstout）设栈S=(a1,a2,…,an)。栈中元素按a1,a2,…,an的次序进栈，则退栈的第一个元素为an。栈是又称为后进先出（lastinfirstou
2、t）的线性表（简称LIFO结构）。3.1栈a1a2...an栈顶栈底进栈出栈图3.1栈3.1.1栈的定义例：火车调度，如进栈的车厢序列为1、2、3,则可能的出栈序列有哪些？已知一个栈的入栈序列为1,2,3…,n，其输出序列为p1,p2,…,pn，若pn＝n，则pi为？3.1栈3.1.1栈的基本运算初始化空栈，InitStack(S)；判断栈是否为空栈，StackEmpty(S)；往栈中插入（或称推入）一个元素（入栈），push(S,e)；从栈中删除（或称弹出）一个元素（删除），pop(S)；求栈顶元素的值，GetTop(S)。3.1栈3.1.2栈的表示与实现1.顺序栈用向量表示
3、栈，附设top指向栈顶位置。定义1：#defineMAXSIZE1024typedefstruct{ElemTypedata[MAXSIZE];inttop;}SeqStack；定义2：ElemTypes[MAXSIZE];inttop;3.1.2栈的表示与实现⑴置空栈：首先建立栈空间，然后初始化栈顶指针。voidinitStack(SqStack&s){s.top=0;}⑵判空栈boolStackEmpty(SeqStacks){if(s.top==0)returntrue;elsereturnfalse;}3.1.2栈的表示与实现⑶入栈intPush(SeqStack&s,
4、elemtypex){if(s.top==MAXSIZE-1)return0;/*上溢*/else{s.data[s.top]=x;s.top++;return1;}}⑷出栈intPop(SeqStack&s,datatype&x){if(Empty_SeqStack(s))return0;/*下溢*/else{s.top--;x=s.data[s.top];return1;}}3.1.2栈的表示与实现⑸取栈顶元素elemtypeGetTop(SeqStacks){if(Empty_SeqStack(s))return0;/*栈空*/elsereturn(s.data[s.to
5、p]);}3.1.2栈的表示与实现2.链栈typedefstructnode{ElemTypedata;structnode*next;}StackNode，*LinkStack;LinkStacktop;图3.3链栈示意图top∧⑴置空栈voidInit_LinkStack（LinkStack&top）{top=NULL;}⑵判栈空intEmpty_LinkStack（LinkStacktop）{if（top==NULL）return1;elsereturn0;}3.1.2栈的表示与实现⑶入栈voidPush（LinkStack&top,ElemTypex）{s=malloc
6、(sizeof(StackNode));s->data=x;s->next=top;top=s;}3.1.2栈的表示与实现⑷出栈voidPop(LinkStack&top,datatype&x){if(top==NULL)return;else{x=top->data;p=top;top=top->next;free(p);}}3.1.2栈的表示与实现3.2栈的应用举例1数制转换一个十进制N和其它进制数的转换的简单算法基于下列原理:N=(ndivd)*d+nmodd(其中:div为整除运算,mod为求余运算)例如(1348)10=(2504)8，其运算过程如下：nndiv8nm
7、od8134816841682102125202算法如下：typedefintdatatype;voidconversion(intN，intr){InitStack(s);while(N){Push(s,N%r);N=N/r;}while(!EmptyStack(s)){Pop(s，x);printf(“%d”，x);}}//另一种写法#defineL10voidconversion(intN，intr){ints[L],top;/*定义一个顺序栈*/intx;top=-1;/*初始化栈*
