《队列的应用》由会员分享，可在线阅读，更多相关《队列的应用（7页珍藏版）》请在金锄头文库上搜索。
1、队列的应用：单服务台排队系统的模拟一、三个模拟1. 离散事件模拟系统在排队系统中，主要有两类事件：顾客的到达事件和服务完毕后顾客的离去事件，整个系统 就是不断有到达事件和离开事件的发生，这些事件并不是连续发生的，因此这样的系统被称为离 散事件模拟系统。(1) 事件处理过程当生成一个到达事件时，表示有一个新顾客到达。如果服务员没空，就去队列中排队；否则就为这个顾客生成服务所需的时间t,表示服务员 开始为它服务，所需的服务时间是t。经过这段时间后会产生一个顾客I离开事件,每当一个离开事件发生，就检查有没有顾客在排 队，如果有顾客在排队，则让队头顾客离队，为它提供服务，如果没有顾客排队，则服务员可以
2、 休息。(2) 如何产生顾客到达事件和离开事件在一个排队系统中，顾客的到达时间和为每个顾客服务的时间并不一定是固定的。但从统计 上来看是服从一定的概率分布。假设到达的间隔时间和服务时间都满足均匀分布，则可以用随机 数产生器产生的随机数。以生成顾客到达事件为例子如顾客到达的间隔时间服从a,b之间的均匀分布，则可以生成一个a,b之间的随机数x, 表示前一个顾客到达后，经过了 x的时间后又有一个顾客到达。a,b 之间的随机数可以按照下面的过程产生：假如系统的随机数生成器生成的随机数是均 匀分布在0到RAND_MAX之间，可以把0到RAND_MAX之间的区间等分成b-a+1个，当生成的随机 数落在第一
3、个区间，则表示生成的是a，当落在第二个区间，则表示生成的是a+1当落在最后 一个区间，则表示生成的是b。这个转换可以用rand()*(b-a+l)/( RAND_MAX+l)+a实现，rand 表示系统的随机数生成函数。2. 离散的时间驱动模拟在得到了在x秒后有一个事件生成的信息时，并不真正需要让系统等待x秒再处理该事件。 在模拟系统中，一般不需要使用真实的精确事件，只要用一个时间单位即可，这个时间单位是嘀 嗒tick，可以表示1秒，也可以表示1min1h.沿着时间轴，模拟每一个嘀嗒中发生了什么事件并处理该事件。模拟开始时时钟是0嘀嗒，随后每一步都把时钟加1嘀嗒，并检查这个时间内是否有事件发生
4、，如果有，则处理并生成统计I 口 J 匕、o3. 离散的事件驱动模拟 离散的时间驱动模拟连续地处理每个事件单位，如果在很长一段时间内没有任何事件发生， 程序海必须检查每个嘀嗒中是否有事件发生，这很浪费计算机的时间。因此，可以将事件按照发生时间排队，当一个事件处理结束后，直接将时间拨到下一个事件 的发生时间，处理下一事件，这就是事件驱动模拟。二、模拟一个单服务台排队系统1. 原理模拟银行中只有一个服务台，顾客到达的时间间隔服从arrivalLow, arrivalHigh的均匀 分布，服务时间长度服从serviceLow,serviceHigh的均匀分布，一共模拟custNum个顾客，要 求统计
5、顾客的平均服务时间。整个模拟由3个步骤组成：首先生成所有的顾客到达事件，按到达时间排成一个队列；其次， 服务员一旦有空，就为队头元素服务，在提供服务前先检查该顾客等待了多少时间，记入累计值； 最后，在所有顾客服务完以后，返回累计值除以顾客数的结果。2. 伪代码totalWaitTime=0;设置顾客开始到达的时间currentTime=0;for(i=0;icustNum;+i)生成下一顾客到达间隔时间；下一顾客到达时间currentTime+二下一顾客到达的间隔时间；/currentTime二currentTime+ 下一顾客到达的间隔时间，红色的currentTime 直为0,蓝色的下一顾
6、客到达的间隔时间为随 机数生成器生成的随机数。将下一顾客的到达时间入队；从时刻0开始模拟；while (顾客队列非空)取队头顾客；if (到达时间当前时间)直接将时钟拨到事件发生的时间;else 收集该顾客的等待时间；生成服务时间; 将时钟拨到服务完成的时刻;返回 等待时间/顾客数3. 代码分析4-6代码分析链接队列类的定义template class linkQueueprivate:st ruct node/定义一个结点结构体elemType data; /存储数据部分node* next; /存储指向下一个数据的指针部分node(const elemType &x,node*N=NULL
7、)/定义一个node，它包含数据部分和指针部分 data=x;next=N; /给 data 和 next 赋值node():next(NULL) /什么参数都没有，就令为空node()/析构函数，释放空间;node*front,*rear; /结点的队头和队尾public:linkQueue() front=rear=NULL; /空队列，队头和队尾都为空linkQueue();/析构函数，释放空间bool isEmpty() return front=NULL; /判队列空void enQueue(const elemType &x); /进队elemType deQueue();/ 出队
8、elemType getHead() return front-data; /返回队头元素值;4-7代码分析析构函数的实现template linkQueue :linkQueue()node*tmp; /定义一个跟随指针，确保能够找到头结点 while(front!=NULL) /当头结点不为空，进行下列循环 tmp=front; /tmp扌旨向头结点 front=front-next; /头结点指向下一位 delete tmp; /删除tmp所指结点4-8代码分析 链接队列类中enQueue和deQueue运算的实现template void linkQueue :enQueue(cons
9、t elemType &x) /进队 if(rear=NULL) /如果队尾为空front=rear=new node(x); /则队头=队尾=新结点elserear-next=new node(x); /否则队尾的后继旨针旨向新结点 rear=rear-next; /更新队尾，现在队尾为新添加的结点template elemType linkQueueelemType：deQueue()/ 出队node *tmp=front; /定义一个旨针旨向队头elemType value二fro nt-da ta; /队头元素值用 v alue 保存front=front-next; /队头往后移一个
10、，队头更新if(front=NULL) rear=NULL;delete tmp; /删除原来的队头return value; /返回原来队头元素值4-10代码分析 模拟类simulator的定义class simulatorint arrivalLow; /到达间隔时间下限int arrivalHigh; /到达间隔时间上限int serviceTimeLow; /服务时间下限int serviceTimeHigh; /服务时间上限int customNum; /模拟的顾客数public:simulator();int avgWaitTime() const; /平均等待时间(常数);4-1
11、1代码分析构造函数的实现simulator:simulator()cou t请输入到达间隔时间的上、下界:；/屏幕输出“”里的文字，一般输入数字cin arrivalLow arrivalHigh; /计算机读入输入的参数cou t请输入服务时间的上、下界:；cin serviceTimeLow serviceTimeHigh;cou t请输入模拟的顾客数:;cin customNum；srand(time(NULL); /初始化随机数发生器4-12代码分析avgWaitTime函数的实现int simulator:avgWaitTime() constint currentTime=0; /
12、当前时间int totalWaitTime=0; /总的等待时间int evenTime; /顾客到达时间，根据到达时间入队linkQueue customerQueue; /定义一个链接队列，存放顾客到达时间，生成到达事 件int i;for(i=0;icustomNum;+i) /生成所有的到达事件currentTime+=arrivalLow+(arrivalHigh-arrivalLow+1)* rand()/(RAND_MAX+1); customerQueue.enQueue(currentTime);/循环体的含义是生成所有顾客的到达时间，并按照到达时间的次序存入队列 curre
13、ntTime=0;while(! customerQueue.isEmpty() evenTime二cus to merQueue.deQueue();/ 队头元素if(evenTimecurrentTime) totalWaitTime+=currentTime-evenTime;/判断顾客的到达时间和当前时间，如果到达时间比当前时间要小，说明顾客已经等待了一段时 间，则统计总的等待时间else curre nt Time二evenTime;/如果到达时间不小于当前时间，说明顾客还没到达，还 没入队，可以将时钟直接拨到事件发生的时间。currentTime+=serviceTimeLow+
14、(serviceTimeHigh-serviceTimeLow+1)*rand()/(RAND_MAX+1); /随机生成服务时间return totalWaitTime/customNum; /返回平均等待时间4-13代码分析simulator类的使用#include stdafx.h#include simulator.h #include using namespace std;int main(int argc, char* argv)simula tor sim; /定义一个Simula tor类对象sim,在Simula tor类的对象的构造过程中， 会调用构造函数输入模拟参数cout平均等待时间：sim.avgWaitTime()endl; /调用 avgWaitTime 函数得到模拟 结果return 0;
