文档介绍：第三章栈和队列
栈(stack)
栈的定义和特点
定义:限定仅在表尾进行插入或删除操作的线性表,允许插入和删除的一端称为栈顶(top)(表尾),表头—栈底(bottom),不含元素的空表称空栈
特点:后进先出(LIFO)或先进后出(FILO)
an
a1
a2
……...
栈底
栈顶
...
出栈
进栈
栈s=(a1,a2,……,an)
栈
基本操作:
InitStack(&S)
操作结果:构造一个空栈S。
DestroyStack(&S)
初始条件:栈S已存在。
操作结果:栈S被销毁。
ClearStack(S)
初始条件:栈S已存在。
操作结果:将S清为空栈。
StackEmpty(S)
初始条件:栈S已存在。
操作结果:若栈S为空栈,则返回TRUE,否则返回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()失败,则操作失效。
顺序栈
顺序栈:即栈的顺序存储结构,是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,同时附设指针top指示栈顶元素在顺序栈中的位置。
通常以下述类型说明作为顺序栈的定义:
typedef struct{
SElemType *base; //栈底指针
SElemType *top; //栈顶指针,初始值指向栈底(top=base 栈空)
int stacksize; //栈当前可使用的最大容量
}SqStack;
//常用的基本操作的函数原型说明:
Status InitStack(SqStack &S); //构造一个空栈S
Status ClearStack(SqStack &S); //把S置为空栈
Status StackEmpty(SqStack S); // 判断栈S是否为空
Status GetTop(SqStack S, SElemType &e); //获取栈顶元素
Status Push(SqStack &S, SElemType e); //进栈
Status Pop(SqStack &S, SElemType &e); //出栈
顺序栈的基本操作实现
#define STACK_INIT_SIZE 100;
#define STACKINCREMENT 10;
(1)初始化栈
Status InitStack(SqStack &S){
//构造一个空栈S
=(Selemtype *)malloc(STACK_INIT_SIZE *sizeof(SElemType));
if(!) exit(OVERFLOW); //存储分配失败
=;
= STACK_INIT_SIZE ;
return OK;
}//InitStack
获取栈顶元素
Status GetTop(SqStack S, SElemType &e){
//若栈不空,则用 e 返回S的栈顶元素,并返回OK,否则返回FALSE
if(= =) return ERROR;
e=*(-1);
reutrn OK;
}//GetTop
(3) 进栈
Status Push(SqStack &S, SElemType e){
//插入元素e为新的栈顶元素
if(->=){ //栈满。
=(SElemType *)realloc(, (+ STACKINCREMENT)*sizeof(SElemType));
if(!) exit(OVERFLOW);
=+;
+= STACKINCREMENT;
}
*++=e;
reutrn OK;
}//Push