3.1.2 栈的抽象数据类型

栈的抽象数据类型定义了栈中的数据对象、数据关系及基本操作。栈的抽象数据类型定义如下：

ADT Stack

{

数据对象：D={a_i|a_i∈ElemSet，i=1，2，…，n，n≥0}

数据关系：R={<a_i-1,a_i>|a_i-1，a_i∈D，i=2，3，…，n}

约定a₁端为栈底，a_n端为栈顶。

基本操作：

（1）InitStack（&S）

初始条件：栈S不存在。

操作结果：建立一个空栈S。

这就像盖房子前，先打了地基，建好框架结构，再准备垒墙。

（2）StackEmpty（S）

初始条件：栈S已存在。

操作结果：若栈S为空，返回1，否则返回0。

栈为空就类似于打好了地基，还没有开始垒墙。栈不为空就类似于开始垒墙。

（3）GetTop（S,&e）

初始条件：栈S存在且非空。

操作结果：返回栈S的栈顶元素给e。

栈顶就像刚垒好的墙的最上面一层砖。

（4）PushStack（&S,x）

初始条件：栈S已存在。

操作结果：将元素x插入到栈S中，使其成为新的栈顶元素。

这就像在墙上放置了一层砖，成为墙的最上面一层。

（5）PopStack（&S,&e）

初始条件：栈S存在且非空。

操作结果：删除栈S的栈顶元素，并用e返回其值。

这就像拆墙，需要把墙的最上面一层从墙上取下来。

（6）StackLength（S）

初始条件：栈S已存在。

操作结果：返回栈S的元素个数。

这就像整个墙有多少层组成。

（7）ClearStack（S）

初始条件：栈S已存在。

操作结果：将栈S清为空栈。

这就像把墙全部拆除。

}ADT Stack

与线性表一样，栈也有两种存储表示：顺序存储和链式存储。