数据结构-04栈与队列.ppt

《数据结构-04栈与队列.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第四章栈与队列4.1栈4.1.1栈的结构特点和操作4.1.2栈的表示和操作的实现4.2栈的应用举例4.3队列4.3.1队列的结构特点和操作4.3.2队列的表示和操作的实现4.4队列的应用举例4.1栈3.1.1栈的结构特点与操作栈（stack）是限定只能在一端进行插入和删除操作的线性表。其中允许进行插入和删除的一端称为“栈顶（top）”，另一端称为“栈底（bottom）”。数据元素个数为零的栈是“空栈”栈是一种“先进后出（LIFO）”的线性表。例：假设栈中元素以（a1,a2,…,an）的顺序进栈，

2、出栈的第一个元素是an.a1a2…栈顶栈底进栈出栈an出栈的第一个元素为栈顶元素an…a2a1在应用中，常用的栈的基本操作有：InitStack(&s):构造一个空栈S;DestoryStack(&s):销毁一个已存在的栈s；ClearStack(&s):将栈s清为空栈;StackLength(s):返回s的元素个数；StackEmpty（S）：判断栈S是否为空，为空返回“TRUE”，否则，返回“FALSE”；4.1.2栈的基本操作Push(&S，e）：将新元素e插入作为栈S的栈顶。Pop（&S

3、，&e）：删除S的栈顶元素，并用e返回其值。GetTop（S，&e）：用e返回栈顶元素，S保持不变。StackTraverse（S）：从栈底到栈顶依次输出S中的各个元素。4.1.2栈的基本操作4.1.2栈的表示和操作的实现栈有两种表示方法：顺序栈和链栈。1.顺序栈用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，并附设一栈顶指针Top指示栈顶元素在顺序栈中的位置。顺序栈通常用一维数组来实现，并预设一最大数组空间，并且还可以根据需要设一个增补量。1.顺序栈栈的顺序存储表示ConstSTACK

4、_INT_SIZE=100;//初始分配的最大空间量ConstSTACKINCREMENT=10;//增补空间量Typedefstruct{SElemType*elem;//存储空间的基地址inttop;//栈顶指针intsatcksize;//当前分配的最大容量intincrementsize;//约定的增补空间}Sqstack;//stacksize和incrementsize以SElemType为单位用C做描述语言时，通常以top=-1表示顺序栈为空。1.顺序栈基本操作的实现初始化操作vo

5、idInitStack_Sq(Sqstack&S,intmaxsize=STACK_INIT_SIZE,intincresize=STACKINCREMENT){//构造一个最大容量为maxsize的顺序栈S.elem=newSElemType[maxsize];S.top=-1;S.stacksize=maxsize;S.incrementsize=incresize;}//Initstack_Sq复杂度为O(1)取栈顶元素boolGetTop_Sq(SqStackS,SElemType&e)

6、{//若栈不空，用e返回S的栈顶元素，并返回TRUE，否则返回FALSEif(S.top==-1)returnFALSE;e=S.elem[S.top];returnTRUE;}1.顺序栈执行后e=“数据结构”C语言数据结构C语言数据结构S.topS.top将新元素压入栈中的操作：voidPush_Sq(SqStack&S,SElemTypee){//将新元素e压入栈中作为新的栈顶元素if(S.top==S.stacksize)incrementStacksize(S)；//若栈已满，则重新分配

7、存储空间，并追加S.incrementsize个元素空间。S.elem[++S.top]=e;}//Push_Sq1.顺序栈例：已知顺序栈S如图所示，x=“数据结构”执行push(S,x）后的结果为：S.top执行后C语言C语言数据结构S.top1.顺序栈删除栈顶元素的操作boolPop_Sq(SqStack&S,SElemType&e){//若栈不空，则用e返回栈顶元素，并返回TRUE，否则，返回FALSEif(S.top==-1)returnFALSE;e=S.elem[S.top--];r

8、eturnTRUE;}//Pop_Sq复杂度为O(1)1.顺序栈执行后C语言数据结构C语言S.topS.top例：删除栈顶元素的过程1.顺序栈e=“数据结构”顺序栈在使用时受到最大空间容量的限制，在当前栈已满并需要加入新的数据元素的情况下，需要追加存储空间。这是顺序栈在使用时的一个弱点。下面将介绍栈的另一种存储结构——链栈链栈是用链表结构来表示和实现的栈。链栈的结点结构与链表的结点结构相同，包括数据域和指针域两部分。其中，存储数据元素本身的域称为数据域，存储直接后继元素的存储位置的域称为指针域。