冯毅《数据结构》ch3-2知识课件

种常用的数据结构a1a2a3………….an入队出队frontrear队列Q=(a1,a2,……,an)ana1a2……......出栈进栈栈s=(a1,a2,…,an)栈(stack)栈的逻辑结构栈的存储结构栈的应用栈的逻辑结构栈的定义和特点定义:限定仅在表尾进行插入或删除操作的线性表,表尾—栈顶(top),表头—栈底(bottom),不含元素的空表称空栈特点:先进后出(FILO)或后进先出(LIFO)ana1a2……...栈底栈顶...出栈进栈栈s=(a1,a2,……,an)栈的运算:置空栈取栈顶元素判空栈进栈退栈ADTStack{数据对象:D={ai|ai∈ElemSet,i=1,2,...,n,n≥0}数据关系:R1={<ai-1,ai>|ai-1,ai∈D,i=2,...,n}约定an端为栈顶,a1端为栈底。基本操作:}ADTStack栈的抽象数据类型定义基本操作:InitStack(&S)?操作结果:构造一个空栈S?DestroyStack(&S)?初始条件:栈S已存在?操作结果:栈S被销毁StackEmpty(S)?初始条件:栈S已存在?操作结果:空栈,返回TRUE;否则FALSEStackLength(S)?初始条件:栈S已存在?操作结果:返回S的元素个数,即栈的长度ClearStack(&S)?初始条件:栈S已存在?操作结果:将S清为空栈栈的抽象数据类型定义基本操作:GetTop(S,&e)?初始条件:栈S已存在且非空操作结果:用e返回S的栈顶元素Push(&S,e)?初始条件:栈S已存在?操作结果:插入元素e为新的栈顶元素Pop(&S,&e)?初始条件:栈S已存在且非空?操作结果:删除S的栈顶元素,并用e返回其值StackTraverse(S,visit())初始条件:栈S已存在且非空?操作结果:依次对S的每个元素调用函数visit()栈的抽象数据类型定义