3、栈的表示和操作的实现

3.3.1 栈的抽象数据类型的类型定义

InitStack(&S) 初始化操作

操作结果：构造出一个空栈 S

DestroyStack(&S) 摧毁栈操作

初始条件：栈 S 已存在

操作结果：栈 S 被摧毁

StackEmpty(S) 判定 S 是否空栈

初始条件：栈 S 已存在

操作结果：若栈 S 为空栈，则返回 true ，否则返回 false

StackLength(S) 求栈的长度

初始条件：栈 S 已存在

操作结果：返回 S 的元素个数，即栈的长度

GetTop(S,&e) 取栈顶元素

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

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

ClearStack(&S) 栈置空操作

初始条件：栈 S 已存在

操作结果：将 S 清为空栈

Push(&S,e) 入栈操作

初始条件：栈 S 已存在

操作结果：插入元素 e 为新的栈顶元素

Pop(&S,&e) 出栈操作

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

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

由于栈本身就是线性表，于是栈也有顺序存储和链式存储两种实现方法。

• 栈的顺序存储 —— 顺序栈

• 栈的链式存储 —— 链栈

3.3..2 顺序栈的表示和实现