栈是限定仅在表尾进行插入或删除操作的线性表。因此，对栈来说，表尾端有其特殊含义，称为栈顶，相应地，表头端称为栈底。不含元素的空表称为空栈。

假设栈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

凌阳教育，全国唯一一家原厂式嵌入式培训机构，专业从事嵌入式人才培训13年，最近新开课程信息安全工程师培训，想了解更多嵌入式资料下载或者是凌阳教育的动态，请访问凌阳教育官网www.sunplusedu.com。