《3_栈和队列.ppt》由会员分享，可在线阅读，更多相关《3_栈和队列.ppt（86页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1 1第三章第三章 栈和队列栈和队列2 2什么是栈？什么是队列？什么是栈？什么是队列？栈和和队列都是列都是线性表性表但是其操作是受限的但是其操作是受限的a an na a2 2a a1 1栈顶栈顶栈底栈底出栈出栈进栈进栈a a1 1a an-1n-1a an n出队列出队列进队列进队列队首队首队尾队尾3 3本章内容本章内容3.1 栈3.2 栈的的实现3.3 栈的的应用用3.4 队列列3.5 离散事件模离散事件模拟4 43.1 栈栈栈：限定限定仅能在表尾一端能在表尾一端进行插入、行插入、删除操作的除操作的线性表；性表；栈的特点的特点：后：后进先出（先出（LIFO）a an na a2 2a a1
2、 1栈顶栈顶栈底栈底出栈出栈进栈进栈5 5栈的应用栈的应用-函数调用函数调用 当在一个函数的运行期当在一个函数的运行期间调用另一个函数用另一个函数时，在运，在运行行该被被调用函数之前用函数之前，需先完成三，需先完成三项任任务：将所有的将所有的实参数、返回地址等参数、返回地址等信息信息传递给被被调用用函数函数保存保存；为被被调用函数的局部用函数的局部变量量分配存分配存储区区；将将控制控制转移移到被到被调用函数的入口。用函数的入口。6 6从被从被调用函数用函数返回返回调用函数之前用函数之前，应该完成下列三完成下列三项任任务：保存保存被被调函数的函数的计算算结果果；释放放被被调函数的函数的数据区数据
3、区；依照被依照被调函数保存的返回地址将函数保存的返回地址将控制控制转移移到到调用用函数。函数。7 7多个函数嵌套多个函数嵌套调用的用的规则是：是：后后调用先返回用先返回！此此时的内存管理的内存管理实行行“栈式管理式管理”void main()void a()void b()a();b();/main /a /bMain的数据区的数据区函数函数a的数据区的数据区函数函数b的数据区的数据区 8 8 ADT Stack 数据对象：数据对象：数据关系：数据关系：基本操作：基本操作：ADT Stack栈的类型定义栈的类型定义D ai|ai ElemSet,i=1,2,.,n,n0 R1|ai-1,aiD
4、,i=2,.,n 约定约定an 端为栈顶，端为栈顶，a1 端为栈底端为栈底9 9栈的基本操作栈的基本操作结构性操作构性操作InitStack(&S)操作操作结果：果：构造一个空构造一个空栈S。DestroyStack(&S)初始条件：初始条件：栈 S 已存在。已存在。操作操作结果：果：栈 S 被被销毁。1010栈的基本操作栈的基本操作StackEmpty(S)初始条件：初始条件：栈 S 已存在。已存在。操作操作结果：果：若若栈 S 为空空栈，则返回返回 TRUE，否，否则 FALE。StackLength(S)初始条件：初始条件：栈 S 已存在。已存在。操作操作结果：果：返回返回 S 的元素个
5、数，即的元素个数，即栈的的长度。度。1111栈的基本操作栈的基本操作ClearStack(&S)初始条件：初始条件：栈 S 已存在。已存在。操作操作结果：果：将将 S 清清为空空栈。GetTop(S,&e)初始条件：初始条件：栈 S 已存在且非空。已存在且非空。操作操作结果：果：用用 e 返回返回 S 的的栈顶元素。元素。ana2a1栈顶栈顶栈底栈底1212栈的基本操作栈的基本操作Pop(&S,&e)初始条件：初始条件：栈 S 已存在且非空。已存在且非空。操作操作结果：果：删除除 S 的的栈顶元素，并用元素，并用 e 返回其返回其值。ana a2 2a a1 1栈顶栈顶栈底栈底出栈出栈an-1
6、a a2 2a a1 1an-1栈底栈底栈顶栈顶1313栈的基本操作栈的基本操作Push(&S,e)初始条件：初始条件：栈 S 已存在。已存在。操作操作结果：果：插入元素插入元素 e 为新的新的栈顶元素。元素。ana a2 2a a1 1栈顶栈顶栈底栈底进栈进栈栈顶栈顶a an na a2 2a a1 1栈底栈底e e14143.23.2栈类型的实现栈类型的实现1）顺序序栈类似于似于线性表的性表的顺序映象序映象实现，指向表，指向表尾的指尾的指针可以作可以作为栈顶指指针。#define STACK_INIT_SIZE 100#define STACKINCREMENT 10 typedef st
7、ruct SElemType *base;/栈底栈底 SElemType *top;/栈顶栈顶 int stacksize;/栈的大小栈的大小 SqStack;ana a2 2a a1 1basetop151512340ABCDE顺序栈的操作顺序栈的操作可可扩充充栈的操作的操作栈顶指针栈顶指针top，指指向实际栈顶向实际栈顶后的后的下一个位置，初下一个位置，初值为值为 top=basetop进栈进栈A出栈出栈栈当前空间栈当前空间不足，需扩充不足，需扩充BCDE 设栈的初始分配量为设栈的初始分配量为 Stacksize=STACK_INIT_SIZE。若若 top=Stacksize，栈满，此时
8、栈满，此时入栈，则需扩充栈空间，每次扩充入栈，则需扩充栈空间，每次扩充 STACK_INCREMENT；若无可利用的存储空间，则若无可利用的存储空间，则上溢上溢(overflow)。toptoptoptoptoptoptoptoptoptop栈空栈空若若top=base,栈空，此时出栈空，此时出栈，则栈，则下溢下溢(underflow)base栈空栈空topbase base top123401234016161）顺序栈的实现）顺序栈的实现InitStack(SqStack&S)申申请空空间S.top=S.base;Push(SqStack&S,SElemType e)*S.top+=e;但要
9、首先判断但要首先判断栈是否已是否已满if(S.top-S.base=S.stacksize)Pop(SqStack&S,SElemType&e)e=*-S.top;但要先判断但要先判断栈是否空是否空a a2 2a a1 1an-1basetop1717InitStack(SqStack&S)参数：参数：S是存放是存放栈的的结构构变量量功能：功能：建一个空建一个空栈S栈空栈空129900S.base0S.top100S.stacksize1818 Status InitStack(SqStack&S)/构造一个空栈构造一个空栈S/InitStack S.base=(SElemType*)mall
10、oc(STACK_INIT_SIZE*sizeof(ElemType);if(!S.base)exit(OVERFLOW);/存储分配失败存储分配失败 S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;1919Push(SqStack&S,SElemType e)功能：功能：元素元素 e e 进栈。进栈。S.baseS.topS.stacksize1299003100a1a2e3129900S.base2S.top100S.stacksizea1a232020 Status Push(SqStack&S,SElemType e)/Pushif
11、(S.top-S.base=S.stacksize)/栈满，追加存储空栈满，追加存储空间间 S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType);if(!S.base)exit(OVERFLOW);/存储分配失败存储分配失败 S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;return OK;2121Pop(SqStack&S,SElemType&e)出出栈操作栈操作功能：功能：栈顶元素退栈，并用栈顶元素退栈，
12、并用 e e 返回。返回。S.baseS.topS.stacksize129900n-1100a1a2nan-1n-1anS.baseS.topS.stacksize129900n100a1a2nann-1an-12222Status Pop(SqStack&S,SElemType&e)/若栈不空，则删除若栈不空，则删除S的栈顶元素，的栈顶元素，/用用e返回其值，并返回返回其值，并返回OK；/否则返回否则返回ERROR/Pop if(S.top=S.base)return ERROR;e=*-S.top;return OK;2323InitStack(SqStack&S)创建建头结点点Push
13、(SqStack&S,SElemType e)创建新建新节点，并插入到点，并插入到头节点之后点之后Pop(SqStack&S,SElemType&e)先判断先判断栈是否是否为空，若不空，若不为空空则删除第一个除第一个结点点2）链栈的实现）链栈的实现topa1.ana22424小小 结结1 1、栈是限定仅能在表尾一端进行、栈是限定仅能在表尾一端进行插入、删除操作的线性表插入、删除操作的线性表2 2、栈的元素具有后进先出的特点、栈的元素具有后进先出的特点3 3、栈顶元素的位置由一个称为栈、栈顶元素的位置由一个称为栈顶指针的变量指示，进栈和出栈操顶指针的变量指示，进栈和出栈操作都要修改栈顶指针作都要
14、修改栈顶指针25253.3 栈的应用栈的应用例一、例一、数制数制转换例二、例二、括号匹配的括号匹配的检验例三、例三、行行编辑程序程序问题例四、例四、迷迷宫求解求解例五、例五、表达式求表达式求值例六、例六、实现递归2626例一、例一、数制转换数制转换算法基于原理：算法基于原理：N=(N div d)d+N mod d 例如：（1348)10=(?)8NN div 8 N mod 81348168 416821 0212 520 2计计算算顺顺序序输输出出顺顺序序2727例一、例一、数制转换数制转换算法思路：算法思路：用用栈实现先先计算，后算，后输出出操作步操作步骤1.初始化初始化栈InitSta
15、ck(S);2.依次依次计算当的算当的d进制数，并将其制数，并将其压栈Push(S,N%8);N=N/8;3.依次从依次从栈中取出中取出计算的算的结果，并果，并输出出Pop(S,e);4.删除除栈 DestroyStack(S);2828void conversion()/conversionInitStack(S);/步骤步骤1 scanf(%d,N);while(N)/步骤步骤2 Push(S,N%8);N=N/8;while(!StackEmpty(S)/步骤步骤3 Pop(S,e);printf(%d,e);DestroyStack(S);/步骤步骤42929例二、例二、括号匹配的检验
16、括号匹配的检验正确的格式：正确的格式：（）（）（）错误的格式：的格式：（）（）或）或（）（）判断是否正确方法判断是否正确方法检验括号是否匹配括号是否匹配匹配：按照匹配：按照最近匹配原最近匹配原最近匹配原最近匹配原则则匹配：按照匹配：按照期待的急迫程度期待的急迫程度期待的急迫程度期待的急迫程度3030例二、例二、括号匹配的检验括号匹配的检验算法的算法的设计思想：思想：1.凡出凡出现左括弧，左括弧，则进栈；2.凡出凡出现右括弧，首先右括弧，首先检查栈是否空是否空若若栈空，空，则表明表明该“右括弧右括弧”多余，多余，否否则和和栈顶元素比元素比较，若相匹配，若相匹配，则“左括弧出左括弧出栈”，否否则表
17、明不匹配。表明不匹配。3.表达式表达式检验结束束时：1.若若栈空，空，则表明表达式中匹配正确；表明表达式中匹配正确；2.否否则表明表明“左括弧左括弧”有余。有余。3131例三、行编辑程序问题例三、行编辑程序问题在接受用在接受用户输入入时，以一行作，以一行作为基本基本单位位允允许用用户在在输入中及入中及时更正。更正。方法是：方法是：设立一个立一个缓冲区，接受用冲区，接受用户输入的一行字符；入的一行字符；然后逐行存入用然后逐行存入用户数据区；数据区；假假设“#”为退格符，退格符，“”为退行符。退行符。例：例：whli#ilr#e（s#*s)；putchaputchar(*s=#+);while(*
18、s)putchar(*s+);3232例三、行编辑程序问题例三、行编辑程序问题算法思路：算法思路：1、初始化、初始化栈2、依次接受用、依次接受用户输入的字符入的字符如果当前的字符是普通字符，如果当前的字符是普通字符，则压栈如果是，如果是，则删除除栈顶字符字符如果是如果是，则将将栈清空清空3、将从、将从栈底到底到栈顶的字符的字符传送至送至调用用过程的数据区程的数据区4、删除除栈3535例五、例五、表达式求值表达式求值 限于二元运算符的表达式定限于二元运算符的表达式定义:表达式表达式:=(操作数操作数)+(运算符运算符)+(操作数操作数)操作数操作数(operand):=简单变量量|表达式表达式简
19、单变量量:=标识符符|无符号整数无符号整数运算符运算符(operator)表达式的三种表达式的三种标识方法：方法：Exp=S1+OP+S2OP+S1+S2 为前前缀表示法表示法 S1+OP+S2 为中中缀表示法表示法S1+S2+OP 为后后缀表示法表示法 36361 12 23 34 4 5+6 (1+2)4topbaseOPTROPTR栈栈+1A+B 1 D 2 中缀表达式的求值中缀表达式的求值=5+6 3-4=5+18-4=23-4=19OPTDOPTD栈栈563737算符优先关系表 2 2 1 1 1 2+-*/()#+-*/()#+-*/()#=3838OPTR栈栈从左向右从左向右扫描
20、表达式：描表达式：5+6(1+2)4遇操作数遇操作数保存在操作数保存在操作数栈；遇运算符号遇运算符号 2与前面的运算符与前面的运算符 1比比较若若 1 2 则 1可可进行运算；行运算；若若 1=2 需要消去括号；需要消去括号；+(表达式求值基本操作基本操作561OPND栈栈23939toptopbaseOPTROPTR栈栈#OPNDOPND栈栈toptopbase5 5toptoptoptop+toptop6 6toptoptoptop(toptop1 1toptop+toptop2 2toptoptoptoptoptoptoptop3 3toptoptoptoptoptoptoptoptop
21、top1818toptoptoptoptoptoptoptop2323toptop-toptop4 4toptoptoptoptoptoptoptop1919toptoptoptop5 5 读入表达式：读入表达式：+6 6 (1 1+2 2)-4 4#=19=191+2=363=185+18=2323-4=19 表达式求值示意图（算符优先算法）表达式求值示意图（算符优先算法）OPTROPTR栈顶元素为栈顶元素为当前字符也为当前字符也为结束标志？结束标志？4040算符优先算法操作步骤算符优先算法操作步骤1.初始化运算符初始化运算符OPTR栈和操作数和操作数OPND栈2.将将#压入入OPTR栈3.
22、依次依次读入每个字符，直到表达式求入每个字符，直到表达式求值完完毕若是操作数，若是操作数，则压入入OPND栈若是运算符，若是运算符，则和和OPTR栈顶元素比元素比较优先先级4.返回运算返回运算结果果1.InitStack(OPTR);InitStack(OPND);2.Push(OPTR,#);3.while(c!=#|GetTop(OPTR)!=#)if(!In(c,OP)Push(OPND,c);else switch(Precede(GetTop(OPTR),c)4.return GetTop(OPND);4141switch(Precede(GetTop(OPTR),c)case:/退
23、退栈，并将运算，并将运算结果果压栈 Pop(OPTR,theta);/取出运算符取出运算符 Pop(OPND,b);Pop(OPND,a);/取出操作数取出操作数 Push(OPND,Operate(a,theta,b);/结果果压栈4242 算符优先算法OperandType EvaluateExpression()/算术表达式求值的算符优先算法。设算术表达式求值的算符优先算法。设OPTR和和OPND分别为运算符栈和操作数栈，分别为运算符栈和操作数栈，OP为运算符集合。为运算符集合。InitStack(OPTR);InitStack(OPND);/步骤步骤1 Push(OPTR,#);c=g
24、etchar();/步骤步骤2 while(c!=#|GetTop(OPTR)!=#)/步骤步骤3 if(!In(c,OP)/操作数进栈操作数进栈OPND Push(OPND,c);c=getchar()else 4343 switch(Precede(GetTop(OPTR),c)case:/退栈，并将运算结果压栈退栈，并将运算结果压栈 Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a);Push(OPND,Operate(a,theta,b);break;/switch /if /while return GetTop(OPND);/步骤步骤4 /Evaluat
25、eExpression4444例六、例六、实现递归实现递归(Hanoi Problem)递归函数函数执行的行的过程可程可视为同一函数同一函数进行嵌套行嵌套调用用xyz213xyz213Hanoi（3,x,y,z)xyz1xyz1Hanoi（1,x,y,z)move(x,1,z);Hanoi Problem4545void hanoi(int n,char x,char y,char z)if(n=1)move(x,1,z);else hanoi(n-1,x,z,y);move(x,n,z);hanoi(n-1,y,x,z);结束条件结束条件4646xyz21xyz21Hanoi Problem
26、xyz213将塔座将塔座x上按直径由小到大且至上而下编号为上按直径由小到大且至上而下编号为1至至n的的n个圆盘按规则搬到塔座个圆盘按规则搬到塔座z上，上，y可用作辅助塔座可用作辅助塔座xyz213Hanoi（2,x,y,z)Hanoi（3,x,y,z)4747xyz1Hanoi（1,x,y,z)xyz1move(x,1,z);if(n=1)move(x,1,z);4848xyz213xyz213xyz213xyz213Hanoi（3,x,y,z)Hanoi（2,x,y,z)Hanoi（2,x,z,y)move(x,3,z);Hanoi（2,y,z,x)hanoi(n-1,x,z,y);move
27、(x,n,z);hanoi(n-1,y,x,z);4949Hanoi（2,x,y,z)xyz12xyz12xyz12Hanoi（1,x,z,y)move(x,2,z);xyz12Hanoi（1,y,z,x)Hanoi（1,x,y,z)hanoi(n-1,x,z,y);move(x,n,z);hanoi(n-1,y,x,z);5050void hanoi(int n,char x,char y,char z)if(n=1)move(x,1,z);/将编号为的圆盘从将编号为的圆盘从x移到移到z else hanoi(n-1,x,z,y);/将将x上编号为至上编号为至n-1的的 /圆盘移到圆盘移到y
28、,z作辅助塔作辅助塔 move(x,n,z);/将编号为将编号为n的圆盘从的圆盘从x移到移到z hanoi(n-1,y,x,z);/将将y上编号为至上编号为至n-1的的 /圆盘移到圆盘移到z,x作辅助塔作辅助塔 51513.4 队列队列队列：列：一端插入，另一端一端插入，另一端删除除从尾从尾进，从，从头出出队列的特点：列的特点：先先进先出的先出的线性表性表FIFOfist in fist outa a1 1a an-1n-1a an n出队列出队列进队列进队列队首队首队尾队尾5252队列的类型定义队列的类型定义 ADT Queue 数据对象：数据对象：Dai|aiElemSet,i=1,2,.
29、,n,n0 数据关系：数据关系：R1|ai-1,ai D,i=2,.,n 约定其中约定其中a1 端为队列头，端为队列头，an 端为队列尾端为队列尾 基本操作：基本操作：ADT Queue5353队列的基本操作队列的基本操作InitQueue(&Q)操作操作结果：构造一个空果：构造一个空队列列QDestroyQueue(&Q)初始条件：初始条件：队列列Q已存在。已存在。操作操作结果：果：队列列Q被被销毁，不再存在。，不再存在。ClearQueue(&Q)初始条件：初始条件：队列列Q已存在。已存在。操作操作结果：将果：将Q清清为空空队列。列。5454队列的基本操作队列的基本操作QueueEmpty
30、(Q)初始条件：初始条件：队列列Q已存在。已存在。操作操作结果：若果：若Q为空空队列，列，则返回返回TRUE，否，否则返返回回FALSE。QueueLength(Q)初始条件：初始条件：队列列Q已存在。已存在。操作操作结果：返回果：返回Q的元素个数，即的元素个数，即队列的列的长度。度。5555队列的基本操作队列的基本操作GetHead(Q,&e)初始条件：初始条件：Q为非空非空队列。列。操作操作结果：用果：用e返回返回Q的的队头元素。元素。a a1 1a an-1n-1a an n队首队首队尾队尾读取读取a a1 1队首不变队首不变5656队列的基本操作队列的基本操作EnQueue(&Q,e)
31、初始条件：初始条件：队列列Q已存在。已存在。操作操作结果：插入元素果：插入元素e为Q的新的的新的队尾元素。尾元素。a a1 1a an n进队列进队列队首队首队尾队尾a a1 1a an ne队首队首队尾队尾5757队列的基本操作队列的基本操作DeQueue(&Q,&e)初始条件：初始条件：Q为非空非空队列。列。操作操作结果：果：删除除Q的的队头元素，并用元素，并用e返回其返回其值。a a1 1a an-1n-1a an n出队列出队列队首队首队尾队尾a a2 2a an-1n-1a an n队首队首队尾队尾a a2 258583.5 队列类型的实现队列类型的实现1）链队列列链式映象式映象2）
32、循）循环队列列顺序映象序映象5959链队列链队列链式映象frontrear空队列空队列a1a2anfrontrear6060 typedef struct QNode QElemType data;struct QNode *next;QNode,*QueuePtr;typedef struct QueuePtr front;/队头指针队头指针 QueuePtr rear;/队尾指针队尾指针 LinkQueue;链队列链队列链式映象结结点点类类型型链链队队列列类类型型6161 Status InitQueue(LinkQueue&Q)/构造一个空队列构造一个空队列Q Q.front=Q.rea
33、r=(QueuePtr)malloc(sizeof(QNode);if(!Q.front)exit(OVERFLOW);/存储分配失败存储分配失败 Q.front-next=NULL;return OK;6262 Status EnQueue(LinkQueue&Q,QElemType e)/插入元素插入元素e为为Q的新的队尾元素的新的队尾元素 p=(QueuePtr)malloc(sizeof(QNode);if(!p)exit(OVERFLOW);/存储分配失败存储分配失败 p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;return OK;6363
34、 Status DeQueue(LinkQueue&Q,QElemType&e)/若队列不空，则删除若队列不空，则删除Q的队头元素，的队头元素，/用用 e 返回其值，并返回返回其值，并返回OK；否则返回；否则返回ERROR if(Q.front=Q.rear)return ERROR;p=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear=p)Q.rear=Q.front;free(p);return OK;6464#define MAXQSIZE 100 /最大队列长度最大队列长度 typedef struct QElemType base
35、MAXQSIZE;int front;/头指针，若队列不空，头指针，若队列不空，/指向队列头元素指向队列头元素 int rear;/尾指针，若队列不空，指向尾指针，若队列不空，指向 /队列尾元素队列尾元素 的下一个位置的下一个位置 SqQueue;循环队列循环队列顺序映象6565 Status InitQueue(SqQueue&Q)/构造一个空队列构造一个空队列Q Q.front=Q.rear=0;return OK;6666J1,J2,J3入队列入队列Q.rearQ.front J1J1 J2J2 J3J3 J4,J5,J6入队入队Q.rearQ.front J6 J6 J5 J5 J4
36、J4J1,J2,J3出队出队Q.rearQ.front 空队列空队列Q.frontQ.rearQ.base6767入队操作前入队操作前0 03 3Q.baseQ.rearQ.front0 01 14 43 32 25 5J4J4J6J6J5J5入队操作后入队操作后Q.baseQ.rearQ.front1 13 30 01 14 43 32 25 5J7J7J4J4J6J6J5J5Q.rear=(Q.rear+1)%MAXQSIZE 循环使用队列空间6868出队操作前出队操作前J4J4出队操作后出队操作后Q.baseQ.rearQ.front1 13 30 01 14 43 32 25 5J7J
37、7J4J4J6J6J5J5Q.baseQ.rearQ.front1 14 40 01 14 43 32 25 5J7J7J6J6J5J5Q.front=(Q.front+1)%MAXQSIZE 6969 循环队列判空、判满的方法及条件Q 1 13 30 01 14 43 32 25 5J7J7J4J4J6J6J5J5Q 1 11 10 01 14 43 32 25 5Q 3 33 30 01 14 43 32 25 5J7J7J8J8J4J4J9J9J6J6J5J5Q.rear=Q.front7070改改进的方法：的方法：保存保存队长另另设标志志少用一个存少用一个存储单元元Q.baseQ.re
38、arQ.front3 34 40 01 14 43 32 25 5J9J9J6J6J5J5J8J8J7J7判满条件判满条件(Q.rear+1)%MAXQSIZE=Q.front判空条件判空条件 Q.rear=Q.frontQ 1 11 10 01 14 43 32 25 57171Status EnQueue(SqQueue&Q,ElemType e)/插入元素插入元素e为为Q的新的队尾元素的新的队尾元素 if(Q.rear+1)%MAXQSIZE=Q.front)return ERROR;/队列满队列满 Q.baseQ.rear=e;Q.rear=(Q.rear+1)%MAXQSIZE;re
39、turn OK;7272 Status DeQueue(SqQueue&Q,ElemType&e)/若队列不空，则删除若队列不空，则删除Q的队头元素，的队头元素，/用用e返回其值，并返回返回其值，并返回OK;否则返回否则返回ERROR if(Q.front=Q.rear)return ERROR;e=Q.baseQ.front;Q.front=(Q.front+1)%MAXQSIZE;return OK;7373问题问题在循在循环队列中列中为何不能用何不能用动态数数组？循循环队列必列必须要要设置最大置最大长度！度！74743.5 离散事件模拟离散事件模拟假假设某某银行有行有4个窗口个窗口对外接
40、待客外接待客户，从早晨，从早晨银行开行开门起不断有客起不断有客户进入入银行行每个窗口一次只能接待一个客每个窗口一次只能接待一个客户，人数众多，人数众多时需要需要在每个窗口前排在每个窗口前排队刚进入入银行的客行的客户，如果有窗口空，如果有窗口空闲则可上前可上前办理理若窗口均有客若窗口均有客户，他便排在人数最少的，他便排在人数最少的队伍后面伍后面编制一个程序模制一个程序模拟银行的行的这种种业务活活动，并，并计算一算一天中客天中客户在在银行逗留的平均行逗留的平均时间需要需要记录每个客每个客户的逗留的逗留时间和客和客户总数数需要模需要模拟客客户到达、排到达、排队、办事和离开的事和离开的过程程7575事
41、件事件(event)：客：客户到达到达银行和离开行和离开银行两个行两个时间发生的事情生的事情为事件。事件。事件表：有序表事件表：有序表基本信息：基本信息：发生生时间、事件、事件类型型基本操作：插入、基本操作：插入、删除除客客户排排队的的队列列4个个队列列基本信息：到达基本信息：到达时间、办理理时间基本操作：插入、基本操作：插入、删除除7676typedef struct /事件结构事件结构 int OccurTime;/事件发生时间事件发生时间 int NType;/事件类型。事件类型。0：到达事件；：到达事件；/1234：四个窗口的离开事件：四个窗口的离开事件 Event,Elemtype;
42、Typedef LinkList EventList/事件链表定义为有事件链表定义为有序链表序链表typedef struct/排队队列排队队列 int ArrivalTime;/到达时刻到达时刻 int Duration;/办理事务所需时间办理事务所需时间 QElemtype;链表链表链表链表7777程序设计模式程序设计模式事件事件驱动模式模式(event-driven)(event-driven)：按照：按照时间发生的先生的先后后顺序序进行模行模拟若有用若有用户到达，到达，则处理到达事理到达事CustomerArrivedCustomerArrived()()若有用若有用户离开，离开，则处
43、理离开事理离开事CustomerDepatureCustomerDepature()()/变量定义变量定义Event List ev;/事件表事件表Event en;/当前事件当前事件LinkQueue q5;/4个客户队列个客户队列QElemType customer;/客户记录客户记录int TotalTime;/累计逗留时间累计逗留时间int CustomerNum;/客户总人数客户总人数7878void Bank_Simulation(int ClostTime)OpenForDay();/初始化初始化 while(!ListEmpty(ev)/依次从事件表中取出事件依次从事件表中取出
44、事件 DelFirst(GetHead(ev),p);en=GetCurElem(p);if(en.Ntype=0)CustomerArrived();/处理达到事件处理达到事件 else CustomerDeparture();/处理离开事件处理离开事件 /while printf(“the average time is%fn”,(float)TotleTime/CustomerNum);/Bank_Simulation7979事件的产生方式事件的产生方式客客户到达事件的模到达事件的模拟：假假设第一个客第一个客户到达到达时间为0时刻刻之后每一个客之后每一个客户到达的到达的时刻在前一个客刻在
45、前一个客户到达的到达的时候候设定，即定，即产生两个随机数：生两个随机数：当前客当前客户办理的理的时间（durtime）下一客下一客户达到的达到的时间间隔（隔（intertime）客客户离开事件的模离开事件的模拟：情况情况1：在第一个客：在第一个客户到达的到达的时候候设定定情况情况2：当：当处理一个客理一个客户的离开事件的离开事件时，设置本置本该客客户所在所在队列的第一个客列的第一个客户的离开的离开时间。8080处理客户到达事件处理客户到达事件CustomerArrived()1.客客户数目加数目加12.随机随机产生生durtime、intertime3.将下一个客将下一个客户的到达事件插入事件
46、表，若在下班前到达的到达事件插入事件表，若在下班前到达4.将当前客将当前客户插入最短的插入最短的队列列i中中5.若若队列列i中只包有当前客中只包有当前客户，则将当前客将当前客户的离开事件插入的离开事件插入到事件表到事件表1.+CustomerNum;2.Random(durtime,intertime);3.t=en.OccurTime+intertime;if(t CloseTime)OrderInsert(ev,(t,0),cmp);4.i=Minimum(q);EnQueue(qi,(en.OccurTime,durtime);5.if(QueueLength(qi=1)OrderIns
47、ert(ev,(en.OccurTime+durtime,i),cmp);8181处理客户离开事件处理客户离开事件CustomerDepature()1.删除除队列列i的的队首客首客户2.累累计客客户逗留逗留时间：当前：当前时间客客户达到达到时间3.设定定队列列i当前当前队首客首客户的离开事件，插入事件表的离开事件，插入事件表1.i=en.NType;DlQueue(qi,customer);2.TotleTime+=en.OccurTime customer.ArrivalTime;3.if(!QueueEmpty(qi)GetHead(qi,customer);OrderInsert(ev
48、,(en.OccurTime+customer.Duration,i),cmp);8282void OpenForDay()TotalTime=0;CustomerNum=0;InitList(ev);/初始化事件表初始化事件表 en.Occurtime=0;en.Ntype=1;OrderInsert(ev,en,cmp);/插入第一个到达的客户的到插入第一个到达的客户的到达事件达事件 for(i=1;i data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;/插在队尾插在队尾 return OK;找到第一个小于等于找到第一个小于等于e的结点，插在它之前的结点，
49、插在它之前84843730frontrear13rqwhile(e r-data)q=r;r=r-next;p-next=r;q-next=p;12322prqif(!r)Q.rear=p;while(r)if(e data)break;q=r;r=r-next;8585 Status EnQueue(LinkQueue&Q,QElemType e)/插入元素插入元素e为为Q的新的队尾元素的新的队尾元素 p=(QueuePtr)malloc(sizeof(QNode);if(!p)exit(OVERFLOW);/存储分配失败存储分配失败 p-data=e;p-next=NULL;Q.rear-
50、next=p;Q.rear=p;return OK;q=Q.front;r=q-next;while(r)if(e data)break;q=r;r=r-next;p-next=r;q-next=p;if(!r)Q.rear=p;8686本章学习要点本章学习要点1.掌握掌握栈和和队列列类型的特点，并能在相型的特点，并能在相应的的应用用问题中正确中正确选用它用它们。2.熟熟练掌握掌握栈类型的两种型的两种实现方法，特方法，特别应注意注意栈满和和栈空的条件以及它空的条件以及它们的描述方法的描述方法3.熟熟练掌握循掌握循环队列和列和链队列的基本操作列的基本操作实现算法，算法，特特别注意注意队满和和队空