…,an)Р栈的逻辑结构?栈的定义和特点?定义:限定仅在表尾进行插入或删除操作的线性表,表尾—栈顶(top),表头—栈底(bottom),不含元素的空表称空栈?特点:先进后出(FILO)或后进先出(LIFO)РanРa1Рa2Р……...Р栈底Р栈顶Р...Р出栈Р进栈Р栈s=(a1,a2,……,an)Р栈的运算:置空栈取栈顶元素判空栈进栈退栈Р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 端为栈底。Р基本操作:Р} ADT StackР栈的抽象数据类型定义Р基本操作:РInitStack(&S)?操作结果:构造一个空栈 S?DestroyStack(&S)?初始条件:栈 S 已存在?操作结果:栈 S 被销毁РStackEmpty(S)?初始条件:栈 S 已存在?操作结果:空栈,返回 TRUE;否则 FALSEРStackLength(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()Р栈的抽象数据类型定义
全文预览
