三章栈和队列知识讲解.ppt

文档介绍：第三章栈和队列栈栈的应用举例队列栈㈠栈:在表的某一端进行插入和删除操作的线性表。特点:后进先出抽象数据数据类型的定义:ADTStack{数据对象:D={ai|ai∈ElemSet,i=1,2,…,n,n>=0}数据关系:R1={<ai-1,ai>|ai-1,ai∈D,i=2,…,n}约定an端为栈顶,a1端为栈底栈的示意图:a1a2:an栈顶栈底进栈栈顶栈底出栈a2:a1an栈顶栈顶栈顶栈顶栈顶栈顶栈顶栈顶基本操作:InitStack(&s)操作结果:构造一个空栈SDestroyStack(&s)初始条件:栈S已存在操作结果:栈S被销毁ClearStack(&s)初始条件:栈S已存在操作结果:将S清为空栈Push(&s,e)初始条件:栈S已存在操作结果:插入元素e为新的栈顶元素Pop(&s,&e)初始条件:栈S已存在且非空操作结果:删除s的栈顶元素,并用e返回其值StackTraverse(S,visit())初始条件:栈S已存在且非空操作结果:从栈底到栈顶依次对s的每个数据元素调用函数visit()。一旦visit()失败,则操作失败}ADTStack二:栈的表示与实现栈的存储结构(两种)⑴顺序存储结构⑵:利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素结构描述:typedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack;图示:AEDCBABAtopbasebasetoptopbasetopbase栈顶指针和栈中元素之间的关系规定:top指针指向下一个元素进栈的位置空栈条件:=:->=:top指针增加1出栈:top指针减1栈的顺序存储表示:#defineSTACK_INIT_SIZE100;//存储空间初始分配量#defineSTACKINCREMENT10;//存储空间分配增量Typedefstruct{SElemType*base;//在栈构造之前和销毁之后,base的值为NULLSElemType*top;//栈顶指针intstacksize;//当前已分配的存储空间,以元素为单位}SqStack;基本操作的函数原型:StatusInitStack(SqStack&s);//构造一个空栈S