数据结构(第三章-栈和队列).ppt

数据结构第3章栈和队列栈和队列栈和队列是在程序设计中被广泛使用的两种特殊的线性表，它们的特殊性在于对栈和队列的插入和删除操作被限制为只能在表的两端（或一端）进行：L=（a1,a2,a3,ai,an）线性表：在表的任意位置进行插入和删除：栈：只能在表尾进行插入和删除：“后进先出”。队列:只能在表尾进行插入,而在表头删除：“先进先出”。和线性表相比，栈和队列的插入和删除操作受更多的约束和限定，故又称为操作受限（或限定性）的线性表结构。可将线性表和栈及队列的插入和删除操作对比如下：线性表栈队列Insert(L,i,x)Insert(S,n+1,x)Insert(Q,n+1,x)1in+1/表尾/表尾 Delete(L,i)Delete(S,n)Delete(Q,1)1in/表尾/表头栈和队列3.1栈的类型定义3.2栈类型的实现3.3栈的应用举例3.4队列的类型定义3.5队列类型的实现主要内容3.1 栈的类型定义栈的定义：限定仅在表尾进行插入或删除操作的线性表。表尾被称为栈顶，表头被称为栈底,不含元素的空表称空栈。栈的特点：后进先出（lastinfirstout,简称LIFO结构）或先进后出（FILO）栈的定义和特点s=(s=(a1,a2,an)ana1a2.栈底栈顶.入栈出栈栈结构示意图3.1 栈的类型定义栈的抽象数据类型定义 ADTStack数据对象：Dai|aiElemSet,i=12,.,n,n0数据关系：R1|ai-1,aiD,i=2,.,n约定an端为栈顶，a1端为栈底。基本操作：ADTStack3.1 栈的类型定义栈的基本操作InitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(s)StackLength(S)GetTop(S,&e)Push(&S,e)Pop(&S,&e)StackTravers(S,visit()InitStack(&S)操作结果：构造一个空栈S。DestroyStack(&S)初始条件：栈S已存在。操作结果：栈S被销毁。3.1 栈的类型定义栈的基本操作3.1 栈的类型定义栈的基本操作StackEmpty(S)初始条件：栈S已存在操作结果：若栈S为空栈，则返回TRUE，否则FALE。StackLength(S)初始条件：栈S已存在。操作结果：返回S的元素个数，即栈的长度。3.1 栈的类型定义栈的基本操作GetTop(S,&e)初始条件：栈S已存在且非空。操作结果：用e返回S的栈顶元素。ClearStack(&S)初始条件：栈S已存在。操作结果：将S清为空栈。3.1 栈的类型定义栈的基本操作Push(&S,e)初始条件：栈S已存在。操作结果：插入元素e为新的栈顶元素。a1a2ane 3.1 栈的类型定义栈的基本操作Pop(&S,&e)初始条件：栈S已存在且非空。操作结果：删除S的栈顶元素，并用e返回其值。a1a2anan-1 3.2 栈的类型实现顺序栈-栈的顺序存储表示链栈-栈的链式存储表示top=0123450栈空栈顶指针top,指向栈顶元素的下一个空位置，初值为0top123450进栈Atop栈满BCDEF设数组维数为ntop=0,栈空，此时出栈，则下溢top=n,栈满，此时入栈，则上溢toptoptoptoptop出栈123450ABCDEFtoptoptoptoptoptop栈空 类似于线性表的顺序映象实现，可用一维数组实现，定义指向表尾的指针可以作为栈顶指针。a1 an01n-13.2 栈的类型实现顺序栈类型的定义3.2 栈的类型实现用一维数组实现顺序栈的C语言描述栈的顺序存储表示（静态数组）#defineMaxlen100/顺序栈的简单定义IntSMaxlen;/全局变量Inttop;/全局变量，指示栈顶元素位置/结构类型定义typedefstructIntSMaxlen;Inttop;STACK;结构体顺序栈使用例子STACKst;st.Sist.top用静态一维数组实现的缺点：.习惯做法以top=0表示空栈，但是当用C/C+语言表示时，其数组下标从0开始,在实际使用时不方便（无法判断是空栈还是有一个元素）。2.由于栈在使用的过程中，所需最大空间很难确定，用静态数组表示时，限定了最大空间，在实际使用过程中，不能随需求增加。合理的做法：使用动态数组：先为栈分配一个基本量，使用中不够用时再逐步增加。栈的顺序存储表示(动态数组)#defineSTACK_INIT_SIZE100;#defineSTACKINCREMENT10;#defineSElemTypeinttypedefstructSElemType*base;/存储空间基址SElemType*top;/栈顶指针也可inttop；intstacksize;/允许的最大存储空间SqStack;几个约定条件：1.top=base表示栈空(inttop:top=0)2.top-base=stacksize表示栈满(top=stacksize）3.栈顶元素表示：*（top-1）(basetop-1)123M0栈空Top=base3.2 栈的类型实现用一维数组实现顺序栈的C语言描述3.2 栈的类型实现顺序栈基本操作的实现StatusInitStack(SqStack&S)/构造一个最大存储容量为STACK_INIT_SIZE的空栈S。S.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType);if(!S.base)exit(OVERFLOW);/存储分配失败S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;S.top=S.base1234:0栈空栈空3.2 栈的类型实现顺序栈基本操作的实现StatusPush(SqStack&S,SElemTypee)/若栈的存储空间不满，则插入元素e为新的栈顶元素，并返回TRUE；否则返回FALSE。if(S.top-S.base=S.stacksize)/栈满，追加存储空间S.base=(ElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType);if(!S.base)exit(OVERFLOW);/存储分配失败S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;/追加的空间可存储元素数量为STACKINCREMENT*S.top+=e;/把e压入栈顶(先压栈，再top加一)returnOK;3.2 栈的类型实现顺序栈基本操作的实现StatusPop(SqStack&S,SElemType&e)/若栈不空，则删除S的栈顶元素，/用e返回其值，并返回OK；/否则返回ERRORif(S.top=S.base)returnERROR;/栈空e=*-S.top;/先top减一，再去掉栈顶元素returnOK;3.2 栈的类型实现顺序栈基本操作的实现boolGetTop(StackS,ElemType&e)/若栈不空，则用e返回S的栈顶元素，/并返回TRUE，否则返回FALSEif(S.top=S.base)returnFALSE;e=*(S.top-1);/返回非空栈中栈顶元素returnTRUE;intStackLength(StackS);/返回S的元素个数，即栈的长度。return（S.top-S.base）;3.2 栈的类型实现顺序栈基本操作的实现 voidClearStack(Stack&S);/将S置为空栈。S.top=S.base;S.stacksize=STACK_INIT_SIZE;boolStackEmpty(StackS);/若栈S为空栈，则返回TRUE，否则返回FALSE。if(S.top=S.base)returnTRUE；elsereturnFALSE；3.2 栈的类型实现链栈类型的定义结点定义入栈算法StatusPush(Lstack*top,SElemTypee)出栈算法StatusPop(Lstack*top,SElemType&e)typedefstructnodeintdata;structnode*next;LStack;.栈底toptopxptop .栈底topq .top栈底栈顶a1anan-1a1a1anan元素进入链栈（压栈）StatusPush(Lstack*top,SElemTypee)p=(LinkList)malloc(sizeof(LStack);if(!p)return-1;/*申请新结点失败*/p-data=e;p-next=top;/*top指针指向栈顶元素*/top=p;returnOK3.2 栈的类型实现链栈基本操作的实现3.2 栈的类型实现链栈基本操作的实现链栈元素出栈（弹栈）StatusPop(Lstack*top,ElemType&e)/*将栈顶元素出栈*/Lstack*p;if(top=NULL)returnERROR;/*栈空，返回错误标志*/p=top;e=p-data;/*取top指针所指的栈顶元素*/top=p-next;/*修改栈顶指针*/free(p);returnOK;例一、数制转换例二、括号匹配的检验例三、行编辑程序问题例四、迷宫求解例五、表达式求值例六、实现递归3.3 栈的应用举例3.3 栈的应用举例数制转换不同数制间的转换（例如十进制数d进制数）假设待转换的十进制数为N，转化后的数制为d，则：用d不断地去除待转换的十进制数整数N，直到商等于0为止。然后将各次所得余数，以最后一次的余数为d进制数的最高数位，依次排列，即得到所求的d进制数。算法基于原理：N=(Ndivd)d+Nmodd3.3 栈的应用举例数制转换 N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2计计算算顺顺序序输输出出顺顺序序例如：（1348)10=(2504)8，其运算过程如下：3.3 栈的应用举例数制转换算法描述voidconversion()InitStack(S);scanf(%d,N);while(N)Push(S,N%8);/这里转化为8进制数N=N/8;while(!StackEmpty(S)Pop(S,e);printf(%d,e);/conversion 在文字处理软件或编译程序设计时，常常需要检查一个字符串或一个表达式中的括号是否相匹配?匹配思想：从左至右扫描一个字符串(或表达式)，则每个右括号将与最近遇到的那个左括号相匹配。则可以在从左至右扫描过程中把所遇到的左括号存放到堆栈中。每当遇到一个右括号时，就将它与栈顶的左括号(如果存在)相匹配，同时从栈顶删除该左括号。算法思想：设置一个栈，1）当读到左括号时，左括号进栈；2）当读到右括号时，则从栈中弹出一个元素，与读到的左括号进行匹配，若匹配成功，继续读入；否则匹配失败，返回FLASE。3）表达式检验结束时，若栈为空，则匹配正确，否则表明“做括号”多了。3.3 栈的应用举例括号匹配检验3.3 栈的应用举例括号匹配检验算法描述#defineTRUE0#defineFLASE-1SqStackS;S=Init_Stack();/*堆栈初始化*/intMatch_Brackets()charch,x;scanf(“%c”,&ch);while(asc(ch)!=#)/设置#号为结束符if(ch=()|(ch=)push(S,ch);elseif(ch=)x=pop(S);if(x!=)printf(“括号不匹配”);returnFLASE;elseif(ch=)x=pop(S);if(x!=()printf(“(括号不匹配”);returnFLASE;/endwhile括号匹配检验3.3 栈的应用举例括号匹配检验if(S.top!=0)printf(“括号数量不匹配！”);returnFLASE;elsereturnTRUE;/endmain3.3 栈的应用举例行编辑程序问题3.3 栈的应用举例如何实现？思路1：每接收一个字符即存入用户数据区不恰当（不能保证不出差错）思路2：设立一个输入缓冲区（栈结构），用以接受用户输入的一行字符，然后逐行存入用户数据区。在用户输入一行的过程中，允许用户输入出差错，并在发现有误时可以及时更正。行编辑程序问题3.3 栈的应用举例假设从终端接受这样两行字符：whli#ilr#e(s#*s)outchaputchar(*s=#+)；(#为退格符，表示前一个字符无效，为退行符，表示当前行中的字符均无效)则实际有效的是下列两行：while(*s)putchar(*s+)；行编辑程序问题3.3 栈的应用举例算法描述（行编辑问题）VoidLineEdit()/*利用字符栈S，从终端接收一行并传送至调用过程的数据区*/InitStack(S);/构造空栈Sch=getchar();/从终端接收第一个字符while(ch!=EOF)/EOF为全文结束符while(ch!=EOF&ch!=n)/判断结束或是换行switch(ch)case#：Pop(S,c);break;/仅当栈非空时退栈case：ClearStack(S);break;/重置S为空栈default:Push(S,ch);break;/有效字符进栈，未考虑栈满情形ch=getchar();/从终端接收下一个字符将从栈底到栈顶的栈内字符传送至调用过程的数据区；ClearStack(S);/重置S为空栈if(ch!=EOF)ch=getchar();DestroyStack(S);/LineEdit迷宫问题3.3 栈的应用举例求从迷宫入口到出口的所有（简单）路径是一个经典的程序设计问题。计算机解迷宫时，通常用的是“穷举求解”的方法，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止。如果所有可能的通路都试探过，还是不能走到终点，那就说明该迷宫不存在从起点到终点的通道。迷宫问题3.3 栈的应用举例#1234567891012345678910i ij j入口出口迷宫问题3.3 栈的应用举例从演示过程可见：1从入口进入迷宫之后，不管在迷宫的哪一个位置上，都是先往东走，如果走得通就继续往东走；如果在某个位置（当前位置）上往东走不通的话，就依次试探往南、往西和往北方向，从一个走得通的方向继续往前直到出口为止；2如果在某个位置上四个方向都走不通的话，就退回到前一个位置，换一个方向再试，如果这个位置已经没有方向可试了就再退一步，如果所有已经走过的位置的四个方向都试探过了，一直退到起始点都没有走通，那就说明这个迷宫根本不通；迷宫问题3.3 栈的应用举例3所谓走不通不单是指遇到墙挡路，还有已经走过的路不能重复走第二次，它包括曾经走过而没有走通的路。显然为了保证在任何位置上都能沿原路退回，需要用一个后进先出的结构即栈来保存从入口到当前位置的路径。并且在走出出口之后，栈中保存的正是一条从入口到出口的路径。迷宫问题3.3 栈的应用举例求迷宫路径算法的基本思想是l若当前位置“可通”，则纳入路径，继续前进;l若当前位置“不可通”，则后退，换方向继续探索;l若四周“均无通路”，则将当前位置从路径中删除出去。迷宫问题3.3 栈的应用举例设定当前位置的初值为入口位置；do若当前位置可通，则将当前位置插入栈顶；若该位置是出口位置，则算法结束；/此时栈中存放的是一条从入口位置到出口位置的路径否则切换当前位置的东邻方块为新的当前位置；否则/.接下一页求迷宫中一条从入口到出口的路径的算法：迷宫问题3.3 栈的应用举例若栈空，则表明迷宫没有通路。否则若栈不空且栈顶位置尚有其他方向未被探索，则设定新的当前位置为:沿顺时针方向旋转找到的栈顶位置的下一相邻块；若栈不空但栈顶位置的四周均不可通，则删去栈顶位置；/从路径中删去该通道块若栈不空，则重新测试新的栈顶位置，直至找到一个可通的相邻块或出栈至栈空；while(栈不空）；具体伪代码见课本中算法3.3表达式求值3.3 栈的应用举例1）表达式（限于二元运算）的构成操作数+运算符+界符（如括号）2）表达式的求值：例5+6(1+2)-4按照四则运算法则，上述表达式的计算过程为：5+6(1+2)-4=5+63-4=5+18-4=23-4=19表达式中运算符的运算顺序为：+，+，-如何确定运算符的运算顺序？表达式求值3.3 栈的应用举例3）算符优先关系表表达式中任何相邻运算符1、2的优先关系有：12：1的优先级高于2表达式求值3.3 栈的应用举例由四则运算法则，可得到如下的算符优先关系表：+21-*/()#+-*/()#+-*/()#=注：12是相邻算符，1在左2在右表达式求值3.3 栈的应用举例4)算符优先算法我们再来分析一下表达式5+4(1+2)-6计算过程：从左向右扫描表达式：遇操作数保存；遇运算符号 j与前面的刚扫描过的运算符 i比较若 i j则保存 j（后面可能有优先级更高的运算符，已保存的运算符的优先关系为 1 2 3 j则说明 i是已扫描的运算符中优先级最高者，可进行运算；若 i=j则 i为（，j为），说明括号内的式子已计算完，需要消去括号；5+4(1+2)-6表达式求值3.3 栈的应用举例实现算符优先算法，可以使用两个工作栈。一个称作OPTR，用以寄存运算符；另一个称作OPND，用以寄存操作数或运算结果。算法的基本思想是：（1）首先置操作数栈为空栈，表达式起始符“#”为运算符栈的栈底元素；（2）依次读入表达式中的每一个字符，若是操作数则进OPND栈，若是运算符则和OPTR栈的栈顶运算符比较优先权后作相应操作，直至表达式求值完毕（即OPTR栈的栈顶元素和当前读入的字符均为“#”）。表达式求值3.3 栈的应用举例表达式求值示意图：表达式求值示意图：5+65+6(1+2)-4(1+2)-4 toptopbasebaseOPTROPTR栈栈#OPNDOPND栈栈toptopbasebase5 5toptoptoptop+toptop6 6toptoptoptop(toptop1 1toptop+toptop2 2toptoptoptoptoptoptoptop3 3toptoptoptoptoptoptoptoptoptop1818toptoptoptoptoptoptoptop2323toptop-toptop4 4toptoptoptoptoptoptoptop1919toptoptoptoptoptop5 5读入表达式过程：读入表达式过程：+6 6(1 1+2 2)-4 4#=19=191+2=31+2=36 63=183=185+18=235+18=2323-4=1923-4=19表达式求值3.3 栈的应用举例operandTypeEvaluateExpression()/算术表达式求值的算符优先算法。设OPTR和OPND分别为运算符栈和运算数栈，OP为运算符集合。InitStack(OPTR);Push(OPTR,#);InitStack(OPND);c=qetchar();While(c!=#|GetTop(OPTR)!=#)if(!In(c,OP)Push(OPND,c);c=getchar()/不是运算符则进栈,In(c,OP)判断c是否是运算符的函数else表达式求值3.3 栈的应用举例续switch(Precede(GetTop(OPTR),c)case:/新输入的算符c优先级低，即栈顶算符优先权/高,出栈并将运算结果入栈OPNDPop(OPTR,theta);Pop(OPND,b);Pop(OPND,a);Push(OPND,Operate(a,theta,b);break;/switch/whilereturnGetTop(OPND);/EvaluateExpression3.3 栈的应用举例实现递归函数（过程）的嵌套调用：在一个函数内调用另一个函数断断点点r r r r主主程程序序srrrs s函函数数1rst t函函数数2rst函函数数3Call 1Call 2Call 33.3 栈的应用举例实现递归函数嵌套调用1.将所有的实参、返回地址等信息传递给被调用函数保存；2.为被调用函数的局部变量分配存储区；3.将控制转移到被调用函数的入口。-保护断点 当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三项任务：3.3 栈的应用举例实现递归1.保存被调函数的计算结果；2.释放被调函数的数据区；3.依照被调函数保存的返回地址将控制转移到调用函数。-恢复断点从被调用函数返回调用函数之前，应该完成下列三项任务：3.3 栈的应用举例实现递归多个函数嵌套调用的规则是：后调用的，其地址、数据信息先返回！此时的内存管理实行“栈式管理”例如：voidmain()voida()voidb()a();b();/main/a/bMain的数据区函数a的数据区函数b的数据区 3.3 栈的应用举例实现递归递归的执行情况分析递归过程（递归调用）及其实现递归：函数直接或间接的调用自身叫递归调用实现：建立递归工作栈voidprint(intw)inti;if(w!=0)print(w-1);for(i=1;i=w;+i)printf(“%3d,”,w);printf(“n”);return;运行结果：1，2，2，3，3，3，递归工作栈的作用是:一、将递归调用时的实在参数和函数返回地址传递给下一层执行的递归函数；二、保存本层的参数和局部变量，以便从下一层返回时重新使用它们。递归调用执行情况如下：主程序(1)print(w)w=3;3print(2);（1）w=3top(2)w2print(1);（2）w=2（1）w=3top(3)w1print(0);（3）w=1（2）w=2（1）w=3top(4)w0（4）w=0（3）w=1（2）w=2（1）w=3topw(3)输出：2,2(2)2(1)3top(4)输出：1(3)1(2)2(1)3top(2)输出：3,3,3(1)3top返回(3)1(2)2(1)3top(4)0结束(1)3.3 栈的应用举例实现递归教材中还有hanoi塔问题也属于利用栈实现递归问题3.4 队列的类型定义队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表l队尾(rear)允许插入的一端l队头(front)允许删除的一端队列特点：先进先出(FirstInFirstOut,简称FIFO)a1a2a3.an入队出队frontrear队列Q=(a1,a2,an)队列的定义及特点3.4 队列的类型定义队列的抽象数据类型定义ADTQueue数据对象：Dai|aiElemSet,i=1,2,.,n,n0数据关系：R1|ai-1,aiD,i=2,.,n约定其中a1端为队列头，an端为队列尾基本操作：ADTQueueInitQueue(&Q)DestroyQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q,&e)ClearQueue(&Q)DeQueue(&Q,&e)EnQueue(&Q,e)QueueTravers(Q,visit()3.4 队列的类型定义队列的基本操作3.4 队列的类型定义队列的基本操作InitQueue(&Q)操作结果：构造一个空队列Q。DestroyQueue(&Q)初始条件：队列Q已存在。操作结果：队列Q被销毁，不再存在。QueueEmpty(Q)初始条件：队列Q已存在。操作结果：若Q为空队列，则返回TRUE，否则返回FALSE。3.4 队列的类型定义队列的基本操作GetHead(Q,&e)初始条件：Q为非空队列。操作结果：用e返回Q的队头元素。a1a2an QueueLength(Q)初始条件：队列Q已存在。操作结果：返回Q的元素个数，即队列的长度。3.4 队列的类型定义队列的基本操作EnQueue(&Q,e)初始条件：队列Q已存在。操作结果：插入元素e为Q的新的队尾元素。a1a2ane ClearQueue(&Q)初始条件：队列Q已存在。操作结果：将Q清为空队列。3.4 队列的类型定义队列的基本操作DeQueue(&Q,&e)初始条件：Q为非空队列。操作结果：删除Q的队头元素，并用e返回其值。a1a2an 3.5 队列类型的实现一、链队列链式映象二、循环队列顺序映象3.5 队列类型的实现链队列typedefstructQNode/结点类型（存放队列中数据）QElemTypedata;structQNode*next;*QueuePtr；3.5 队列类型的实现链队列typedefstruct/链队列数据类型QueuePtrfront;/队头指针QueuePtrrear;/队尾指针LinkQueue;/由队头指针和队尾指针唯一确定一个队列a1anQ.frontQ.rearQ.frontQ.rear空队列3.5 队列类型的实现链队列基本操作StatusInitQueue(LinkQueue&Q)/构造一个空队列Q，（队头指针和队尾指针都指向头结点）Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front)exit(OVERFLOW);/存储分配失败Q.front-next=NULL;returnOK;a1anQ.frontQ.rear3.5 队列类型的实现链队列基本操作StatusEnQueue(LinkQueue&Q,QElemTypee)/插入元素e为Q的新的队尾元素p=(QueuePtr)malloc(sizeof(QNode);if(!p)exit(OVERFLOW);/存储分配失败p-data=e;p-next=NULL;/生成新结点Q.rear-next=p;/插入队尾（钩链）Q.rear=p;/修改队尾指针指向队尾returnOK;a1anQ.frontQ.rear3.5 队列类型的实现链队列基本操作 StatusDeQueue(LinkQueue&Q,QElemType&e)/若队列不空，则删除Q的队头元素，用e返回其值，并返回OK/否则返回ERRORif(Q.front=Q.rear)returnERROR;/判空p=Q.front-next;e=p-data;/用e返回Q.front-next=p-next;/修改头指针始终指向队首元素if(Q.rear=p)Q.rear=Q.front;/特殊情况处理空队free(p);/释放队首结点returnOK;a1anQ.frontQ.rear3.5 队列类型的实现顺序队列实现：用一维数组实现sqM front=0rear=0123450队空123450frontJ1,J2,J3入队J1J2J3rearrear123450J4,J5,J6入队J4J5J6front设两个指针front,rear,约定：rear指示队尾元素下一位置；front指示队头元素初值：front=rear=0入队列：sqrear+=x;出队列：x=sqfront+;空队列时：front=rearrearrearfrontrear123450J1,J2,J3出队J1J2J3frontfrontfront3.5 队列类型的实现顺序队列存在问题设数组维数为M，则：l当front=0,rear=M时,再有元素入队发生溢出真溢出l当front0,rear=M时,再有元素入队发生溢出假溢出解决方案l队首固定，每次出队后剩余元素向下移动浪费时间l循环队列基本思想：把队列设想成环形，让sq0接在sqM-1之后，若rear+1=M,则令rear=0;0M-11frontrear.3.5 队列类型的实现顺序队列实现：利用“模”运算l入队：sqrear=x;rear=(rear+1)%M;l出队：x=sqfront;front=(front+1)%M;约定：front指向队首元素，rear指向对尾元素的下一个位置。0M-11frontrear.3.5 队列类型的实现顺序队列012345rearfrontJ4J5J6012345rearfrontJ9J8J7J4J5J6012345rearfront初始状态J4,J5,J6出队J7,J8,J9入队队空：front=rear队满：front=rear解决方案：1.另外设一个标志位以区别队空、队满2.少用一个元素空间：队空：front=rear队满：(rear+1)%M=front问题：队满、队空无法判定3.5 队列类型的实现顺序队列#defineMAXQSIZE100/最大队列长度typedefstructQElemType*base;/动态分配存储空间intfront;/头指针，指向队列头元素intrear;/尾指针，指向队列尾元素/的下一个位置SqQueue;循环队列的C/C+语言描述3.5 队列类型的实现顺序队列 StatusInitQueue(SqQueue&Q)/构造一个空队列QQ.base=(ElemType*)malloc(MAXQSIZE*sizeof(ElemType);if(!Q.base)exit(OVERFLOW);/存储分配失败Q.front=Q.rear=0;returnOK;循环队列的基本操作3.5 队列类型的实现顺序队列StatusEnQueue(SqQueue&Q,ElemTypee)/插入元素e为Q的新的队尾元素if(Q.rear+1)%MAXQSIZE=Q.front)returnERROR;/判满Q.baseQ.rear=e;/插入队尾Q.rear=(Q.rear+1)%MAXQSIZE;/队尾指针后移returnOK;循环队列的基本操作J4J5J6012345rearfront3.5 队列类型的实现顺序队列循环队列的基本操作 StatusDeQueue(SqQueue&Q,ElemType&e)/若队列不空，则删除Q的队头元素，用e返回其值，/并返回OK;否则返回ERRORif(Q.front=Q.rear)returnERROR;e=Q.baseQ.front;Q.front=(Q.front+1)%MAXQSIZE;returnOK;J4J5J6012345rearfront3.5 队列类型的实现顺序队列循环队列的基本操作intQueueLength(QueueQ)/返回队列Q中元素个数，即队列的长度return(Q.rear-Q.front+Q.queuesize)%Q.queuesize);l说明：因为在循环队列中，队尾指针的“数值”有可能比队头指针的数值小，因此为避免在求队列长度两者相减时出现负值的情况，因此在队尾与队头相减后加上一个最大容量的值，同时，如果队尾指针值大于对头指针值，二者相减再加上最大容量后会超出队列长度，所以要再进行一次模运算。讨论线性表、栈与队的异同点相同点：逻辑结构相同，都是线性的；都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表（只是对插入、删除运算加以限制）。不同点：运算规则不同，线性表为随机存取，而栈是只允许在一端进行插入和删除运算，因而是后进先出表LIFO；队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。用途不同，线性表比较通用；堆栈用于函数调用、递归和简化设计等；队列用于离散事件模拟、多道作业处理和简化设计等。本章学习要点1.掌握栈和队列类型的特点，并能在相应的应用问题中正确选用它们。2.熟练掌握栈类型的两种实现方法，特别应注意栈满和栈空的条件以及它们的描述方法。3.熟练掌握循环队列和链队列的基本操作实现算法，特别注意队满和队空的描述方法。4.理解递归算法执行过程中栈的状态变化过程。