文档介绍：第三章栈和队列
栈
栈的应用举例
队列
栈
栈的定义及基本运算
栈(Stack)是限制在表的一端进行插入和删除运算的线性表,通常称插入、删除的这一端为栈顶(Top),另一端为栈底(Bottom)。当表中没有元素时称为空栈。
假设栈S = (a1,a2,a3,…an),则a1称为栈底元素,an为栈顶元素。栈中元素按a1,a2,a3,…an的次序进栈,退栈的第一个元素应为栈顶元素。换句话说,栈的修改是按后进先出的原则进行的。因此,栈称为后进先出表(LIFO)。
an
a1
a2
……...
栈底
栈顶
...
出栈
进栈
栈 s=(a1,a2,……,an)
示例:铁路调度站
栈的表示与实现
一、顺序栈
栈的顺序存储结构简称为顺序栈,它是运算受限的线性表。因此,可用数组来实现顺序栈。因为栈底位置是固定不变的,所以可以将栈底位置设置在数组的两端的任何一个端点,用指针base指示;栈顶位置是随着进栈和退栈操作而变化的,故需用一个指针top指示。
栈的示例
//-------栈的顺序存储表示-----------
#define STACK_INIT_SIZE 100
//存储空间初始分配量
#define STACKINCREMENT 10
//存储空间分配增量
typedef int SElemType;
typedef struct{
SElemType * base;
//在栈构造之前和销毁之后,base的值为NULL
SElemType * top; //栈顶指针
int stacksize;
//当前已分配的存储空间,以元素为单位
}SqStack;
顺序栈
//------基本操作的函数原型说明---------
//Status InitStack(SqStack &S);
//构造一个空栈S
//-------------------------------------
//Status DestroyStack(SqStack &S);
//销毁栈S,S不再存在
//-------------------------------------
//Status ClearStack(SqStack &S);
//把S置为空栈
//-------------------------------------
//Status StackEmpty(SqStack S);
//若栈为空栈,则返回TRUE,否则返回FLASE
//-------------------------------------
///int StackLength(SqStack S);
//返回S的元素个数,即栈的长度
//------------------------------------
//Status GetTop(SqStack S,SElemType &e);
//若栈不空,则用e返回S的栈顶元素,并返回OK;否则返回ERROR
//------------------------------------
//Status Push(SqStack &S,SElemType e);
//插入元素e为新的栈顶元素