单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第三章 栈和队列,3.1 栈,3.1.1 抽象数据类型栈的定义,3.1.2 栈的表示和实现,3.2 栈的应用举例,3.2.1 数制转换,3.2.2 括号匹配的检验,3.2.3 行编辑程序,3.2.4 迷宫求解,3.2.5 表达式求值,3.4 队列,3.4.1 抽象数据类型队列的定义,3.4.2 链队列队列的链式表示和实现,3.4.3 循环队列队列的顺序表示和实现,3.1 栈,3.1.1 栈的定义及基本运算,栈(Stack)是限制在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶(Top)，另一端为栈底(Bottom)。当表中没有元素时称为空栈。,假设栈S=(a,1,，a,2,，a,3,，a,n,)，则a,1,称为栈底元素，a,n,为栈顶元素。栈中元素按a,1,，a,2,，a,3,，a,n,的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。因此，栈称为后进先出表（LIFO）。,3.1.2 顺序栈,由于栈是运算受限的线性表，因此线性表的存储结构对栈也适应。,栈的顺序存储结构简称为顺序栈，它是运算受限的线性表。因此，可用数组来实现顺序栈。因为栈底位置是固定不变的，所以可以将栈底位置设置在数组的两端的任何一个端点；栈顶位置是随着进栈和退栈操作而变化的，故需用一个整型变量top,例、一叠书或一叠盘子。,栈的抽象数据类型的定义如下：P,44,a,n,a,n-1,a,2,a,1,栈顶,栈底,top,7 6 5 4 3 2 1,-1,来指示当前栈顶的位置，通常称top为栈顶指针。因此，顺序栈的类型定义只需将顺序表的类型定义中的长度属性改为top即可。顺序栈的类型定义如下：,#define StackSize 100,typedef char datatype;,typedef struct,datatype datastacksize;,int top;,seqstack;,设S是SeqStack类型的指针变量。若栈底位置在向量的低端，即sdata0是栈底元素，那么栈顶指针stop是正向增加的，即进栈时需将s,top加1，退栈时需将stop 减1。因此，stoptop=stacksize-1表示栈满。当栈满时再做进栈运算必定产生空间溢出，简称“上溢”;当栈空时再做退栈运算也将产生溢出，简称“下溢”。上溢是一种出错状态，应该设法避免之；下溢则可能是正常现象，因为栈在程序中使用时，其初态或终态都是空栈，所以下溢常常用来作为程序控制转移的条件。,1、置空栈,void initstack(seqstack*s),stop=-1;,2、判断栈空,int stackempty(seqstack*s),return(stop=-1);,3、判断栈满,int stackfull(seqstack *s),return(stop=stacksize-1);,4、进栈,void push(seqstack *s，datatype x),if(stackfull(s),error(“stack overflow”);,sdata+stop=x;,5、退栈,datatype pop(seqstack*s),if(stackempty(s),error(“stack underflow”);,x=sdatatop;,stop-;,return(x),/return(sdatastop-);,6、取栈顶元素,Datatype stacktop(seqstack *s),if(stackempty(s),error(“stack is enpty”);,return sdatastop;,3.2 栈的应用举例,由于栈结构具有的后进先出的固有特性，致使栈成为程序设计中常用的工具。以下是几个栈应用的例子。,3.2.1 数制转换,十进制N和其它进制数的转换是计算机实现计算的基本问题,其解决方法很多,其中一个简单算法基于下列原理:,N=(n div d)*d+n mod d,(其中:div为整除运算,mod为求余运算),例如(,1348),10,=(2504),8,，,其运算过程如下：,n n div 8 n mod 8,1348 168 4,168 21 0,21 2 5,2 0 2,void conversion(),initstack(s);,scanf(“%”,n);,while(n),push(s,n%8);,n=n/8;,while(!Stackempty(s),pop(s,e);,printf(“%d”,e);,3.2.2 括号匹配的检验,假设表达式中充许括号嵌套,则检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。例：,（）（）（）,3.2.3 行编辑程序,在编辑程序中，设立一个输入缓冲区，用于接受用户输入的一行字符，然后逐行存入用户数据区。允许用户输入错误，并在发现有误时可以及时更正。,行编辑程序算法如下:,void lineedit(),initstack(s);,ch=gether();,while(ch!=eof),while(ch!=eof&ch!=n),switch(ch),case#:pop(s,c);,case :clearstack(s);,default:push(s,ch);,ch=getchar();,clearstack(s);,if(ch!=eof),ch=gethar();,destroystack(s);,3.2.4 迷宫求解,入口,出口,伪代码描述迷宫算法,设定当前位置的初值为入口位置；,do,若当前位置可通，,则将当前位置插入栈顶；,若该位置是出口位置，则结束；,否则切换当前位置的东邻方块为新的当前位置；,否则，若栈不空且栈顶位置还有其他方向未经搜索，,则设定新的当前位置为沿顺时针方向旋转找到的,栈顶位置的下一个邻块；,若栈不空但栈顶位置的四周均不可通，,则删去栈顶位置；,若栈不空，则重新测试新的栈顶位置，直到找到一个可通的相邻块或出栈或栈空；,while(栈不空);,3.2.5表达式求值,表达式求值是程序设计语言编译中的一个最基本问题。它的实现方法是栈的一个典型的应用实例。,在计算机中，任何一个表达式都是由操作数（operand）、运算符（operator）和界限符（delimiter）组成的。其中操作数可以是常数，也可以是变量或常量的标识符；运算符可以是算术运算体符、关系运算符和逻辑符；界限符为左右括号和标识表达式结束的结束符。在本节中，仅讨论简单算术表达式的求值问题。在这种表达式中只含加、减、乘、除四则运算，所有的运算对象均为单变量。表达式的结束符为“#”。,算术四则运算的规则为：,（1）先乘除、后加减；,（2）同级运算时先左后右；,（3）先括号内，后括号外。,计算机系统在处理表达式前，首先设置两个栈：,（1）操作数栈（OPND）：存放处理表达式过程中的操作数。,（2）运算符栈（OPTR）：存放处理表达式过程中的运算符。开始时，在运算符栈中先在栈底压入一个表达式的结束符“#”。,表3-1给出了+、-、*、/、（、）、和#的算术运算符间的优先级的关系。,计算机系统在处理表达式时，从左到右依次读出表达式中的各个符号（操作数或运算符），每读出一个符号后，根据运算规则作如下的处理：,（1）假如是操作数，则将其压入操作数栈，并依次读下一个符号。,（2）假如是运算符，则：,1）假如读出的运算符的优先级大于运算符栈栈顶运算符的优先级，则将其压入运算符栈，并依次读下一个符号。,2）假如读出的是表达式结束符“#”，且运算符栈栈顶的运算符也为“#”，则表达式处理结束，最后的表达式的计算结果在操作数栈的栈顶位置。,3）假如读出的是“（”，则将其压入运算符栈。,4）假如读出的是“）”，则：,A）若运算符栈栈顶不是“（”，则从操作数栈连续退出两个操作数，从运算符栈中退出一个运算符，然后作相应的运算，并将运算结果压入操作数栈，然后继续执行4）。,B）若运算符栈栈顶为“（”，则从运算符栈退出“（”，依次读下一个符号。,5）假如读出的运算符的优先级不大于运算符栈栈顶运算符的优先级，则从操作数栈连续退出两个操作数，从运算符栈中退出一个运算符，然后作相应的运算，并将运算结果压入操作数栈。此时读出的运算符下次重新考虑（即不读入下一个符号）。,图3-7给出了表达式5+(6-4/2)*3的计算过程，最后的结果为T4，置于OPRD的栈顶。,top,6,2,5,(c)读出),作运算T1=4/2=2,top,-,#,(,+,(d)作运算T2=6-2=4,OPRD,top,5,4,OPTR,top,+,#,(,(h)重新考虑#,作运算T4=5+18=23,OPRD,top,23,OPTR,top,#,(g)读#,作运算T3=6*3=18,OPTR,top,+,#,OPRD,top,18,5,(a)初始状态,OPTR,OPND,top,top,#,(b)读出5,+,(,6,-,4,/,2,OPTR,top,/,-,(,+,#,OPRD,top,5,2,4,6,(e)退(,OPTR,OPRD,top,5,4,top,#,+,(f)读出*,3,OPRD,top,3,5,4,OPTR,top,#,+,*,OPRD,OPTR,算法描述,OperandType EvaluateExpression(),/设OPTR和OPND分别为运算符栈和运算数栈,Initstack(OPTR);Push(OPTR,#);,Initstack(OPND);c=getchar();,While(c!=#|Gettop(OPTR)!=#),If(!In(c,OP)Push(OPND,c);c=getchar();/OP是运算符的集合,Else,switch(Precede(Gettop(OPTR),c)/Precede是优先关系,case:/退栈并将运算结果入栈,Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a);,Push(OPND,Operate(a,theta,b);break;,return Gettop(OPND);,3.4 队列,3.4.1 抽象数据类型队列的定义,队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。,例如：排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。因此队列亦称作先进先出(First In First Out)的线性表，简称FIFO表。,当队列中没有元素时称为空队列。在空队列中依次加入元素a,1,a,2,a,n,之后，a,1,是队头元素，a,n,是队尾元素。显然退出队列的次序也只能是a,1,a,2,a,n,，也就是说队列的修改是依先进先出的原则进行的。,下图是队列的示意图：,a,1,a,2,a,n,出队,入队,队头,队尾,队列的抽象数据定义见书,59,3.4.2 循环队列队列的顺序表示和实现,队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表，和顺序表一样，顺序队列也是必须用一个向量空间来存放当前队,列中的元素。由于队列的队头和队尾的位置是变化的，因而要设两个指针和分别指示队头和队尾元素在队列中的位置，它们的初始值地队列初始化时均应置为。入队时将新元素插入所指的位置，然后将加。出队时，删去所指的元素，然后将加并返回被删元素。由此可见，当头尾指针相等时队列为空。在非空队列里，头指针始终指向队头元素，而尾指针始终指向队尾元素的下一位置。,0 1 2 3,Front,rear,a,b,c,Front rear,(a)队列初始为空（b）A,B,C入队,b,c,front rear front,rear,（c)a,出队,(d)b,c,出队，队为空,和栈类似，队列中亦有上溢和下溢现象。此外，顺序队列中还存在“假上溢”现象。因为在入队和出队的操作中