第三章-栈-队列.ppt

第三章栈和队列胡哲第三章栈和队列栈和队列是两种重要的线性结构。从数据结构的角度看，栈和队列也是线性表，其特殊性在于栈和队列的基本操作是线性表操作的子集，它们是操作受限的线性表。第三章栈和队列3.1.1栈的类型定义3.1.2栈的表示和实现3.2栈的应用举例3.3栈与递归的实现3.4队列3.5离散事件模拟3.1.1栈的类型定义ADTStack{数据对象：D={ai|ai∈ElemSet,i=1,2,…,n,n=0}数据关系：R1={ai-1,ai|ai-1,ai∈D,i=2,..,n}约定an端为栈顶，a1端为栈底基本操作：}ADTStack3.1.1栈的类型定义队列线性表栈队列3.1.1栈的类型定义基本操作：InitStack(S)DestroyStack(S)引用型：StackEmpty(S)StackLength(S)GetTop(S,e)加工型：ClearStack(S)Push(S,e)(入栈)Pop(S,e)(出栈)3.1.1栈的类型定义InitStack(S)操作结果：构造一个空栈SDestroyStack(S)初始条件：栈S已存在操作结果：栈S被销毁ClearStack(S)初始条件：栈S已存在操作结果：将S清为空栈StackEmpty(S)初始条件：栈S已存在操作结果：若栈S为空栈，则返回TRUE，否则FALSE3.1.1栈的类型定义StackLength(S)初始条件：栈S已存在操作结果：返回S的元素个数，即栈的长度GetTop(S,e)初始条件：栈S已存在且非空操作结果：用e返回S的栈顶元素Push(S,e)初始条件：栈S已存在操作结果：插入元素e为新的栈顶元素。Pop(S,e)初始条件：栈S已存在且非空操作结果：删除S的栈顶元素，并用e返回其值3.1.1栈的类型定义StackTraverse(S,visit())初始条件：栈S已存在且非空操作结果：从栈底到栈顶依次对S的每个数据元素调用函数visit()。一旦visit()失败，则操作失效。第三章栈和队列3.1.1栈的类型定义3.1.2栈的表示和实现3.2栈的应用举例3.3栈与递归的实现3.4队列3.5离散事件模拟3.1.2 栈的表示和实现顺序栈链栈顺序栈类似于线性表的顺序映象实现，指向表尾的指针可以作为栈顶指针。//-----栈的顺序存储表示-----#defineSTACK_INIT_SIZE100;#defineSTACKINCREMENT10;typedefstruct{SElemType*base;//栈底指针SElemType*top;//栈顶指针intstacksize;//当前栈大小}SqStack;顺序栈的特点1、若base=NULL,则栈结构不存在；2、若top=base则栈为空；3、当插入新的栈顶元素时，指针top增加1；当删除栈顶元素时，指针top减1；4、非空栈中的栈顶指针始终指向栈顶元素的下一位置；如图所示为栈中元素与栈顶指