中南大学.ppt

文档介绍：中南大学中南大学信息院计科系主讲人:王国军,郑瑾{csgjwang,zhengjin}***@://./电话:[phone]手机:**********办公室:校本部计算机楼406-B本PPT根据《数据结构》教材(清华大学)制作,仅供中南大学计算机科学与技术专业及相关专业11级本科生和任课老师使用。第三章栈和队列栈和队列是限定插入和删除只能在表的“端点”进行的线性表,又称为限定性的线性表。线性表栈队列Insert(L,i,x)Insert(S,n+1,x)Insert(Q,n+1,x)1≤i≤n+1Delete(L,i)Delete(S,n)Delete(Q,1)1≤i≤n栈和队列是两种常用的数据类型。一、栈的类型定义二、栈的表示与实现三、栈的应用举例四、队列的类型定义五、队列的表示与实现提纲一、栈的类型定义定义:限定仅在表尾进行插入和删除操作的线性表,表尾—栈顶,表头—栈底,不含元素的空表称空栈。ana1a2……...栈底栈顶...出栈/弹出入栈/压栈栈S=(a1,a2,……,an)第一部分栈(Stack)表头—表尾—特点:先进后出(FILO)或后进先出(LIFO)。表头(栈底)是固定的,表尾(栈顶)是浮动的栈底元素栈顶元素一、栈的类型定义ADTStack{数据对象:D={ai|ai∈ElemSet,i=1,2,...,n,n≥0}数据关系:R1={<ai-1,ai>|ai-1,ai∈D,i=2,...,n}约定an端为栈顶,a1端为栈底。基本操作:InitStack(&S)操作结果:构造一个空栈SDestroyStack(&S)初始条件:栈S已存在操作结果:销毁栈SClearStack(&S)初始条件:栈S已存在操作结果:将栈置为空栈StackEmpty(&S)初始条件:栈S已存在操作结果:若栈S为空栈则返回TRUE,否则返回FALSEStackLength(&S)初始条件:栈S已存在操作结果:返回栈S中数据元素的个数,即栈的长度GetTop(S,&e)初始条件:栈S已存在操作结果:用e返回栈S的栈顶元素a1a2an……Push(&S,e)初始条件:栈S已存在操作结果:插入元素e为新的栈顶元素a1a2ane……Pop(&S,&e)初始条件:栈S已存在且非空操作结果:删除栈S的栈顶元素,并用e返回其值a1a2anan-1……