文档介绍：:栈和队列的应用教学目的:掌握栈和队列的应用方法,理解栈的重要作用教学重点:利用栈实现行编辑,利用栈实现表达式求值教学难点:利用栈实现表达式求值线性表栈队列Insert(L,i,x)(1<=i<=n+1)Insert(S,n+1,x)Insert(Q,n+1,x)Delete(L,i)(1<=i<=n)Delete(S,n)Delete(Q,1)栈和队列是两种特殊的线性表,它们是运算时要受到某些限制的线性表,故也称为限定性的数据结构。从数据结构的角度看:它们和线性表相同从数据类型的角度看:(Stack)是限制仅在表的一端进行插入和删除运算的线性表,通常称插入、删除的这一端为栈顶(Top),另一端为栈底(Bottom)。当表中没有元素时称为空栈。假设栈S=(a1,a2,a3,…an),则a1称为栈底元素,an为栈顶元素。栈中元素按a1,a2,a3,…an的次序进栈,退栈的第一个元素应为栈顶元素。换句话说,栈的修改是按后进先出的原则进行的。因此,栈称为后进先出表(LIFO)。、b、c、d、e,则栈的不可能的输出序列是::(1)置栈空SETNULL(s)(2)判栈空EMPTY(s)(3)入栈PUSH(s,x)(4)出栈POP(s)(5)取栈顶TOP(s),因此线性表的存储结构对栈也适应。栈的顺序存储结构简称为顺序栈,它是运算受限的线性表。因此,可用数组来实现顺序栈。因为栈底位置是固定不变的,所以可以将栈底位置设置在数组的两端的任何一端;栈顶位置是随着进栈和退栈操作而变化的,故需用一个整型变量top来指示当前栈顶位置,通常称top为栈顶指针。因此,顺序栈的类型定义只需将顺序表的类型定义中的长度属性改为top即可。顺序栈的类型定义如下:#definemaxSize100typedefchardatatype;typedefstruct{datatypedata[maxSize];inttop;}seqstack;seqstack*s;。……6543210设S是SeqStack类型的指针变量。若栈底位置在向量的低端,即s–>data[0]是栈底元素,那么栈顶指针s–>top是正向增加的,即进栈时需将s–>top加1,退栈时需将s–>top减1。因此,s–>top<0表示空栈,s–>top=maxsize-1表示栈满。当栈满时再做进栈运算必定产生空间溢出,简称“上溢”;当栈空时再做退栈运算也将产生溢出,简称“下溢”。上溢是一种出错状态,应该设法避免之;下溢则可能是正常现象,因为栈在程序中使用时,其初态或终态都是空栈,所以下溢常常用来作为程序控制转移的条件。