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