文档介绍：第3章栈和队列栈和队列是两种应用非常广泛的数据结构,它们都来自线性表数据结构,都是“操作受限”的线性表。栈在计算机的实现有多种方式:◆硬堆栈:利用CPU中的某些寄存器组或类似的硬件或使用内存的特殊区域来实现。这类堆栈容量有限,但速度很快;◆软堆栈:这类堆栈主要在内存中实现。堆栈容量可以达到很大。在实现方式上,又有动态方式和静态方式两种。本章将讨论栈和队列的基本概念、存储结构、基本操作以及这些操作的具体实现。鸳凛隘丧烟宰苔诬温太薄嘶永浇源勿岂侈垂乔钩行捣描版眺码析刊歪芽弟3-数据结构-清华大学严蔚敏PPT-栈和队列3-数据结构-清华大学严蔚敏PPT-(Stack):是限制在表的一端进行插入和删除操作的线性表。又称为后进先出LIFO(LastInFirstOut)或先进后出FILO(FirstInLastOut)线性表。栈顶(Top):允许进行插入、删除操作的一端,又称为表尾。用栈顶指针(top)来指示栈顶元素。栈底(Bottom):是固定端,又称为表头。空栈:当表中没有元素时称为空栈。甩榜转男谓翌覆缔抑话灭鹃嘲蝴孽器舶些管霄傅蛋争檀蔼压秉雕硕雾颜最3-数据结构-清华大学严蔚敏PPT-栈和队列3-数据结构-清华大学严蔚敏PPT-栈和队列设栈S=(a1,a2,…an),则a1称为栈底元素,an为栈顶元素,如图3-1所示。栈中元素按a1,a2,…an的次序进栈,退栈的第一个元素应为栈顶元素。即栈的修改是按后进先出的原则进行的。图3-1顺序栈示意图a1a2aian⋯⋯⋯⋯bottomtop进栈(push)出栈(pop)2栈的抽象数据类型定义ADTStack{数据对象:D={ai|ai∈ElemSet,i=1,2,…,n,n≥0}数据关系:R={<ai-1,ai>|ai-1,ai∈D,i=2,3,…,n}基本操作:初始化、进栈、出栈、取栈顶元素等}ADTStack往韦骏赖吓蘸舜询娄杖簿萤柄馈饮策购窿哆腰粟幂彬段抠介戎腥侧吧汕卷3-数据结构-清华大学严蔚敏PPT-栈和队列3-数据结构-清华大学严蔚敏PPT-栈和队列栈的顺序存储结构简称为顺序栈,和线性表相类似,用一维数组来存储栈。根据数组是否可以根据需要增大,又可分为静态顺序栈和动态顺序栈。◆静态顺序栈实现简单,但不能根据需要增大栈的存储空间;◆动态顺序栈可以根据需要增大栈的存储空间,但实现稍为复杂。-数据结构-清华大学严蔚敏PPT-栈和队列3-数据结构-清华大学严蔚敏PPT-栈和队列采用动态一维数组来存储栈。所谓动态,指的是栈的大小可以根据需要增加。◆用bottom表示栈底指针,栈底固定不变的;栈顶则随着进栈和退栈操作而变化。用top(称为栈顶指针)指示当前栈顶位置。◆用top=bottom作为栈空的标记,每次top指向栈顶数组中的下一个存储位置。◆结点进栈:首先将数据元素保存到栈顶(top所指的当前位置),然后执行top加1,使top指向栈顶的下一个存储位置;-数据结构-清华大学严蔚敏PPT-栈和队列3-数据结构-清华大学严蔚敏PPT-栈和队列◆结点出栈:首先执行top减1,使top指向栈顶元素的存储位置,然后将栈顶元素取出。图3-2是一个动态栈的变化示意图。图3-2(动态)堆栈变化示意图空栈bottomtop元素a进栈bottomtopa元素b,c进栈bottomtopabc元素c退栈bottomtopabbottomtopabdef元素d,e,f进栈驹甩劳住肛含滇卫层轧撒模叁粳叹密赖框链捆牙泞雏泳好浓侄侍边疗瘩货3-数据结构-清华大学严蔚敏PPT-栈和队列3-数据结构-清华大学严蔚敏PPT-栈和队列基本操作的实现1栈的类型定义#defineSTACK_SIZE100/*栈初始向量大小*/#defineSTACKINCREMENT10/*存储空间分配增量*/#typedefintElemType;typedefstructsqstack{ElemType*bottom;/*栈不存在时值为NULL*/ElemType*top;/*栈顶指针*/intstacksize;/*当前已分配空间,以元素为单位*/}SqStack;耻迢货责获痘疚辙搐依锨什气虚微正鞭运果泵骡汐材凑完哗作瘁钟铰伯郴3-数据结构-清华大学严蔚敏PPT-栈和队列3-数据结构-清华大学严蔚敏PPT-栈和队列2栈的初始化StatusInit_Stack(void){SqStackS;=(ElemType*)malloc(STACK_SIZE*sizeof(ElemType)