310计1 5-栈和栈的应用实例.ppt

3.1.1 栈的定义及基本运算 　　 栈(Stack)是限制在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶(Top)，另一端为栈底(Bottom)。当表中没有元素时称为空栈。 假设栈S=(a1，a2，a3，…an)，则a1称为栈底元素，an为栈顶元素。栈中元素按a1，a2，a3，…an的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。因此，栈称为后进先出表（LIFO）。 栈的基本操作除了在栈顶进行插入(入栈)或删除(出栈)外，还有栈的初始化、判空及取栈顶元素下面给出栈的抽象数据类型的定义： 3.1.2 顺序栈　　 由于栈是运算受限的线性表，因此线性表的存储结构对栈也适应。 栈的顺序存储结构简称为顺序栈，它是运算受限的线性表。因此，可用数组来实现顺序栈。因为栈底位置是固定不变的，所以可以将栈底位置设置在数组的两端的任何一个端点；栈顶位置是随着进栈和退栈操作而变化的，故需用一个整型变量top。 3.1.2 顺序栈　　 由于栈是运算受限的线性表，因此线性表的存储结构对栈也适应。 栈的顺序存储结构简称为顺序栈，它是运算受限的线性表。因此，可用数组来实现顺序栈。因为栈底位置是固定不变的，所以可以将栈底位置设置在数组的两端的任何一个端点；栈顶位置是随着进栈和退栈操作而变化的，故需用一个整型变量top来指示当前栈顶的位置，通常称top为栈顶指针。因此，顺序栈的类型定义只需将顺序表的类型定义中的长度属性改为top即可。 顺序栈的类型定义如下： # define StackSize 100 typedef char datatype; typedef struct { datatype data[stacksize]; int top; }seqstack;   设S是SeqStack类型的指针变量。若栈底位置在向量的低端，即s–data[0]是栈底元素，那么栈顶指针s–top是正向增加的，即进栈时需将s–top加1，退栈时需将s–top 减1。因此，s–top0表示空栈， s–top =stacksize-1表示栈满。当栈满时再做进栈运算必定产生空间溢出，简称“上溢”;当栈空时再做退栈运算也将产生溢出，简称“下溢”。上溢是一种出错状态，应该设法避免之；下溢则可能是正常现象，因为栈在程序中使用时，其初态或终态都是空栈，所以下溢常常用来作为程序控制转移的条件。 1、置空栈 void initstack(seqstack *s) { s–top=-1; }2、判断栈空 int stackempty(seqstack *s) { return(s–top==-1); } 3、判断栈满 int stackfull(seqstack *s) { return(s–top==stacksize-1); } 4、进栈 void push(seqstack *s，datatype x) { if (stackfull(s)) error(“stack overflow”); s–data[++s–top]=x; }  5、退栈 int pop(seqstack *s) { if(stackempty(s)) error(“stack underflow”); x=s–data[top]; s–top--; return(x) //return(s–data[s–top--]); } 6、取栈顶元素  int stacktop(seqstack *s) { if(stackempty(s) error(“stack is enpty”); return s–data[s–top]; } 由于栈在使用过程中所需最大空间的大小很难估计，因此，一般来说，在初始化设空栈时不应限定栈的最大容量即，动态分配