队列(queue)及其应用课件

队列（queue）及其应用

2007/04/061队列（queue）及其应用

2007/04/0后缀表达式的求值过程。使用一个存放算子（运算分量）的栈。求值过程顺序扫描后缀表达式，每次遇到算子便将它推入栈中；遇到运算符时，就从栈中弹出两个整数(算子)进行计算，而后再把结果推入栈中。到扫描结束时，留在栈顶的整数就是所求表达式的值。4123+35*/-2后缀表达式的求值过程。使用一个存放算子（运算分量）的栈。41关于带括号的表达式的计算-（+#341*6)/3#operatorstackoperandstackexpression???push(data);Push(oper);getResult();checkIn(oper);3关于带括号的表达式的计算-（+#341*6)/本讲主要内容：队列的引入与抽象数据类型定义队列的存储结构与实现队列的应用4本讲主要内容：队列的引入与抽象数据类型定义4队列的特点队列是一种特殊的线性表，只允许在表的一端有插入操作，而在另一端有删除操作。队头：允许删除的这一端叫队列的头。队尾：允许插入的这一端叫队列的尾。空队列：当队列中没有任何元素时，称为空队列。进队/出队：队列的插入操作通常称为进队列或入队列，队列的删除操作通常称为退队列或出队列。5队列的特点队列是一种特殊的线性表，只允许在表的一端有插入操作队列的基本概念：

队列也称作先进先出表（FirstInFirstOut，FIFO表）。支持队尾插入，队头删除操作。

a0a1a2an-1入队列队头队尾出队列队列的示意图6队列的基本概念：

队列也称作先进先出表（FirstIn队列ADTADTQueueisoperations QueuecreateEmptyQueue(void);//创建一个空队列。 intisEmptyQueue(Queuequ);//判队列qu是否为空队列。 voidenQueue(Queuequ,DataTypex); //往队列qu尾部插入一个值为x的元素。 voiddeQueue(Queuequ);//从队列qu头部删除一个元素。 DataTypefrontQueue(Queuequ);//求队列qu头部元素的值。endADTQueue7队列ADTADTQueueis7基于顺序存储结构的队列实现…a1a2a3a4…an…frontrearenQueue:{rear++;qBuffer[rear]=inData;}deQueue:{outData=qBuffer[rear];rear++;}8基于顺序存储结构的队列实现…a1a2a3a4…an…fron基于环形存储结构的队列实现a1a2a3a4…anfrontrearmodMAXSIZEenQueue:{rear=(rear+1)%MAXSIZEqBuffer[rear]=inData;}deQueue:{outData=qBuffer[rear];rear=(rear+1)%MAXSIZE;}9基于环形存储结构的队列实现a1a2a3a4…anfrontr基于环形存储结构的队列实现把数组paqu->q[MAXNUM]从逻辑上看成一个环，这种队列称为环形队列。当表中已有MAXNUM－1个结点时，如果还要插入，paqu->r和paqu->f就会重合，而这与空队列的情形相混。为区分空队列与满队列两种情况的环形队列，一般是牺牲队列中的一个结点，当队列中已有MAXNUM－1个结点时就称满，再要插入就发生溢出.10基于环形存储结构的队列实现把数组paqu->q[MAXNUMpaqu->rpaqu->f图(a)空队列a1a2a7a6a5a4a3paqu->fpaqu->r图(b)队列满，判断(paqu->r+1)==paqu->f图:环形队列11paqu->rpaqu->f图(a)空队列a1a2a7a6顺序结构队列的类型定义12顺序结构队列的类型定义12顺序结构队列的操作定义（ADT）13顺序结构队列的操作定义（ADT）13顺序结构队列操作的实现14顺序结构队列操作的实现14顺序结构队列操作的实现15顺序结构队列15顺序结构队列操作的实现

16顺序结构队列操作的实现

16链接结构队列的数据结构设计尾部插入头部删除。r->link=newNode;r=newNode;newNode.link=NULL;ptr=f;f=f->next;free(ptr);空链表？17链接结构队列的数据结构设计尾部插入链接结构队列操作的实现

18链接结构队列操作的实现

18队列的应用——缓冲区的管理用于匹配不同速率需求与服务用于格式转换a1a2a3a4…an…稳定的服务提供随机到来的服务请求19队列的应用——缓冲区的管理用于匹配不同速率需求与服务a1队列的应用

——理发店问题模拟仿真20队列的应用——理发店问题模拟仿真20队列的应用

——理发店问题模拟仿真C1C2C3…Cn…struct{intinTime;intservTime;intwaitTime;}C;=t+rand()%20;=minServeTime+R%(maxServeTime-minServeTime)chairsCustomerQueue21队列的应用——理发店问题模拟仿真C1C2C3…Cn…str2222队列的应用

——顾客流生成23队列的应用——顾客流生成23ActasaTimer24ActasaTimer242525从均匀分布到正态分布数学期望方差26从均匀分布到正态分布数学期望方差26应用：农夫过河（农夫狼白菜羊）（农夫狼白菜羊）1111000027应用：农夫过河（农夫狼白菜羊）（农夫（农狼菜羊）（农

狼菜羊）（农狼菜羊）（农狼菜羊）（农

狼菜羊）（农

狼菜羊）（农狼菜羊）（农狼菜羊）（农狼菜羊）（农狼菜羊）（农

狼菜羊）（农

狼菜羊）（农狼菜羊）（农狼菜羊）（农狼菜羊）28（农狼菜羊）（农狼菜羊）（农狼菜迷宫问题RatInAMaze迷宫问题RatInAMaze作业：实现带括号的正整数的四则运算表达式的求值。对错误格式的表达式进行判别并给出错误信息。提交：8号阅读有关理发店的模拟算法，修改并给出顾客平均等待时间。座位平均利用率。如果考虑照顾员工下班时间，凡在下班前不能完成的顾客就请他明天再来。则需要如何修改。提交：11号30作业：实现带括号的正整数的四则运算表达式的求值。30队列（queue）及其应用

2007/04/0631队列（queue）及其应用

2007/04/0后缀表达式的求值过程。使用一个存放算子（运算分量）的栈。求值过程顺序扫描后缀表达式，每次遇到算子便将它推入栈中；遇到运算符时，就从栈中弹出两个整数(算子)进行计算，而后再把结果推入栈中。到扫描结束时，留在栈顶的整数就是所求表达式的值。4123+35*/-32后缀表达式的求值过程。使用一个存放算子（运算分量）的栈。41关于带括号的表达式的计算-（+#341*6)/3#operatorstackoperandstackexpression???push(data);Push(oper);getResult();checkIn(oper);33关于带括号的表达式的计算-（+#341*6)/本讲主要内容：队列的引入与抽象数据类型定义队列的存储结构与实现队列的应用34本讲主要内容：队列的引入与抽象数据类型定义4队列的特点队列是一种特殊的线性表，只允许在表的一端有插入操作，而在另一端有删除操作。队头：允许删除的这一端叫队列的头。队尾：允许插入的这一端叫队列的尾。空队列：当队列中没有任何元素时，称为空队列。进队/出队：队列的插入操作通常称为进队列或入队列，队列的删除操作通常称为退队列或出队列。35队列的特点队列是一种特殊的线性表，只允许在表的一端有插入操作队列的基本概念：

队列也称作先进先出表（FirstInFirstOut，FIFO表）。支持队尾插入，队头删除操作。

a0a1a2an-1入队列队头队尾出队列队列的示意图36队列的基本概念：

队列也称作先进先出表（FirstIn队列ADTADTQueueisoperations QueuecreateEmptyQueue(void);//创建一个空队列。 intisEmptyQueue(Queuequ);//判队列qu是否为空队列。 voidenQueue(Queuequ,DataTypex); //往队列qu尾部插入一个值为x的元素。 voiddeQueue(Queuequ);//从队列qu头部删除一个元素。 DataTypefrontQueue(Queuequ);//求队列qu头部元素的值。endADTQueue37队列ADTADTQueueis7基于顺序存储结构的队列实现…a1a2a3a4…an…frontrearenQueue:{rear++;qBuffer[rear]=inData;}deQueue:{outData=qBuffer[rear];rear++;}38基于顺序存储结构的队列实现…a1a2a3a4…an…fron基于环形存储结构的队列实现a1a2a3a4…anfrontrearmodMAXSIZEenQueue:{rear=(rear+1)%MAXSIZEqBuffer[rear]=inData;}deQueue:{outData=qBuffer[rear];rear=(rear+1)%MAXSIZE;}39基于环形存储结构的队列实现a1a2a3a4…anfrontr基于环形存储结构的队列实现把数组paqu->q[MAXNUM]从逻辑上看成一个环，这种队列称为环形队列。当表中已有MAXNUM－1个结点时，如果还要插入，paqu->r和paqu->f就会重合，而这与空队列的情形相混。为区分空队列与满队列两种情况的环形队列，一般是牺牲队列中的一个结点，当队列中已有MAXNUM－1个结点时就称满，再要插入就发生溢出.40基于环形存储结构的队列实现把数组paqu->q[MAXNUMpaqu->rpaqu->f图(a)空队列a1a2a7a6a5a4a3paqu->fpaqu->r图(b)队列满，判断(paqu->r+1)==paqu->f图:环形队列41paqu->rpaqu->f图(a)空队列a1a2a7a6顺序结构队列的类型定义42顺序结构队列的类型定义12顺序结构队列的操作定义（ADT）43顺序结构队列的操作定义（ADT）13顺序结构队列操作的实现44顺序结构队列操作的实现14顺序结构队列操作的实现45顺序结构队列15顺序结构队列操作的实现

46顺序结构队列操作的实现

16链接结构队列的数据结构设计尾部插入头部删除。r->link=newNode;r=newNode;newNode.link=NULL;ptr=f;f=f->next;free(ptr);空链表？47链接结构队列的数据结构设计尾部插入链接结构队列操作的实现

48链接结构队列操作的实现

18队列的应用——缓冲区的管理用于匹配不同速率需求与服务用于格式转换a1a2a3a4…an…稳定的服务提供随机到来的服务请求49队列的应用——缓冲区的管理用于匹配不同速率需求与服务a1队列的应用

——理发店问题模拟仿真50队列的应用——理发店问题模拟仿真20队列的应用

——理发店问题模拟仿真C1C2C3…Cn…struct{intinTime;intservTime;intwaitTime;}C;=t+rand()%20;=minServeTime+R%(maxServeTime-minServeTime)chairsCustomerQueue51队列的应用——理发店问题模拟仿真C1C2C3…Cn…str5222队列的应用

——顾客流生成53队列的应用——顾客流生成23ActasaTimer54