本课主题： 栈的表示与实现
　　教学目的： 栈的数据类型定义、栈的顺序存储表示与实现
　　教学重点： 栈的顺序存储表示与实现方法
　　教学难点： 栈的定义

授课内容：

一、栈的定义

栈是限定仅在表尾进行插入或删除操作的线性表。
栈的表尾称为栈顶，表头称为栈底，不含元素的空表称为空栈。

栈的抽象数据类型定义：

ADT Stack{

数据对象:D={ai

ai(- ElemSet,i=1,2,...,n,n>=0}

数据关系:R1={<ai-1,ai>

ai-1,ai(- D,i=2,...,n}

基本操作:

InitStack(&S) 构造一个空栈S
DestroyStack(&S) 栈S存在则栈S被销毁
ClearStack(&S) 栈S存在则清为空栈
StackEmpty(S) 栈S存在则返回TRUE,否则FALSE
StackLength(S) 栈S存在则返回S的元素个数,即栈的长度
GetTop(S,&e) 栈S存在且非空则返回S的栈顶元素
Push(&S,e) 栈S存在则插入元素e为新的栈顶元素
Pop(&S,&e) 栈S存在且非空则删除S的栈顶元素并用e返回其值
StackTraverse(S,visit())栈S存在且非空则从栈底到栈顶依次对S的每个数据元素调用函数visit()一旦visit()失败,则操作失败
}ADT Stack

二、栈的表示和实现

栈的存储方式：

1、顺序栈:利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,同时附设指针top指示栈顶元素在顺序栈中的位置
2、链栈:利用链表实现

顺序栈的类C语言定义:

typedef struct{
SElemType *base;
SElemType *top; //设栈顶栈底两指针的目的是便于判断栈是否为空
int StackSize; //栈的当前可使用的最大容量.
}SqStack;

顺序栈的的模块说明:

struct STACK {
SElemType *base;
SElemType *top;
int stacksize;
};