数据结构ppt课件-第3章-栈和队列

第三章第三章 栈和队列栈和队列【课前思考】【课前思考】1.什么是线性结构？2.你见过餐馆中一叠一叠的盘子吗？如果它们是按1,2,n的次序往上叠的，那么使用时候的次序应是什么样的？3.在日常生活中，为了维持正常的社会秩序而出现的常见现象是什么？第三章栈和队列【课前思考】1第三章第三章 栈和队列栈和队列栈和队列与线性表相比，是限定性的线性表结构。栈的特点：栈必须按“后进先出”的规则进行操作队列特点：必须按“先进先出”的规则进行操作。插入删除线性表：Insert(L,i,x)Delete(L,i)(1in+1)(1in)栈：Insert(L,n+1,x)Delete(L,n)队列：Insert(L,n+1,x)Delete(L,1)第三章栈和队列栈和队列与线性表相比，是限定性的线性表结构21.从“数据结构”的角度看，它们都是线性结构即数据元素之间的关系相同。2.它们是完全不同的数据类型。除了它们各自的基本操作集不同外，主要区别是对插入和删除操作的“限定”。如：线性表允许在表内任一位置进行插入和删除；栈只允许在表尾一端进行插入和删除；队列只允许在表尾一端插入，在表头一端删除。栈和队列与线性表对比：第三章第三章 栈和队列栈和队列1.从“数据结构”的角度看，它们都是线性结构栈和队列33.1 栈栈 3.1.1 栈的类型定义栈的类型定义栈（栈（Stack）是限定只能在表的一端进行插入和删除操作的线性表。允许插入和删除的一端称作“栈顶(top)”不允许插入和删除的另一端称作栈底(bottom)3.1栈3.1.1栈的类型定义栈（4通常称往栈顶插入元素的操作为“入栈”，称删除栈顶元素的操作为“出栈”。栈被称为是一种“后进先出”的结构，又称LIFO（LastInFirstOut的缩写）表。如下图所示的铁路调度站通常称往栈顶插入元素的操作为“入栈”，5栈的类型定义如下：ADT Stack 数据对象：数据对象：Dai|aiElemSet,i=1,2,.,n,n0数据关系：数据关系：R1|ai-1,aiD,i=2,.,n约定an端为栈顶，a1端为栈底。基本操作：基本操作：InitStack(&S)操作结果：构造一个空栈S。DestroyStack(&S)初始条件：栈S已存在。操作结果：栈S被销毁。栈的类型定义如下：6ClearStack(&S)初始条件：栈S已存在。操作结果：将S清为空栈。StackEmpty(S)初始条件：栈S已存在。操作结果：若栈S为空栈，则返回TRUE，否则返回FALSE。StackLength(S)初始条件：栈S已存在。操作结果：返回栈S中元素个数，即栈的长度GetTop(S,&e)初始条件：栈S已存在且非空。操作结果：用e返回S的栈顶元素。ClearStack(&S)初始条件：栈S已存在7Push(&S,e)初始条件：栈S已存在。操作结果：插入元素e为新的栈顶元素。Pop(&S,&e)初始条件：栈S已存在且非空。操作结果：删除S的栈顶元素，并用e返回其值。StackTraverse(S,visit()初始条件：栈S已存在且非空，visit()为元素的访问函数。操作结果：从栈底到栈顶依次对S的每个元素调用函数visit()，一旦visit()失败，则操作失败。ADT StackPush(&S,e)初始条件：栈S已存在。83.1栈栈3.1.2 栈的存储表示和操作的实现栈的存储表示和操作的实现栈也有两种存储表示：顺序存储和链式存储顺序存储结构简称为顺序栈链式存储结构简称为链栈栈顶指针意为指示栈顶元素在栈中的位置，但它的值实际是栈中元素的个数，和顺序表中的length值的意义相同。3.1栈栈也有两种存储表示：顺序存储和链式存储9一、顺序栈类型的定义一、顺序栈类型的定义/结构定义：结构定义：typedef structelemType*base;/存储空间基址inttop;/栈顶指针intstacksize;/允许的最大存储空间以元素为单位Stack;3.1栈栈3.1.2 栈的存储表示和操作的实现栈的存储表示和操作的实现一、顺序栈类型的定义/结构定义：3.1栈10/基本操作接口基本操作接口(函数声明函数声明)：voidInitStack(Stack&S，intmaxsize);/构造一个最大存储容量为maxsize的空栈S。voidDestroyStack(Stack&S);/销毁栈S，S不再存在。voidClearStack(Stack&S);/将S置为空栈。boolStackEmpty(StackS);/若栈S为空栈，则返回TRUE，否则返回FALSEintStackLength(StackS);/返回S的元素个数，即栈的长度。/基本操作接口(函数声明)：11boolGetTop(StackS,ElemType&e);/若栈不空，则用e返回S的栈顶元素，并返回TRUE；/否则返回FALSE。boolPush(Stack&S,ElemTypee);/若栈的存储空间不满，则插入元素e为新的栈顶/元素，并返回TRUE；否则返回FALSE。boolPop(Stack&S,ElemType&e);/若栈不空，则删除S的栈顶元素，用e返回其值，/并返回TRUE；否则返回FALSE。voidStackTraverse(StackS,void(*visit(ElemType)/依次对S的每个元素调用函数visit()，/一旦visit()失败，则操作失败。boolGetTop(StackS,ElemType12voidInitStack(Stack&S，intmaxsize)/构造一个最大存储容量为构造一个最大存储容量为 maxsize 的空栈的空栈 Sif(maxsize=0)maxsize=MAXLISTSIZE;S.base=newSElemTypemaxsize;if(!S.base)exit(1);/存储分配失败S.stacksize=maxsize;S.top=0;/空栈中元素个数为0boolPush(Stack&S,ElemTypee)/若栈的存储空间不满，则插入元素若栈的存储空间不满，则插入元素 e 为新的栈顶元素，为新的栈顶元素，/并返回并返回 TRUE；否则返回；否则返回 FALSEif(S.top=S.stacksize)/栈已满，无法进行插入returnFALSE;*(S.base+S.top)=e;/插入新的元素+S.top;/栈顶指针后移returnTRUE;在此只给出其中在此只给出其中4个函数的定义。个函数的定义。voidInitStack(Stack&S，intm13boolGetTop(StackS,ElemType&e)/若栈不空，则用若栈不空，则用 e 返回返回S的栈顶元素，返回的栈顶元素，返回TRUE；/否则返回否则返回FALSEif(S.top=0)returnFALSE;e=*(S.base+S.top-1);/返回非空栈中栈顶元素S.baseS.top-1return TRUE;bool Pop(Stack&S,ElemType&e)/若栈不空，则删除若栈不空，则删除S的栈顶元素，用的栈顶元素，用 e 返回其值，返回其值，/并返回并返回 TRUE；否则返回；否则返回 FALSE if(S.top=0)return FALSE;e=*(S.base+S.top-1);/返回非空栈中栈顶元素返回非空栈中栈顶元素-S.top;/栈顶指针前移栈顶指针前移return TRUE;Pop和GetTop不同仅在于多一句移动指针的语句。boolGetTop(StackS,ElemType14图中的顺序栈的最大容量为7，当前栈中元素个数为4，因此，我们也可认为栈顶指针总是指在栈顶元素的后面一个位置上。用图表示顺序栈如下：abcdS.topS.stacksize图中的顺序栈的最大容量为7，当前栈中元素个数为15二、链栈链栈即为栈的链式存储结构。结点结构和单链表中的结点结构相同，链栈中不需要头结点，但链栈中指针的方向是从栈顶指向栈底的，正好和单链表是相反的。S.top栈顶栈底3.1栈栈3.1.2 栈的存储表示和操作的实现栈的存储表示和操作的实现二、链栈S.top栈顶栈底3.1栈16结构定义：结构定义：typedef structSLinktop;/栈顶指针intlength;/栈中元素个数Stack;只需对顺序栈的基本操作接口作两处改动，便可作为链栈的基本操作接口。其一：初始化时不需要“maxsize”的参数，因为它不需要事先分配空间其二：在进行入栈操作时，不需要顾忌栈的空间是否已经被填满结构定义：17链栈的基本操作链栈的基本操作void InitStack(Stack&S)/构造一个空栈构造一个空栈 SS.top=NULL;/设栈顶指针的初值为空S.length=0;/空栈中元素个数为0/InitStackvoid Push(Stack&S,ElemType e)/在栈顶之上插入元素在栈顶之上插入元素 e 为新的栈顶元素为新的栈顶元素p=new LNode;/建新的结点建新的结点if(!p)exit(1);/存储分配失败存储分配失败p-data=e;p-next=S.top;/链接到原来的栈顶链接到原来的栈顶S.top=p;/移动栈顶指针移动栈顶指针+S.length;/栈的长度增栈的长度增1/Push链栈的基本操作18boolPop(Stack&S,SElemType&e)/若栈不空，则删除若栈不空，则删除S的栈顶元素，用的栈顶元素，用 e 返回其值，返回其值，/并返回并返回 TRUE；否则返回；否则返回 FALSEif(!S.top)returnFALSE;elsee=S.top-data;/返回栈顶元素q=S.top;S.top=S.top-next;/修改栈顶指针-S.length;/栈的长度减1deleteq;/释放被删除的结点空间returnTRUE;/PopboolPop(Stack&S,SElemType193.2栈的应用举例3.2.1 数制转换数制转换十进制数N和其他d进制数的转换，解决方法很多，其中一个简单算法基于下列原理：N=(N div d)d+N mod d(其中：div为整除运算，mod为求余运算)例如：(1348)10=(2504)81348881684218820052计算过程输出顺序3.2栈的应用举例3.2.1数制转换十20假设现要编制一个满足下列要求的程序：对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数。问题分析：问题很明确，就是要输出计算过程中所得到的各个八进制数位。然而从计算过程可见，这八进制的各个数位产生的顺序是从低位到高位的，而打印输出的顺序从高位到低位，这恰好和计算过程相反。因此，需要先保存在计算过程中得到的八进制数的各位，然后逆序输出，因为它是按后进先出的规律进行的，所以用栈最合适。假设现要编制一个满足下列要求的程序：21算法算法 3.1voidconversion()/对于输入的任意一个非负十进制整数对于输入的任意一个非负十进制整数,输出与其等值的八进制数输出与其等值的八进制数InitStack(S);/构造空栈cinN;/输入一个十进制数while(N)Push(S,N%8);/余数入栈N=N/8;/非零商继续运算/whilewhile(!StackEmpty)/和“求余”所得相逆的顺序输出八进制的各位数Pop(S,e);cout e;/while/conversion算法3.1223.2.2 括弧匹配检验括弧匹配检验假设表达式中允许包含两种括号：圆括号和方括号其正确的匹配：如（）或（）等错误的匹配：（）或（）或()）等现在的问题是，要求检验一个给定表达式中的括弧是否正确匹配？3.2.2括弧匹配检验假设表达式中允许包含两种括23问题分析：方法可用“期待的急迫程度”这个概念来描述。即后出现的“左括弧”，它等待与其匹配的“右括弧”出现的“急迫”心情要比先出现的左括弧高。即：对“左括弧”来说，后出现的比先出现的“优先”等待检。对“右括弧”来说，每个出现的右括弧要去找在它之前“最后”出现的那个左括弧去匹配。显然，保存左括弧的结构用栈最合适。问题分析：24例如考虑下列括号序列：()12345678上面列举的三种错误匹配从“期待匹配”的角度描述即为：1来的右括弧非是所“期待”的；2来的是“不速之客”；3直到结束，也没有到来所“期待”的。这三种情况对应到栈的操作即为：1和栈顶的左括弧不相匹配；2栈中并没有左括弧等在哪里；3栈中还有左括弧没有等到和它相匹配的右括弧。（自练习写算法）例如考虑下列括号序列：(253.2.3迷宫求解问题计算机解迷宫时，通常用的是穷举求解穷举求解的方法什么是迷宫问题？先看两个动画演示的例子（flash3-3-1;3-3-2）3.2.3迷宫求解问题计算机解迷宫时，通常用的是穷举求26问题分析：1从入口进入迷宫之后，不管在迷宫的哪一个位置上，都是先往东走，如果走得通就继续往东走，如果在某个位置上往东走不通的话，就依次试探往南、往西和往北方向，从一个走得通的方向继续往前直到出口为止；2如果在某个位置上四个方向都走不通的话，就退回到前一个位置，换一个方向再试，如果这个位置已经没有方向可试了就再退一步，如果所有已经走过的位置的四个方向都试探过了，一直退到起始点都没有走通，那就说明这个迷宫根本不通；3所谓走不通不单是指遇到墙挡路，还有已经走过的路不能重复走第二次，它包括曾经走过而没有走通的路。问题分析：27显然为了保证在任何位置上都能沿原路退回，需要用需要用一个一个“后进先出后进先出”的结构即栈来保存从入口到当前位置的的结构即栈来保存从入口到当前位置的路径路径。并且在走出出口之后，栈中保存的正是一条从入口到出口的路径。求迷宫中一条路径的算法的基本思想基本思想是：若若当前位置当前位置“可通可通”，则则纳入纳入“当前路径当前路径”，并继续朝，并继续朝“下一位置下一位置”探索；探索；若若当前位置当前位置“不可通不可通”，则则应顺着应顺着“来的方向来的方向”退回到退回到“前一通道块前一通道块”，然后朝然后朝 着除着除“来向来向”之外的其他方向继续探索；之外的其他方向继续探索；若若该通道块的四周四个方块均该通道块的四周四个方块均“不可通不可通”，则则应从应从当前路径当前路径上删除该通道块。上删除该通道块。显然为了保证在任何位置上都能沿原路退回，需要28假设以栈栈S记录记录“当前路径当前路径”，则栈顶栈顶中存放的是存放的是“当当前路径上前路径上最后一个最后一个通道块通道块”。“纳入路径纳入路径”的操作即为的操作即为“当前位置入栈当前位置入栈”；从当前路径上删除前一通道块从当前路径上删除前一通道块的操作即为的操作即为出栈出栈。假设以栈S记录“当前路径”，则栈顶中存放的是“当前路径上最29求迷宫中一条从入口到出口的路径的伪码算法如下：设定当前位置的初值为入口位置；do若若当前位置可通，则则将当前位置插入栈顶；/纳入路径 若若该位置是出口位置，则则算法结束；/此时栈中存放的是一条从入口位置到出口位置的路径否则否则切换当前位置的东邻方块为新的当前位置；求迷宫中一条从入口到出口的路径的伪码算法如下：30否则否则 若若栈不空且栈顶位置尚有其他方向未被探索，则则设定新的当前位置为:沿顺时针方向旋转找到的栈顶位置的下一相邻块；若若栈不空但栈顶位置的四周均不可通，则则删去栈顶位置；/从路径中删去该通道块若若栈不空，则则重新测试新的栈顶位置，直至直至找到一个可通的相邻块或出栈至栈空；while(栈不空栈不空)；否则若栈不空且栈顶位置尚有其他方向未被313.2.4 表达式求值问题表达式求值问题任何一个表达式都是由操作数(operand)、运算符(operator)和界限符(delimiter)组成。其中操作数：常数、标识符运算符：算术运算符、关系运算符和逻辑运算符基本界限符：左右括弧、表达式结束符等以简单的二元运算符的算术表达式二元表达式：操作数1（S1）操作符（OP）操作数2（S2）其中：操作数可以是简单变量，也可以是表达式；而简单变量可以是标识符，也可以是无符号整数。3.2.4表达式求值问题任何一个表达式都是由32问题分析：由于算术运算的规则是：先乘除后加减、先左后右和先括弧内后括弧外，不按其中运算符出现的先后次序。那么怎么办？其中一个方法是先将它转换成另一种形式。在计算机中，对这种二元表达式可以有三种不同的标识方法。假设Exp=S1+OP+S2则称OP+S1+S2为表达式的前缀表示法前缀表示法（简称前缀式前缀式）称S1+OP+S2为表达式的中缀表示法中缀表示法（简称中缀式中缀式）称S1+S2+OP为表达式的后缀表示法后缀表示法（简称后缀式后缀式）问题分析：33例如：若则它的前缀式为：中缀式为：后缀式为：例如：34综合比较它们之间的关系可得下列结论：1三式中的“操作数操作数之间的相对次序相同之间的相对次序相同”；2三式中的“运算符运算符之间的的相对次序不同之间的的相对次序不同”；3中缀式丢失了括弧信息，致使运算的次序不确定；4前缀前缀式的运算规则式的运算规则为：连续出现的两个操作数和在连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式；它们之前且紧靠它们的运算符构成一个最小表达式；5后缀后缀式的运算规则式的运算规则为：运算符运算符在式中出现的顺序恰为表达式的运算顺序；在式中出现的顺序恰为表达式的运算顺序；每个运算符和在它之前出现且紧靠它的两个操作数每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式；构成一个最小表达式；以下就分如何按后缀式进行运算和如何将原表达式转换成后缀式两个问题进行讨论。综合比较它们之间的关系可得下列结论：35如何按后缀式进行运算？“先找运算符，后找操作数。”如：后缀式参看动画flash3-3-5如何按后缀式进行运算？“先找运算符，后找操作数。36运算过程为：对后缀式从左向右“扫描”，遇见操作数则暂时保存，遇见运算符即可进行运算；此时参加运算的两个操作数应该是在它之前刚刚碰到的两个操作数，并且先出现的是第一操作数，后出现的是第二操作数。由此可见，在运算过程中保存操作数的结构应该是个栈。运算过程为：37如何由原表达式转换成后缀式？先分析一下原表达式和后缀式两者中运算符出现的次序有什么不同。例一例一原表达式：后缀式：例二例二原表达式：后缀式：先分析一下原表达式和后缀式两者中运算符出现的次序有什么不同。例一例一原表达式：后缀式：例二例二原表达式：后缀式：如何由原表达式转换成后缀式？先分析一下原表达式和后缀38给每个运算符赋以一个优先数的值，如下所列：运算符优先数优先数高的优先于优先数低的进行运算显然，保存运算符的结构应该是个栈，从栈底到栈顶的运算符的优先数是从低到高的，因此它们运算的先后应是从栈顶到栈底的。给每个运算符赋以一个优先数的值，如下所列：运算符39因此，从原表达式求得后缀式的规则为：1)设立运算符栈栈；2)设表达式的结束符为“#”，为栈底；3)若当前字符是操作数，则直接发送给后缀式；4)若当前字符为运算符且优先数大于栈顶运算符，则进栈，否则退出栈顶运算符发送给后缀式；5)若当前字符是结束符，则自栈顶至栈底依次将栈中所有运算符发送给后缀式；6)“(”对它之前后的运算符起隔离作用，则若当前运算符为“(”时进栈；7)可视为自相应左括弧开始的表达式的结束符，则从栈顶起，依次退出栈顶运算符发送给后缀式直至栈顶字符为(止。因此，从原表达式求得后缀式的规则为：40算法算法3.2voidtransform(charsuffix,charexp)/从合法的表达式字符串从合法的表达式字符串 exp 求得其相应的后缀式求得其相应的后缀式 suffixInitStack(S);Push(S,#);p=exp;ch=*p;while(!StackEmpty(S)if(!IN(ch,OP)Pass(suffix,ch);/直接发送给后缀式elseswitch(ch)case(:Push(S,ch);break;case):Pop(S,c);while(c!=()Pass(suffix,c);Pop(S,c)break;算法3.2voidtransform(chars41 defult:while(!Gettop(S,c)&(precede(c,ch)Pass(suffix,c);Pop(S,c);if(ch!=#)Push(S,ch);break;/defult/switch/elseif(ch!=#)p+;ch=*p;/while/transform算法的时间复杂度为O(n)，其中n为表达式字符串的长度。defult:423.2.5递归函数的实现当一个函数在运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三件事：1)将所有的实在参数、返回地址等信息传递给被调用函数保存；2)为被调用函数的局部变量分配存储区；3)将控制转移到被调用函数的入口。而从被调用函数返回调用函数之前，应该完成：1)保存被调函数的计算结果；2)释放被调函数的数据区；3)依照被调函数保存的返回地址将控制转移到调用函数。当多个函数嵌套调用时，由于函数的运行规则是：后调用先返回，因此各函数占有的存储管理应实行栈式管理栈式管理。3.2.5递归函数的实现当一个函数在运行43假设主函数调用函数A，函数A又调用函数B，显然，在函数B运行期间主函数和函数A占用的存储都不能被覆盖，反之，当函数B运行结束，它所占用的存储区便可释放，同时因为程序控制转移到函数A，当前程序访问的数据自然就是函数A占用的存储区了。假设主函数调用函数A，函数A又调用函数B，显然，在函数44递归函数:类似于多个函数的嵌套调用，差别仅在于调用函数和被调用函数是同一个函数。递归工作栈:递归过程执行过程中所占用的数据区递归工作记录:每一层的递归参数等数据合成一个记录当前活动记录:栈顶记录指示当前层的执行情况当前环境指针:递归工作栈的栈顶指针递归函数:递归工作栈:递归过程执行过程中所占用的数据区45以大家熟悉的hanoi塔问题为例，来看一下栈是如何实现递归函数的问题描述:教材p55-例3-2动画演示看flash3-3-9总结：实现步骤1.先将x盘上的n-1个编号从小到大的盘子借助y盘移动到z盘2.将x盘上的n号盘移动到z盘3.将y盘上的n-1个编号从小到大的盘子借助x盘移动到z盘（1次递归调用）以大家熟悉的hanoi塔问题为例，来看一下46算法算法3.3voidhanoi(intn,charx,chary,charz,int&i)/将塔座将塔座 x 上按直径由小到大且至上而下编号为上按直径由小到大且至上而下编号为1至至 n/的的 n 个圆盘按规则搬到塔座个圆盘按规则搬到塔座 z 上，上，y 可用作辅助塔座。可用作辅助塔座。if(n=1)move(x,1,z);/将编号为1的圆盘从x移到zi+;else hanoi(n-1,x,z,y);/将x上编号为1至n-1的圆盘移到y,z作辅助塔move(x,n,z);/将编号为n的圆盘从x移到zi+;hanoi(n-1,y,x,z);/将y上编号为1至n-1的圆盘移到z,x作辅助塔算法3.3voidhanoi(intn,cha473.3队列3.3.1 队列的类型定义队列的类型定义队列（队列（Queue）是限定只能在表的一端进行插入和在另一端进行删除操作的线性表。允许插入的一端称作“队列尾(tail)”，允许删除的另一端称作队列头(front)。队列的修改是依先进先出的原则进行的，因此队列又称FIFO（FirstInFirstOut的缩写）表3.3队列3.3.1队列的类型定义队列的修改是依先48其类型定义如下：ADTQueue 数据对象数据对象：Dai|aiElemSet,i=1,2,.,n,n0 数据关系数据关系：R1|,ai,ai+1D,i=2,.,n约定其中a1端为队列头,an端为队列尾。基本操作基本操作：InitQueue(&Q)操作结果：构造一个空队列Q。DestroyQueue(&Q)初始条件：队列Q已存在。操作结果：队列Q被销毁，不再存在。ClearQueue(&Q)初始条件：队列Q已存在。操作结果：将Q清为空队列。其类型定义如下：49QueueEmpty(Q)初始条件：队列Q已存在。操作结果：若Q为空队列，则返回TRUE，否则返回FALSE。QueueLength(Q)初始条件：队列Q已存在。操作结果：返回Q的元素个数，即队列的长度。GetHead(Q,&e)初始条件：Q为非空队列。操作结果：用e返回Q的队头元素。EnQueue(&Q,e)初始条件：队列Q已存在。操作结果：插入元素e为Q的新的队尾元素。QueueEmpty(Q)初始条件：队列Q已存在50DeQueue(&Q,&e)初始条件：Q为非空队列。操作结果：删除Q的队头元素，并用e返回其值。QueueTraverse(Q,visit()初始条件：队列Q已存在且非空，visit()为元素的访问函数。操作结果：依次对Q的每个元素调用函数visit()，一旦visit()失败则操作失败。ADT QueueDeQueue(&Q,&e)初始条件：Q为非空队列513.3.2 队列的存储表示和操作的实现队列的存储表示和操作的实现队列也有两种存储表示方法：链式、顺序一、链队列一、链队列链队列是队列的链式存储结构，其结构示意图如下：附加一个头结点，指针方向和线性表一致，“队尾指针(Q.rear)”，指向链队列中的队尾元素结点，“队头指针(Q.front)”，指向链表的头结点，空队列中只含一个其指针域为空的头结点，并且头、尾指针都指向头结点而不为空。3.3.2队列的存储表示和操作的实现队列也有两种存储表示方52链队列的类型定义：/结构定义结构定义typedefSLinkQueuePtr;/链队列的结点结构和单链表相同typedef structQueuePtrfront;/队列的头指针QueuePtrrear;/队列的尾指针intlength;/队列元素个数Queue;/链队列链队列的类型定义：/结构定义typedefSLi53/基本操作接口（函数声明）基本操作接口（函数声明）voidInitQueue(Queue&Q);/构造一个空队列QvoidDestroyQueue(Queue&Q);/销毁队列Q，Q不再存在voidClearQueue(Queue&Q);/将Q置为空队列boolQueueEmpty(QueueQ);/若队列Q为空队列，则返回TRUE，否则返回FALSEintQueueLength(QueueQ);/返回队列Q中元素个数，即队列的长度/基本操作接口（函数声明）54 boolGetHead(QueueQ,ElemType&e);/若队列不空，则用e返回Q的队列头元素，/并返回TRUE；否则返回FALSEvoidEnQueue(Queue&Q,ElemTypee);/在当前队列的尾元素之后插入元素e为新队列尾元素boolDeQueue(Queue&Q,ElemType&e);/若队列不空，则删除当前队列Q中的头元素，/用e返回其值，并返回TRUE；否则返回FALSEvoidQueueTraverse(QueueQ,void(*visit(ElemType)/依次对Q的每个元素调用函数visit()，/一旦visit()失败，则操作失败。boolGetHead(QueueQ,Ele55voidInitQueue(Queue&Q)/构造一个空队列构造一个空队列 Q Q.front=Q.rear=newLNode;if(!Q.front)exit(1);/存储分配失败Q.front-next=NULL;Q.length=0;voidInitQueue(Queue&Q)56voidEnQueue(Queue&Q,ElemTypee)/在当前队列的尾元素之后插入元素在当前队列的尾元素之后插入元素 e 为新队列尾元素为新队列尾元素s=newLNode;if(!s)exit(1);/存储分配失败s-data=e;s-next=NULL;Q.rear-next=s;/修改尾结点的指针Q.rear=s;/移动队尾指针+Q.length;/队列长度增1voidEnQueue(Queue&Q,ElemTyp57boolDeQueue(Queue&Q,ElemType&e)/若队列不空，则删除当前队列若队列不空，则删除当前队列 Q 中的头元素，中的头元素，/用用 e 返回其值，并返回返回其值，并返回 TRUE；否则返回；否则返回 FALSE if(Q.front=Q.rear)/链队列中只有一个头结点returnFALSE;p=Q.front-next;e=p-data;/返回被删元素Q.front-next=p-next;/修改头结点指针if(Q.rear=p)Q.rear=Q.front;deletep;/释放被删结点returnTRUE;/DeQueue链队列的基本操作的时间复杂度，除遍历之外，都是常量级的。boolDeQueue(Queue&Q,ElemTy58二、循环队列循环队列是队列的一种顺序存储表示。循环队列的一种模拟参看动画flash3-3-13利用顺序分配存储结构实现队列时，用一维数组描述队列中数据元素的存储区域，设立两个指针front队头和rear队尾二、循环队列循环队列是队列的一种顺序存储表示。59假设又有两个元素f和g相继入队列，而队列中的元素b和c又相继出队列。致使下一个入队操作无法进行(请注意此时队列空间并未满)。为此，设想这个数组的存储空间是个环，认定7的下一个位置是0。如下图所示。假设又有两个元素f和g相继入队列，而队列中的元素b60循环队列的结构定义如下：typedef struct ElemType*elem;/存储空间基址intrear;/队尾指针intfront;/队头指针intqueuesize;/允许的最大存储空间，以元素为单位Queue;循环队列的结构定义如下：typedefstruct61以下是循环队列的主要操作的函数定义voidInitQueue(Queue&Q，intmaxsize)/构造一个最大存储空间为构造一个最大存储空间为 maxsize 的空队列的空队列 Q if(maxsize=0)maxsize=MAXLISTSIZE;Q.elem=newElemTypemaxsize;/为循环队列分配存储空间if(!Q.elem)exit(1);/存储分配失败Q.queuesize=maxsize;Q.front=Q.rear=0;/InitQueue以下是循环队列的主要操作的函数定义voidInitQue62boolDeQueue(Queue&Q,ElemType&e)/若队列不空，则删除当前队列若队列不空，则删除当前队列Q中的头元素，用中的头元素，用 e 返回其值返回其值/并返回并返回TRUE；否则返回；否则返回 FALSEif(Q.front=Q.rear)returnFALSE;e=Q.elemQ.front;Q.front=(Q.front+1)%Q.queuesize;returnTRUE;boolDeQueue(Queue&Q,ElemTy63boolEnQueue(Queue&Q,ElemTypee)/若当前队列不满，这在当前队列的尾元素之后，若当前队列不满，这在当前队列的尾元素之后，/插入元素插入元素 e 为新的队列尾元素为新的队列尾元素,并返回并返回TRUE,否则返回否则返回FALSEif(Q.rear+1)%Q.queuesize=Q.front)return FALSE;Q.elemQ.rear=e;Q.rear=(Q.rear+1)%Q.queuesize;return TRUE;boolEnQueue(Queue&Q,ElemTyp64intQueueLength(QueueQ)/返回队列返回队列Q中元素个数，即队列的长度中元素个数，即队列的长度return(Q.rear-Q.front+Q.queuesize)%Q.queuesize);/在循环队列中，队尾指针的“数值有可能比队头指针的/数值小，因此为避免在求队列长度两者相减时出现负值/的情况，在作取模运算之前先加上一个最大容量的值。intQueueLength(QueueQ)65循环对列空满的判定参见p63图3.13图3.14存在问题：空：Q.front=Q.rear=0满：Q.front=Q.rear解决方法：1.另设一标志为区别对列是空还是满2.少一个元素空间，约定“对头指针在队尾指针下一个位置上”为满状态的标志循环对列空满的判定参见p63图3.13图3.1466第四节队列应用举例例一例一循环队列应用举例循环队列应用举例编写一个打印二项式系数表（即杨辉三角）的算法。11121133114641第四节队列应用举例例一循环队列应用举例编写一个打67问题分析：这个问题的程序可以有很多种写法1.利用两个数组：一个存放第k行的值，输出第k行的值同时计算第k+1行的值放入第二个数组中。2.引入“循环队列”：可以省略一个数组的辅助空间，且可将一琐碎操作屏蔽起来，使程序结构变得清晰，易理解。问题分析：这个问题的程序可以有很多种写法68若要输出杨辉三角前n行，则队列的最大空间应为n+2。由此从左到右依次输出第k行的值，并将计算所得的第k+1行的值插入队列的基本操作为：doDeQueue(Q,s);/s为二项式系数表第k行中左上方的值GetHead(Q,e);/e为二项式系数表第k行中右上方的值cout0)行行QueueQ;for(i=1;i=n;i+)cout;cout1endl;/在中心位置输出杨辉三角最顶端的“1”InitQueue(Q,n+2);/设置最大容量为n+2的空队列EnQueue(Q,0);/添加行界值EnQueue(Q,1);EnQueue(Q,1);/第一行的值入队列k=1;以下为计算杨辉三角的算法。算法3.4voidya70while(kn)/通过循环队列输出前n-1行的值for(i=1;i=n-k;i+)cout;/输出n-k个空格以保持三角型EnQueue(Q,0);/行界值0入队列do/输出第k行，计算第k+1行Dequeue(Q,s);GetHead(Q,e);if(e)coute;/若e为非行界值0，则打印输出e的值并加一空格elsecoutendl;/否则回车换行，为下一行输出做准备EnQueue(Q,s+e);while(e!=0);k+;/whilewhile(kn)/71DeQueue(Q,e);/行界值0出队列while(!QueueEmpty(Q)/单独处理第n行的值的输出DeQueue(Q,e);coute；/while/yanghui容易看出此算法的时间复杂度为O(n2)。DeQueue(Q,e);/行界值72本章小结在这一章我们学习了栈和队列这两种抽象数据类型栈和对列的特点、存储形式如何判断栈空和栈满，对列空和满这一章的重点则在于栈和队列的应用本章小结在这一章我们学习了栈和队列这两种抽象数据类型73课后习题【基础知识题】【基础知识题】1若按3.1.1节中所示铁道进行车厢调度(注意：两侧铁道均为单向行驶道)，则请回答：(1)如果进站的车厢序列为123，则可能得到的出站车厢序列是什么?(2)如果进站的车厢序列为123456，则能否得到435612和135426的出站序列，并请说明为什么不能得到或者如何得到？2简述栈和线性表的差别。课后习题【基础知识题】1若按3.1.1节中所示铁道进行74