数据结构讲义第3章.ppt

第三章栈和队列栈和队列是操作受限的线性表，在计算机科学和程序设计中有广泛的应用。3.1栈3.2栈的应用举例3.3栈与递归3.4队列3.1.2栈的表示与实现1.顺序栈用向量表示栈，附设top指向栈顶位置。3.1.2栈的表示与实现⑴置空栈：首先建立栈空间，然后初始化栈顶指针。voidinitStack(SqStacks){s.top=0;}3.1.2栈的表示与实现⑶入栈intPush(SeqStacks,elemtypex){if(s.top==MAXSIZE-1)return0;/*上溢*/else{s.data[s.top]=x; s.top++; return1; }}⑷出栈intPop(SeqStacks,datatypex){if(Empty_SeqStack(s))return0;/*下溢*/else{s.top--;x=s.data[s.top];return1;}}3.1.2栈的表示与实现3.1.2栈的表示与实现2.链栈3.1.2栈的表示与实现⑴置空栈voidInit_LinkStack（LinkStacktop）{top=NULL;}⑵判栈空intEmpty_LinkStack（LinkStacktop）{if（top==NULL）return1;elsereturn0;}3.1.2栈的表示与实现⑶入栈voidPush（LinkStacktop,ElemTypex）{s=malloc(sizeof(StackNode));s-data=x;s-next=top;top=s;}3.2栈的应用举例1数制转换一个十进制N和其它进制数的转换的简单算法基于下列原理:N=(ndivd)*d+nmodd(其中:div为整除运算,mod为求余运算)例如(1348)10=(2504)8，其运算过程如下：3.2栈的应用举例2括号匹配的检验假设表达式中充许括号嵌套,则检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。例：（（）（）（（）））4表达式求值表达式由运算量、运算符以及其它定义符构成的，有完全确定意义的式子叫表达式中缀表示法在表示表达式时，把运算符写在两个运算量之间的方法叫中缀表示法。如：A＋B后缀表示法在表示表达式时，每一个运算符都紧跟在它所操作的运算量之后的方法叫后缀表示法。如A＋B的后缀表示法为：AB＋3.3栈与递归1递归的概念2递归设计3栈与递归的执行过程3.4队列3.4队列3.4队列3.4队列3.4队列3.4队列

3.4.4、应用实例----停车场管理

习题三设5个元素进栈的先后顺序为A、B、C、D、E，试问能否得到出栈顺序：（1）C、E、A、B、D（2）C、B、A、D、E（3）D、C、A、B、E（4）A、C、B、E、D（5）A、B、C、D、E（6）E、A、B、C、DrearfrontJ1J2rearfrontJ2（a)空队列(b)J1,J2相继入队列(c)J1出队(d)J3,J4和J5相继入队之后,J2出队rearfront-101234rearfrontJ5J4J3又有J6入队,怎么办？

3.4.3循环队列frontrearJ6J4J5312405rear540312frontJ6J7J8J9J4J5frontrear540312(b)队空(c)队满队空、队满都有front=rear如何判断循环队列队空、队满？

J7rear有两种方法：

1）另设一个标志位以区分队空、队满。

2）少用一个存储单元，队满条件front=rear+1;front540312J6J7J8J4J5（d）队满rear3.4.3循环队列#defineMAXSIZE100typedefstruct{