第3章 栈与队列(简)ppt课件.ppt

《第3章 栈与队列(简)ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、§3.1栈----线性表应用例一§3.1.1栈的ADT定义§3.1.2栈的表示和实现§3.2栈的应用举例1.数制转换2.括号匹配的检验3.行编辑5.算术表达式求值§3.3栈与递归的实现§3.4队列----线性表应用例二§3.4.1队的ADT定义§3.4.2链队§3.4.3循环队第三章栈和队列要点栈—递归，队，运算实现作业245815182831栈和队列是在软件设计中常用的两种数据结构，它们的逻辑结构和线性表相同。其特点在于运算受到了限制：栈按“后进先出”的规则进行操作，队按“先进先出”的规则进行操作，故称运算受限制的线性表。总

2、述从数据结构的角度看:它们和线性表相同从数据类型的角度看:它们和线性表不同插入删除线性表Insert(L,i,x)Delete(L,i)(1<=i<=n+1)(1<=i<=n)栈Insert(S,n+1,x)Delete(S,n)队列Insert(Q,n+1,x)Delete(Q,1)§3.1.1栈的ADT定义解决某种问题特别好用【定义】是限定仅在表尾进行插入或删除操作的线性表栈----线性表应用例一定义仅是在线性表上规定了操作点操作受限的﹑线性的后进先出线性表LIFO允许插入、删除的这一端称为栈顶top另一个固定端称为栈底

3、bottom。当表中没有元素时称为空栈§3.1栈Top〖例〗洗盘摞起a1a2a3a4a5a6a6a5a6a5baseTopTo其它没有，因为仅在线性表的一头操作，运算少了许多。⑴栈初始化InitStack(&s)栈S不存在,构造一个空栈⑵销毁栈DstoryStack(&s)栈S存在,将S销毁(3)清为空栈ClearStack(&s)栈S存在,将S清空⑷判栈空StackEmpty(s)栈S已存在,若S为空栈返回TRUE否则返回FALSE(5)求栈长Stacklength(s)栈S存在,返回S的元素个数(6)读栈顶元素GeTo

4、p(s,&e)栈S存在且非空,返回栈顶元素e(7)入栈Push(&s,e)栈S已存在,在S顶部插入新栈元e(8)出栈Pop(&s,&e)栈S存在且非空,删除栈S顶元,用e返回其值(9)遍历栈StackTraverse(s,visit())依次对栈调用visit()§3.1栈对于栈，常做的基本运算有9个P45一、栈的顺序存储结构P46由于栈是运算受限的线性表，因此线性表的存储结构对栈也是适用的，只是操作点不同而已。#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10typedefstruct

5、{SElemType*base;SElemType*top;intstacksize;}sqstack;说明top指向栈顶元素的下一个位置，即待接收数据的位置top=base空栈top=base+stacksize栈满补添存储补10topbase初始100§3.1.2栈的表示和实现IObase空栈a进栈b进栈atopbasetopbasetopabbasee进栈f进栈溢出e出栈edcbatopbasetopbasetopedcbadcba约定：top指向栈顶元素的下一个位置一、栈的顺序存储结构P46顺序栈的初始化首先建立栈空间，

6、然后初始化栈顶指针。§3.1.2栈的表示和实现statusInitStack(SqStack&s){s.base=(SElemtype*)malloc(STACK_INIT_SIZE*sizeof(SElemtype));if(!s.base)exit(OVERFLOW)；s.top=s.base;s.stacksize=STACK-INIT-SIZE;returnOk;}//InitStack顺序栈的取栈顶元statusGetTop(SqStacks,SElemType&e){if(s.top==s.base)returnERROR

7、;e=*(S.top-1);returnOk;}//GetTop出栈和取栈顶元，先判栈是否为空为空时不能操作，否则产生错误。通常栈空作为一种控制转移的条件顺序栈入栈statusPush(SqStack&s,SElemTypee){if(s.top-s.base>=s.stacksize){s.base=(SElemType*)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(SElemType));if(!s.base)exit(OVERFLOW)；s.top=s.base+s.s

8、tacksize;s.stacksize+=STACKINCREMENT;}*s.top++=e;returnOK;}//Push}对于顺序栈，入栈时先判栈是否满了，栈满时不能入栈;否则出现空间溢出，引起错误，这种现象