《栈和队列XU》PPT课件

《《栈和队列XU》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3讲栈和队列主要内容栈的定义及ADT、存储表示及算法栈的应用示例（表达式求值、回溯算法的栈应用）递归算法的使用技巧队列的定义及ADT、存储表示及算法队列的应用示例栈和队列从数据结构的角度看栈和队列也是线性表但其操作是线性表操作的子集栈只能从一端操作，后进先出（LIFO）队列一端只能进，另一端只能出（FIFO）从数据类型的角度看是与线性表不同的两类重要抽象数据类型栈(stack)定义限定只能在表的一端进行插入和删除的特殊的线性表设栈s=（a1，a2，...,ai，...，an），其中a1是栈底元素，an是栈顶元素。后进先出原则LIFO(lastinfir

2、stout)栈顶（top)：允许插入和删除的一端；栈底（base):不允许插入和删除的一端。注意top指向的位置。可以指向栈顶元素可以指向当前栈顶元素上相邻的空位（更常用）a1a2….an入栈出栈栈顶栈底栈的ADTADT见P45注意几个基本操作设置空栈插入新的栈顶元素（入栈操作，push）删除栈顶元素（出栈操作，pop）读取栈顶元素依据其存储结构分为顺序栈栈采用顺序存取结构，称为顺序栈。链栈栈采用链表存取结构，称为链栈。如何实现顺序栈？整个线性表每个元素请你用C或其他语言写出！栈底指针栈顶指针当前栈大小P46数据元素，可有若干个数据项为什么要有栈底指针？

3、设数组S是一个顺序栈，栈的最大容量stacksize=4，初始状态top=010S[4]2310bases[top]=xtop=top+1top102530S[4]2310topbasetop=top-1x=s[top]栈空10进栈30出栈S[4]2310Top=base=0top栈满top=stacksize10253040S[4]2310top=4base顺序栈注意top的位置，空栈如何表达（下溢）？栈满如何表达（上溢）？base·进栈算法(P47)Statuspush(SqStack&S,SElemTypee){//判别栈满if((S.top–S.

4、base)>=S.stacksize){cout<<“overflow”;returnERROR;}*(S.top++)=e;returnOK;}//pusha2a3a4987654321a10topbase出栈算法(P47)：Statuspop(SqStack&S,SElemType&e){if(S.top==S.base)//判别栈空{cout<<“stackempty”;returnERROR;}else{e=*(--S.top);returnOK;}}带回出栈元素a2a3a4987654321a10top其它操作同学自己考虑base链栈x∧to

5、p栈底base采用链式存储结构约定插入、删除等操作只能在表头进行可以不必像单链表那样附加头结点栈顶指针就是链表的头指针如何实现链栈？整个线性表每个元素请你用C或其他语言写出！栈顶指针数据元素，可有若干个数据项指向下一个元素的指针进栈算法Statuslpush(Lstack&s,inte){p=newlnode;p->data=e;p->next=s;s=p;returnOK;}∧baseS栈s进栈元素e其它操作同学自己思考栈原为空，设用S和X分别表示进栈和出栈操作，则对输入序列a,b,c,d和e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为：

6、。栈已经为空，输出序列为：bceda设栈的初始状态和结束状态均为空栈，用S和X分别表示进栈和出栈操作，SXSX合法吗？SXXS合法吗？合法不合法设进栈序列为123，则可能的出栈序列有：123132213231321设进栈序列为123456，下面出栈序列合法吗？135426435612合法不合法，设有一个顺序栈S，元素S1,S2,S3,S4,S5,S6依次进栈，如果6个元素的出栈顺序为S2,S3,S4,S6,S5,S1，则顺序栈的容量至少应为多少？3栈的应用举例---表达式求值算符优先法理解表达式（先只考虑算术四则运算）先乘除，后加减从左到右（结合律）先括

7、号内，后括号外一个表达式由下面组成操作数（常量、变量等）操作符（只考虑/*+-）左右括号（（））和表达式结束符（#）表达式中相继出现算符间的优先关系无非三种，P53表#3X（7–2）#算法思路使用两个栈：运算符栈OPTR和运算数及运算结果栈OPND首先置OPND为空栈，置OPTR栈只有一个栈底元素为#依次读入表达式中字符若是操作数，进OPND栈若操作符，和OPTR栈栈顶元素比较优先级当栈顶元素优先级低“<”，则此字符进OPTR栈；当栈顶元素优先级高“>”，则此操作符出OPTR栈，从OPND栈出两个数，进行操作符指定元素，结果进OPND栈；当栈顶元素优先级

8、一样“=”，则OPTR栈栈顶元素出栈；整个表达式求值完毕（当前读入字符为#，栈顶