《数据结构课程chap03栈和队列.ppt》由会员分享，可在线阅读，更多相关《数据结构课程chap03栈和队列.ppt（117页珍藏版）》请在三一办公上搜索。
1、第三章栈和队列,第3章 栈和队列,通常称，栈和队列是限定插入和删除只能在表的“端点”进行的线性表。,线性表 栈 队列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 栈的类型定义,3.1 栈的类型定义,ADT Stack 数据对象：D ai|ai ElemSet,i=1,2,.,n,n0 数据关系：R1|ai-1,aiD,i
2、=2,.,n 约定an 端为栈顶，a1 端为栈底。,基本操作：,ADT Stack,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 被销毁。,StackEmpty(S)初始条件：栈 S 已存在。操作结果：若栈 S 为空栈，则返回 TRUE，否则 FAL
3、E。,StackLength(S)初始条件：栈 S 已存在。操作结果：返回 S 的元素个数，即栈的长度。,GetTop(S,&e)初始条件：栈 S 已存在且非空。操作结果：用 e 返回 S 的栈顶元素。,a1,a2,an,ClearStack(&S)初始条件：栈 S 已存在。操作结果：将 S 清为空栈。,Push(&S,e)初始条件：栈 S 已存在。操作结果：插入元素 e 为新的栈顶元素。,a1,a2,an,e,Pop(&S,&e)初始条件：栈 S 已存在且非空。操作结果：删除 S 的栈顶元素，并用 e 返回其值。,a1,a2,an,an-1,3.2 栈的应用举例,例一、数制转换,例二、括号匹
4、配的检验,例三、行编辑程序问题,例四、迷宫求解,例五、表达式求值,例六、实现递归,例一、数制转换 算法基于原理：N=(N div d)d+N mod d,例如：（1348)10=(2504)8，其运算过程如下：,void conversion()InitStack(S);scanf(%d,N);while(N)Push(S,N%8);N=N/8;while(!StackEmpty(S)Pop(S,e);printf(%d,e);/conversion,例二、括号匹配的检验假设在表达式中（）或（）等为正确的格式，（）或（）或（）)均为不正确的格式。,则 检验括号是否匹配的方法可用“期待的急迫程度
5、”这个概念来描述。,分析可能出现的不匹配的情况:,到来的右括弧并非是所“期待”的；,例如：考虑下列括号序列：()1 2 3 4 5 6 7 8,到来的是“不速之客”；,直到结束，也没有到来所“期待”的括弧。,算法的设计思想：,1）凡出现左括弧，则进栈；,2）凡出现右括弧，首先检查栈是否空 若栈空，则表明该“右括弧”多余，否则和栈顶元素比较，若相匹配，则“左括弧出栈”，否则表明不匹配。,3）表达式检验结束时，若栈空，则表明表达式中匹配正确，否则表明“左括弧”有余。,Status matching(string.,例三、行编辑程序问题,如何实现？,“每接受一个字符即存入存储器”?,并不恰当！,设立
6、一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区，并假设“#”为退格符，“”为退行符。,在用户输入一行的过程中，允许 用户输入出差错，并在发现有误时 可以及时更正。,合理的作法是：,假设从终端接受了这样两行字符：whli#ilr#e（s#*s)outchaputchar(*s=#+);,则实际有效的是下列两行：while(*s)putchar(*s+);,while(ch!=EOF/从终端接收下一个字符,ClearStack(S);/重置S为空栈if(ch!=EOF)ch=getchar();,while(ch!=EOF)/EOF为全文结束符,将从栈底到栈顶的字符传送至调用过
7、程的数据区；,例四、迷宫求解,通常用的是“穷举求解”的方法,求迷宫路径算法的基本思想是：,若当前位置“可通”，则纳入路径，继续前进;,若当前位置“不可通”，则后退，换方向继续探索;,若四周“均无通路”，则将当前位置从路径中删除出去。,设定当前位置的初值为入口位置；do 若当前位置可通，则将当前位置插入栈顶；若该位置是出口位置，则算法结束；否则切换当前位置的东邻方块为 新的当前位置；否则 while(栈不空）；,求迷宫中一条从入口到出口的路径的算法：,若栈不空且栈顶位置尚有其他方向未被探索，则设定新的当前位置为:沿顺时针方向旋转 找到的栈顶位置的下一相邻块；,若栈不空但栈顶位置的四周均不可通，则
8、删去栈顶位置；/从路径中删去该通道块 若栈不空，则重新测试新的栈顶位置，直至找到一个可通的相邻块或出栈至栈空；,若栈空，则表明迷宫没有通路。,限于二元运算符的表达式定义:表达式:=(操作数)+(运算符)+(操作数)操作数:=简单变量|表达式 简单变量:=标识符|无符号整数,例五、表达式求值,表达式的三种标识方法：,设 Exp=S1+OP+S2,则称 OP+S1+S2 为前缀表示法,S1+OP+S2 为中缀表示法,S1+S2+OP 为后缀表示法,例如:Exp=a b+(c d/e)f前缀式:+a b c/d e f中缀式:a b+c d/e f后缀式:a b c d e/f+,结论:,1）操作数
9、之间的相对次序不变;,2）运算符的相对次序不同;,3）中缀式丢失了括弧信息，致使运算的次序不确定;,4)前缀式的运算规则为:连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式;,5)后缀式的运算规则为:运算符在式中出现的顺序恰为 表达式的运算顺序;每个运算符和在它之前出现 且 紧靠它的两个操作数构成一个最小 表达式。,如何从后缀式求值？,先找运算符，再找操作数,例如：a b c d e/f+,ab,d/e,c-d/e,(c-d/e)f,如何从原表达式求得后缀式？,每个运算符的运算次序要由它之后的一个运算符来定，在后缀式中，优先数高的运算符领先于优先数低的运算符。,分析“原表达
10、式”和“后缀式”中的运算符:原表达式:a+b c d/e f 后缀式:a b c+d e/f,逆波兰表达式,从原表达式求得后缀式的规律为：,1)设立操作符栈；,2)设表达式的结束符为“#”，予设运算符栈的栈底为“#”；,3)若当前字符是操作数，则直接发送给后缀式。,4)若当前运算符的优先数高于栈顶运算符，则进栈；,5)否则，退出栈顶运算符发送给后缀式；,6)“(”对它之前后的运算符起隔离作用，“)”可视为自相应左括弧开始的表达式的结束符。,从原表达式求得后缀式的规律为：,void transform(char suffix,char exp)InitStack(S);Push(S,#);p=e
11、xp;ch=*p;while(!StackEmpty(S)if(!IN(ch,OP)Pass(Suffix,ch);else if(ch!=#)p+;ch=*p;else Pop(S,ch);Pass(Suffix,ch);/while/CrtExptree,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)/switch,例六、实现递归,将所有的实在参数、返回地址等信息传递给被调用函数保存；为被调用函数的局部变量分配存储
12、区；将控制转移到被调用函数的入口。,当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三项任务：,保存被调函数的计算结果；释放被调函数的数据区；依照被调函数保存的返回地址将控制转移到调用函数。,从被调用函数返回调用函数之前，应该完成下列三项任务：,多个函数嵌套调用的规则是：,此时的内存管理实行“栈式管理”,后调用先返回！,例如：void main()void a()void b()a();b();/main/a/b,Main的数据区,函数a的数据区,函数b的数据区,递归工作栈：递归过程执行过程中占用的 数据区。递归工作记录：每一层的递归参数合成 一个记录。当前活动记录：栈
13、顶记录指示当前层的 执行情况。当前环境指针：递归工作栈的栈顶指针。,递归函数执行的过程可视为同一函数进行嵌套调用，例如：,递归算法的一般形式：void p(参数表)if（递归结束条件）可直接求解步骤；-基本项 else p（较小的参数）；-归纳项,递归：函数直接或间接的调用自身叫一个对象部分地包含它自己，或是用它自己给自己定义一个过程直接地或间接地调用自己利用前面运算来求得答案的过程实现：建立递归工作栈优点：递归函数结构清晰，程序易读，正确性易证明缺点：速度慢，空间大，效率低 通过栈来实现递归，通过栈来消除递归,递归过程及其实现,Factorial(4);,对于一个较为复杂的问题，如果能够分解
14、成几个相对简单的且解法相同或类似的子问题来求解分治法,例:递归的执行情况分析,void print(int w)int i;if(w!=0)print(w-1);for(i=1;i=w;i+)printf(“%d,”,w);printf(“n”);,运行结果：1，2，2，3，3，3，,递归调用执行情况如下：,Tower of Hanoi问题问题描述：有A,B,C三个塔座，A上套有n个直径不同的圆盘，按直径从小到大叠放，形如宝塔,编号1,2,3n。要求将n个圆盘从A移到C，叠放顺序不变，移动过程中遵循下列原则：每次只能移一个圆盘圆盘可在三个塔座上任意移动任何时刻，每个塔座上不能将大盘压到小盘上,
15、解决方法：n=1时，直接把圆盘从A移到Cn1时，先把上面n-1个圆盘从A移到B,然后将n号盘从A移到C,再将n-1个盘从B移到C。即把求解n个圆盘的Hanoi问题转化为求解n-1个圆盘的Hanoi问题，依次类推，直至转化成只有一个圆盘的Hanoi问题,执行情况：递归工作栈保存内容：形参n,x,y,z和返回地址返回地址用行编号表示,void hanoi(int n,char x,char y,char z)/将塔座x上按直径由小到大且至上而下编号为1至n/的n个圆盘按规则搬到塔座z上，y可用作辅助塔座。1 if(n=1)2 move(x,1,z);/将编号为的圆盘从x移到z3 else 4 ha
16、noi(n-1,x,z,y);/将x上编号为至n-1的/圆盘移到y,z作辅助塔5 move(x,n,z);/将编号为n的圆盘从x移到z6 hanoi(n-1,y,x,z);/将y上编号为至n-1的/圆盘移到z,x作辅助塔7 8,Tower of Hanoi,8 3 a b c,返址 n x y z,5 2 a c b,5 1 a b c,7 1 c a b,void hanoi(int n,char x,char y,char z)1 if(n=1)2 move(x,1,z);3 else 4 hanoi(n-1,x,z,y);5 move(x,n,z);6 hanoi(n-1,y,x,z);
17、7 8,3.3栈类型的实现,顺序栈,链栈,/-栈的顺序存储表示-#define STACK_INIT_SIZE 100;#define STACKINCREMENT 10;typedef struct SElemType*base;SElemType*top;int stacksize;SqStack;,类似于线性表的顺序映象实现，指向表尾的指针可以作为栈顶指针。,Status InitStack(SqStack,Status Push(SqStack,Status Pop(SqStack,栈顶指针,链栈,a1,an,注意:链栈中指针的方向,an-1,ADT Queue 数据对象：Dai|ai
18、ElemSet,i=1,2,.,n,n0 数据关系：R1|ai-1,ai D,i=2,.,n 约定其中a1 端为队列头，an 端为队列尾,基本操作：,3.4 队列的类型定义,ADT Queue,队列的基本操作：,InitQueue(&Q),DestroyQueue(&Q),QueueEmpty(Q),QueueLength(Q),GetHead(Q,&e),ClearQueue(&Q),DeQueue(&Q,&e),EnQueue(&Q,e),QueueTravers(Q,visit(),InitQueue(&Q)操作结果：构造一个空队列Q。DestroyQueue(&Q)初始条件：队列Q已存
19、在。操作结果：队列Q被销毁，不再存在。,QueueEmpty(Q)初始条件：队列Q已存在。操作结果：若Q为空队列，则返回TRUE，否则返回FALSE。,QueueLength(Q)初始条件：队列Q已存在。操作结果：返回Q的元素个数，即队列的长度。,GetHead(Q,&e)初始条件：Q为非空队列。操作结果：用e返回Q的队头元素。,a1,a2,an,ClearQueue(&Q)初始条件：队列Q已存在。操作结果：将Q清为空队列。,EnQueue(&Q,e)初始条件：队列Q已存在。操作结果：插入元素e为Q的新的队尾元素。,a1,a2,an,e,DeQueue(&Q,&e)初始条件：Q为非空队列。操作
20、结果：删除Q的队头元素，并用e返回其值。,a1,a2,an,3.5 队列类型的实现,链队列链式映象,循环队列顺序映象,typedef struct QNode/结点类型 QElemType data;struct QNode*next;QNode,*QueuePtr;,链队列链式映象,typedef struct/链队列类型 QueuePtr front;/队头指针 QueuePtr rear;/队尾指针 LinkQueue;,a1,an,Q.frontQ.rear,Q.frontQ.rear,空队列,Status InitQueue(LinkQueue,Status EnQueue(Link
21、Queue,Status DeQueue(LinkQueue,#define MAXQSIZE 100/最大队列长度 typedef struct QElemType*base;/动态分配存储空间 int front;/头指针，若队列不空，/指向队列头元素 int rear;/尾指针，若队列不空，指向/队列尾元素 的下一个位置 SqQueue;,循环队列顺序映象,Status InitQueue(SqQueue,Status EnQueue(SqQueue,Status DeQueue(SqQueue,第 1 行 1 1第 2 行 1 2 1 第 3 行 1 3 3 1第 4 行 1 4 6
22、4 1,二项式系数值（杨辉三角）,设第 i-1行的值：(a0=0)a1.ai(ai+1=0)则第 i 行的值：bj=aj-1+aj,j=1,2,i+1,0,0,利用“循环队列”计算二项式系数的过程,0,1,1,输出:,1,1,1,1,2,2,1,1,0,1,1,0,0,1,1,1,1,1,2,3,2,2,3,1,1,3,3,1,0,1,1,0,do DeQueue(Q,s);GetHead(Q,e);if(e!=0)cout e;EnQueue(Q,s+e);while(e!=0);,void yanghui(int n)/打印输出杨辉三角的前 n(n 0)行 Queue Q;InitQueu
23、e(Q,n+2);EnQueue(Q,0);/添加行界值 EnQueue(Q,1);EnQueue_Sq(Q,1);k=1;while(k n)EnQueue(Q,0);/行界值“0”入队列 do/输出第 k 行，计算第 k+1 行 while(e!=0);k+;/while/yanghui,DeQueue(Q,e);/行界值“0”出队列while(!QueueEmpty(Q)/单独处理第 n 行的值的输出 DeQueue_Sq(Q,e);coute；/while,1.掌握栈和队列类型的特点，并能在相应的应用问题中正确选用它们。,2.熟练掌握栈类型的两种实现方法，特别应注意栈满和栈空的条件以及
24、它们的描述方法。,3.熟练掌握循环队列和链队列的基本操作实现算法，特别注意队满和队空的描述方法。,4.理解递归算法执行过程中栈的状态变化过程。,本章学习要点,练习,队列通常采用两种存储结构是()。A顺序存储结构和链表存储结构 B散列方式和索引方式 C链表存储结构和数组 D线性存储结构和非线性存储结构若让元素1，2，3依次进栈，则出栈次序不可能出现（）种情况。A3，2，1 B2，1，3 C3，1，2 D1，3，2,栈和队列都是（）。A链式存储的线性结构 B顺序存储的线性结构 C限制存取位置的线性结构 D限制存取位置的非线性结构对于给定的结点序列abcdef，规定进栈只能从序列的左端开始。通过栈的
25、操作，能得到的序列为（）。Aabcfed Bcabfed Cabcfde Dcbafde,练习,栈的插入与删除操作在（）进行。A栈顶 B栈底 C任意位置D指定位置设一个栈的输入序列为A、B、C、D，则借助一个栈所能得到的输出序列不可能是（）。AABCD BDCBA CACDB DDABC,练习,一个队列的入队序列是a、b、c、d，则队列的输出序列为_。栈结构通常采用的两种存储结构是_和_。中缀算术表达式5+6/(23-(6+15)*8所对应的后缀算术表达式为_。中缀表达式3+x*(2.4/5-6)所对应的后缀表达式为_。,练习,用单链表表示的链式队列的队头在链表的（）位置。A）链头B）链尾C）
26、链中D）任意若用单链表来表示队列，则应该选用（）。A）带尾指针的非循环链表B）带尾指针的循环链表C）带头指针的非循环链表D）带头指针的循环链表,练习,考研题,若已知一个栈的入栈序列是1,2,3,n，其输出序列为p1,p2,p3,pN,若pN是n,则pi是()。A.i B.n-i C.n-i+1 D.不确定【南京理工大学 2001 一、1（1.5分）】执行完下列语句段后，i值为（）int f(int x)return(x0)?x*f(x-1):2);int i;i=f(f(1);A2 B.4 C.8 D.无限递归【浙江大学 2000 一、6(3分)】试推导出当总盘数为n的Hanoi塔的移动次数。
27、【北京邮电大学 2001 四、3（5分）】,答案,设Hn为n个盘子的Hanoi塔的移动次数。(假定n个盘子从钢针X移到钢针Z，可借助钢针Y)，则 Hn=2Hn-1+1/先将n-1个盘子从X移到Y，第n个盘子移到Z，再将那n-1个移到Z=2（2Hn-2+1）+1=22 Hn-2+2+1=22（2Hn-3+1）+2+1=23 Hn-3+22+2+1=2k Hn-k+2k-1+2k-2+21+20=2n-1 H1+2n-2+2n-3+21+20 因为H1=1，所以原式Hn=2n-1+2n-2+21+20=2n-1，故总盘数为n的Hanoi塔的移动次数是2n-1。,铁路进行列车调度时,常把站台设计成栈
28、式结构的站台，如下图所示。试问：,(1)设有编号为1,2,3,4,5,6的六辆列车,顺序开入栈式结构的站台,则可能的出栈序列有多少种?(2)若进站的六辆列车顺序如上所述,那么4第一个出站，5第二个出站，那么出栈序列有哪些？,应用案例题,作业三：数个数,请问，从1到100中存在着多少个9？请编程实现解决如下问题：接受用户输入一个整数n（0n264）和正整数m（1m9），请输出从0到n的所有整数中存在着多少个m？例如从0到24356中，存在多少个4？Tips：用堆栈实现。,机场模拟,计算机模拟（simulation）：用软件模仿另一个系统的行为。将研究对象表示为数据结构，对象动作表示为对数据的操作
29、，控制动作的规则转换为算法。通过更改数据的值或改变算法设置，可以观察到计算机模拟的变化，从而使用户能够推导出关于实际系统行为的有用结论。在计算机处理一个对象的动作期间，其它对象和动作需等待。队列在计算机模拟中具有重要应用。,简单机场模拟：只有一个跑道。在每个时间单元，可起飞或降落一架飞机，但不可同时起降。飞机准备降落或起飞的时间是随机的，在任一时间单元，跑道可能处于空闲、降落或起飞状态，并且可能有一些飞机在等待降落或起飞。飞机在地上等待的代价比在空中等待的小，只有在没有飞机等待降落的情况下才允许飞机起飞。当出现队列满的情况时，则拒绝为新到达的飞机服务。,需要两个队列landing和takeof
30、f。飞机可描述为：struct plane int id;/编号 int tm;/到达队列时间;飞机的动作为：enum action ARRIVE,DEPART;,模拟运行:时间单元:1 endtime，并产生关于机场行为的重要统计信息，如处理的飞机数量，平均等待时间，被拒绝服务飞机的数量等。采用基于泊松分布的随机整数决定在每个时间单元有多少架新飞机需要降落或起飞。假设在10个时间单元中到达的飞机数分别是：2，0，0，1，4，1，0，0，0，1，那么每个时间单元的平均到达数是0.9。,一个非负整数序列满足给定期望值v的泊松分布意味着，对于该序列的一段足够长的子序列，其中整数的平均值接近v 在模
31、拟中还需要建立新到达飞机的数据，处理被拒绝服务的飞机，起飞、降落飞机，处理机场空闲和总结模拟结果 下面是机场模拟类定义：,class AirportSimulation/机场模拟。一个时间单元=起飞或降落的时间public:AirportSimulation();/构造函数 void RunSimulation();/模拟运行private:Queue landing(6);/等待降落飞机队列，假设用环/型队列，实际长度为5 Queue takeoff(6);/等待起飞飞机队列，同上 double expectarrive;/一个时间单元内期望到达降落飞机数 double expectdepa
32、rt;/一个时间单元内期望到达起飞飞机数 int curtime;/当前时间 int endtime;/模拟时间单元数 int idletime;/跑道空闲时间单元数 int landwait;/降落飞机的总等待时间,int nland;/降落的飞机数 int nplanes;/处理的飞机数 int nrefuse;/拒绝服务的飞机数 int ntakeoff;/起飞的飞机数 void Randomize();/设置随机数种子 int PoissionRandom(double,构造函数初始化各变量，如下所示：AirportSimulation:AirportSimulation()/构造函数
33、 Boolean ok;cout endtime;idletime=landwait=nland=nplanes=0;nrefuse=ntakeoff=takoffwait=0;/初值 Randomize();/设置随机数种子 do cout expectarrive;cout expectdepart;,if(expectarrive 1.0)cout“机场将饱和！请重新输入。”endl;ok=FALSE;else ok=TRUE;while(ok=FALSE);,RunSimulation()是模拟运行的主控程序：void AirportSimulation:RunSimulation()
34、int pri;/伪随机整数 plane p;for(curtime=1;curtime=endtime;curtime+)cout“时间单元”curtime“：”;pri=PoissionRandom(expectarrive);for(int i=1;i=pri;i+)/处理新到达准备降落的飞机 p=*NewPlane(p,ARRIVE);if(landing.IsFull()Refuse(p,ARRIVE);else landing.Add(p);pri=PoissionRandom(expectdepart);,for(int i=1;i=pri;i+)/处理新到达准备起飞的飞机 p=
35、*NewPlane(p,DEPART);if(takeoff.IsFull()Refuse(p,DEPART);else takeoff.Add(p);if(!landing.IsEmpty()/降落飞机 p=*landing.Delete(p);Land(p);else if(!takeoff.IsEmpty()/起飞飞机 p=*takeoff.Delete(p);Fly(p);else Idle();/处理空闲时间单元 Conclude();/总结模拟结果,用库函数srand和rand生成随机数，并用时钟设置随机种子，以增强随机性：void AirportSimulation:Random
36、ize()srand(unsigned int)(time(NULL)%10000);库函数time返回自格林威治时间1970年1月1日00:00:00 至今经历的秒数。这使得每次模拟运行随机数起点都不同。rand按照均匀分布生成随机数，还需要转化为适合机场模拟的泊松分布随机数。下面直接给出根据泊松分布和给定期望值生成伪随机整数的算法（其数学推导略）：,int AirportSimulation:PoissionRandom(double,建立新飞机的数据项由函数NewPlane实现：plane*AirportSimulation:NewPlane(plane,处理被拒绝的飞机由函数Refus
37、e实现:void AirportSimulation:Refuse(plane/被拒绝飞机总数加1,处理飞机降落由函数Land实现：void AirportSimulation:Land(plane/累加总降落等待时间,处理飞机起飞由函数Fly实现：void AirportSimulation:Fly(plane/累加总起飞等待时间,处理机场空闲由函数Idle实现：void AirportSimulation:Idle()cout“跑道空闲。”endl;idletime+;/跑道空闲时间加1 总结模拟结果由函数Conclude实现：void AirportSimulation:Conclude
38、()cout“总模拟时间单元数：”endtime endl;cout“总共处理的飞机数：”nplanes endl;cout“降落飞机总数：”nland endl;cout“起飞飞机总数：”ntakeoff endl;,cout 0)cout 0)cout 0)cout“起飞平均等待时间：”(double)takeoffwait/ntakeoff endl;,可通过下列程序模拟运行：#include“common.h”#include“simdefs.h”/存放模拟类定义及相关函数实现void main()AirportSimulation s;s.RunSimulation();,模拟过程产
39、生的数据如下：请输入模拟时间单元数：30请输入一个时间单元内期望到达降落飞机数：0.47请输入一个时间单元内期望到达起飞飞机数：0.47时间单元1：飞机1准备降落。飞机1降落，该机等待时间：0。时间单元2：跑道空闲。时间单元3：飞机2准备降落。飞机3准备降落。飞机2降落，该机等待时间：0。时间单元4：飞机3降落，该机等待时间：1。,时间单元5：飞机4准备降落。飞机5准备降落。飞机6准备起飞。飞机7准备起飞。飞机4降落，该机等待时间：0。时间单元6：飞机8准备起飞。飞机5降落，该机等待时间：1。时间单元7：飞机9准备起飞。飞机10准备起飞。飞机6起飞，该机等待时间：2。时间单元8：飞机7起飞，该
40、机等待时间：3。时间单元9：飞机8起飞，该机等待时间：3。,时间单元10：飞机11准备降落。飞机11降落，该机等待时间：0。时间单元11：飞机12准备起飞。飞机9起飞，该机等待时间：4。时间单元12：飞机13准备降落。飞机14准备降落。飞机13降落，该机等待时间：0。时间单元13：飞机14降落，该机等待时间：1。时间单元14：飞机10起飞，该机等待时间：7。时间单元15：飞机15准备降落。飞机16准备起飞。飞机17准备起飞。飞机15降落，该机等待时间：0。,时间单元16：飞机18准备降落。飞机19准备降落。飞机20准备起飞。飞机21准备起飞。飞机18降落，该机等待时间：0。时间单元17：飞机2
41、2准备降落。飞机19降落，该机等待时间：1。时间单元18：飞机23准备起飞。告诉飞机23等一会儿再试。飞机22降落，该机等待时间：1。,时间单元19：飞机24准备降落。飞机25准备降落。飞机26准备降落。飞机27准备起飞。告诉飞机27等一会儿再试。飞机24降落，该机等待时间：0。时间单元20：飞机28准备降落。飞机29准备降落。飞机30准备降落。飞机31准备降落。引导飞机31到其它机场降落。飞机25降落，该机等待时间：1。,时间单元21：飞机32准备降落。飞机33准备起飞。告诉飞机33等一会儿再试。飞机26降落，该机等待时间：2。时间单元22：飞机28降落，该机等待时间：2。时间单元23：飞机
42、29降落，该机等待时间：3。时间单元24：飞机34准备起飞。告诉飞机34等一会儿再试。飞机30降落，该机等待时间：4。,时间单元25：飞机35准备起飞。告诉飞机35等一会儿再试。飞机36准备起飞。告诉飞机36等一会儿再试。飞机32降落，该机等待时间：4。时间单元26：飞机37准备起飞。告诉飞机37等一会儿再试。飞机12起飞，该机等待时间：15。时间单元27：飞机16起飞，该机等待时间：12。时间单元28：飞机17起飞，该机等待时间：13。时间单元29：飞机20起飞，该机等待时间：13。,时间单元30：飞机38准备起飞。飞机21起飞，该机等待时间：14。总模拟时间单元数：30总共处理的飞机数：38降落飞机总数：19起飞飞机总数：10拒绝服务的飞机总数：8队列中剩余的准备降落飞机数：0 队列中剩余的准备起飞飞机数：1跑道空闲时间百分比：3.33降落平均等待时间：1.11起飞平均等待时间：8.60,
