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