CH3 栈和队列.ppt

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

1、第三章栈和队列栈和队列是两种特殊的线性表，是操作受限的线性表，称限定性DS。3.1栈3.2栈的应用举例3.4队列3.1栈一、抽象数据类型栈的定义：栈（Stack）：是限制在表的一端进行插入和删除运算的线性表。通常称插入、删除的这一端为栈顶(Top)，另一端为栈底(Bottom)。当表中没有元素时称为空栈。假设栈S=(a1，a2，a3，…an)，则a1称为栈底元素，an为栈顶元素。栈中元素按a1，a2，a3，…an的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。因此，栈称为后进先出表（LIFO）。ana1a2……...栈底栈

2、顶...出栈进栈栈s=(a1,a2,……,an)栈的抽象数据类型定义：ADTStack{数据对象：D＝{ai

3、ai∈ElemSet，i＝1，2，……，n，n≥0}数据关系：R1＝{，ai-1，ai∈D，i＝2，……，n}基本操作：}ADTStack二、栈的存储表示二、栈的表示和实现：栈的顺序存储表示－－顺序栈栈的链式存储表示－－链栈1、栈的顺序存储表示：基本思想：利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。栈的顺序存储结构称为顺序栈。顺序栈的实现：可用数组来实现顺序栈。栈底：将栈底位置设置在数组的两端的任何一个端点；栈顶：栈顶位

4、置是随着进栈和退栈操作而变化的，故需用一个整型变量top来指示当前栈顶的位置，通常称top为栈顶指针。顺序栈的定义：Typedefstruct{SElemType*base；//栈底指针，指向栈底位置SElemType*top；//栈顶指针intstacksize；//栈的最大容量}SqStack；栈底指针base：指向顺序栈的栈底位置。若base＝NULL，则表明栈结构不存在。栈顶指针top：栈初始化时指向栈底，即top＝base。非空栈中top指向栈顶元素的下一个位置。新元素入栈时，top加1；删除栈顶元素时，top减1。topbaseAbasetopAB

5、CDEbasetop2、栈的链式存储表示：栈的链式存储结构称为链栈，它是运算受限的单链表，即插入和删除操作仅限制在表头位置上进行。由于只能在链表头部进行操作，故链表没有必要像单链表那样附加头结点。栈顶指针就是链表的头指针。链栈的类型说明：typedefstructStackNode{elemtypedata；structStackNode*next；}StackNode，*LinkStack;∧……datanexttop栈顶栈底三、栈操作的实现：（一）入栈操作：将新元素压入栈中，成为新的栈顶元素。顺序栈：利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素

6、。判栈满；栈满，则重新分配存储空间，转步骤③；栈若未满，则新元素入栈，栈顶指针加1。算法描述：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.stacksize；S.stacksize＋＝STACKINCREMENT；}*S.top＋＋＝e；

7、returnOK；}链栈：利用单链表存储栈中的数据元素。申请新结点；填入新元素；链入链表；重新设置top指针。^…...栈底topxptop申请新结点：p＝（LinkStack）malloc（sizeof（StackNode））；填入新元素：p－>data＝x；链入链表：p－>next＝top；重新设置top指针：top＝p；（二）出栈操作：非空栈的栈顶元素出栈。顺序栈：利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。判栈空；栈空，则操作失败；栈非空，则top减1，取得栈顶元素。算法描述：StatusPop（SqStack&S，SElemType&e

8、）{if（S.top＝＝S.base）returnERROR；e＝*－－S.top；returnOK；}2、链栈：利用单链表存储栈中的数据元素。^…...栈底topptopp＝top；x＝p－>data；top＝top－>next；free（p）；3.2栈的应用举例表达式求值栈与递归的实现1、表达式求值问题表达式：算术表达式，由操作数和运算符组成。例如：3×4＋5/（8－7）运算规则（运算顺序）：先乘除，后加减；从左至右；先括号内，后括号外。运算符优先级的高低决定了表达式的运算顺序——算符优先法。任意两个相继出现的运算符θ1和θ2之间的优先关系：θ1<θ2θ1

9、的优先级低于θ2θ1＝θ2θ1的优先级