数据结构教程第十课栈的表示与实现

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

栈尾称为栈顶，栈头称为栈底，没有元素的空表称为/[/表
Stack的抽象数据类型定义:
ADT Stack{
数据对象:d = {AI | AI (-elemset，I = 1，2，...，N，n > = 0}
数据关系:R1 = {| N}
基本操作:
InitStack(&S)构造一个空stack S
destroy stack(& S)如果stack S存在，则销毁stack S
clear stack(& S)如果stack S存在，则清除为/[/k，如果S存在，则返回TRUE，否则返回FALSE
StackLength(S)如果S存在 它将返回S的顶部元素
Push(&S，E)当栈S存在时，插入的元素E是新的顶部元素
Pop(&S，&e)当栈S存在而不是空时，S的顶部元素被删除并且它的值
StackTraverse(S，如果visit()栈S存在而不是空，对S的每个数据元素调用函数visit() 一旦visit()失败，那么操作失败
}ADT Stack
II。栈的表示和实现
栈的存储方式:
1。顺序堆栈(Sequential stack):一组具有连续地址的存储单元，用于存储从堆栈底部到堆栈顶部的数据元素，并附加一个指针top来指示顺序堆栈中顶部元素的位置
2。
selem type * top；//在栈顶和栈底设置两个指针的目的是判断栈是否为空
int stack size；//堆栈的当前可用容量。
} sq stack；
顺序堆栈的模块描述:
struct stack {
selem type * base；
selem type * top；
int stack size；
}；
typedef结构堆栈Sqstack
Status init stack(sq stack & S)；
Status destroy stack(sq stack & S)；
Status clear stack(sq stack & S)；
Status stack property(sq stack S)；
int stack length(sq stack S)；
Status GetTop(SqStack S，selem type & e)；
状态推送(SqStack &S，selem type e)；
状态弹出(SqStack &S，selem type & e)；
Status stack traverse(sq stack S，Status(* visit)())；

Status INIT STACK(sq STACK & S){
S . base =(selem type *)malloc(STACK _ INIT _ SIZE * sizeof(elem type))；
如果(！S.base)退出(溢出)；
s . top = s . base；
s . STACK SIZE = STACK _ INI _ SIZE；
return OK；
}//in stack
Status destroy stack(sq stack & S)；{
}//destroy stack
Status clear stack(sq stack & S)；{
s . top = s . base；
}//clear stack
Status stack mpty(sq stack S)；{
if(S.top==S.base)返回TRUE
else返回FALSE
}//stack empty
int stack length(sq stack S)；{
int I；selem type * p；
I = 0；
p = s . top；
while(p！= s . base){ p++；i++；}
}//stack length
Status GetTop(sq stack S，selem type & e)；{
if(S.top==S.base)返回错误；
e = *(s . top-1)；
return OK；
}//GetTop
状态推送(SqStack &S，selem type e)；{
if(s . top-s . base > = s . stack size){
s . base =(elem type *)realloc(s . base，
(s . stack size+stack increment)* sizeof(elem type))；
如果(！S.base)退出(溢出)；
s . top = s . base+s . stack size；
s . stack size+= stack increment；
} * s . top++ = e；
return OK；
}//Push
状态弹出(SqStack &S，selem type & e)；{
if(s . top = = s . base)
返回错误；
e = *-s . top；
return OK；
}//Pop
Status stack traverse(sq stack S，Status(* visit)())；{
}//StackTraverse
以上伪代码的C语言源代码
三、总结一下
stack的定义
stack的顺序存储实现。