文档介绍：CSU中南大学中南大学信息院计科系主讲人:王国军,郑瑾{csgjwang,zhengjin}***@://./电话:0731-88877711手机:**********办公室:校本部计算机楼406-B本PPT根据《数据结构》教材(清华大学)制作,仅供中南大学计算机科学与技术专业及相关专业11级本科生和任课老师使用。第三章栈和队列第三章第三章栈和队列栈和队列栈和队列是限定插入和删除只能在表的“端点”进行的线性表,又称为限定性的线性表。线性表栈队列Insert(L,i, x) Insert(S, n+1, x) Insert(Q, n+1, x)1≤i≤n+1 Delete(L, i) Delete(S, n) Delete(Q, 1)1≤i≤n栈和队列是两种常用的数据类型。一、栈的类型定义二、栈的表示与实现三、栈的应用举例四、队列的类型定义五、队列的表示与实现提纲一、栈的类型定义定义:限定仅在表尾进行插入和删除操作的线性表,表尾—栈顶,表头—栈底,不含元素的空表称空栈。ana1a2……...栈底栈顶...出栈/弹出入栈/压栈栈S=(a1,a2,……,an)第一部分栈(Stack)表头—表尾—特点:先进后出(FILO)或后进先出(LIFO)。表头(栈底)是固定的,表尾(栈顶)是浮动的栈底元素栈顶元素一、栈的类型定义 ADT Stack{数据对象: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……