抽象数据类型栈的定义

sunygd · 发表于 2016-8-11 14:05

EDA365欢迎您！

您需要登录才可以下载或查看，没有帐号？注册

x

栈是限定仅在表尾进行插入或删除操作的线性表。因此，对栈来说，表尾端有其特殊含义，称为栈顶，相应地，表头端称为栈底。不含元素的空表称为空栈。
假设栈S=（a1,…,ai-1,ai,…,an），则a1为栈底元素，an为栈顶元素。栈中元素按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端为栈底。
基本操作：
InitStack（&s）
操作结果：构造一个空栈S。
DestroyStack(&S)
初始条件：栈S已存在。
操作结果：栈S被销毁。
ClearStack(&S)
初始条件：栈S已存在。
操作结果：栈S被清为空栈。
StackEmpty(S)
初始条件：栈S已存在。
操作结果：若栈为空栈，则返回TURE,否则FALSE。
StackLength(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()。一旦visit()失败，则操作失效。
}ADT Stack