第3章栈和队列ppt课件.ppt

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

1、第三章栈和队列本章主要内容：•栈和队列的抽象数据类型定义•栈和队列的表示和实现•栈和队列的应用学习目的及要求：•掌握并理解栈和队列是两种特殊的线性结构•掌握栈和队列的抽象数据类型的定义以及表示和实现掌握栈和队列的典型应用3.1栈一、栈的定义二、抽象数据类型栈的定义三、栈的表示和实现四、栈的应用举例3.1.1栈的定义1．定义栈(Stack)——是一种特殊的线性表，其插入和删除操作均在表的一端进行，是一种运算受限的线性表。栈顶(top)——允许插入和删除的一端，又称表尾。栈底(bottom)——栈的另一端，又称表头。若给栈S=(a1,a2…ai,

2、…an)，则a1为栈底元素，an为栈顶元素，如图所示。进栈(push)——在栈顶插入一个元素，又称入栈或压入。出栈(pop)——在栈顶删除一个元素，又称退栈或弹出。空栈——栈中没有元素(n=0)。3.1栈2．栈的特点后进先出(LastInFirstOut，简称LIFO)。又称栈为后进先出表(简称LIFO结构)。3.1栈对栈的操作除了在栈顶进行插入和删除外，还有栈的初始化、判空及取栈顶元素等。其抽象数据类型定义如下：ADTStack{数据对象：D={ai

3、ai∈ElemSet，i=1,2…n，n≥0}数据关系：R={

4、ai-1

5、，ai∈D，i=2,3,…,n}基本操作：InitStack(&s)操作结果：构造一个空栈s。DestroyStack(&s)操作结果：栈s被销毁。ClearStack(&s)操作结果：将s清为空栈。3.1.2抽象数据类型栈的定义3.1栈StackEmpty(s)操作结果：若s为空栈，则返回TRUE，否则FALSE。StackLength(s)操作结果：返回s的元素个数，即栈的长度。GetTop(s,&e)操作结果：用e返回s的栈顶元素。Push(&s,e)操作结果：插入元素e为新的栈顶元素。Pop(&s,&e)操作结果：删除s的栈顶元素，并

6、用e返回其值。StackTrasverse(s,visit())操作结果：从栈底到栈顶依次对s的每个数据元素调用函数visit()。一旦visit()失败，则操作失效。}ADTStack3.1栈两种存储表示方式：顺序存储和链式存储。1.栈的顺序存储及其基本操作的实现(1)栈的顺序存储是利用一块连续的存储单元依次存放栈中的数据元素，并附一个指针top指示当前栈顶。采用顺序存储方式存储的栈称为顺序栈。3.1.3栈的表示和实现3.1栈(2)基本操作的算法①用一维数组和一个栈顶指针A．定义一个栈设栈中数据类型为整型，用stack数组存放栈中数据元素，

7、定义一个栈类型stacktype：typedefintelemtype;#defineMaxSize100;typedefstruct{elemtypestack[MaxSize];inttop;}stacktype;3.1.3.1用静态数组表示栈3.1栈Top指示最后一个元素B．初始化栈：建立一个空栈s，实际上是将栈顶指针指向-1。voidinitstack(stacktype*s){s->top=-1;}C．判断栈是否为空栈：若栈s为空则返回1，否则返回0。intstackempty(stacktypes){if(s.top==-1)re

8、turn(1);elsereturn(0);}top空栈3.1.3.1用静态数组表示栈3.1栈D．进栈：将元素x插入到栈s中。若栈满则显示相应信息，否则指针top增1，将x送入栈顶指针所在位置。Voidpush(stacktype*s,elemtypex){if(s->top==MaxSize-1)printf(“stackoverflow”);else{s->top++;s->stack[s->top]=x;}}3.1.3.1用静态数组表示栈3.1栈E．出栈：从栈中删除栈顶元素。若栈空则显示相应信息，否则栈指针减1，即栈顶为下一个元素的

9、位置。elemtypepop(stacktype*s){elemtypee;if(s->top==-1)printf(“stackunderflow”);else{e=s->stack[s->top];s->top--;}returne;}3.1.3.1用静态数组表示栈3.1栈toptopatopbtopcabtopc进栈出栈ctopebtop3.1.3.1用静态数组表示栈3.1栈F．取栈顶元素：若栈为空则显示相应信息，否则返回栈顶元素，保持栈顶指针不变。Elemtypegettop(stacktypes){if(s.top==-1)pr

10、intf(“stackempty”);elsereturn(s.stack[s.top]);}G.打印栈：voiddisplay(stacktypes){int