栈和队列及其应用-理发室问题.doc

栈和队列及其应用目的：（1）了解栈和队列的特性，以便在实际问题背景下灵活运用应用；（2）巩固对这两种结构的构造方法的理解 。一、问题描述：1、题目内容：使用队列模拟理发馆的排队现象，通过仿真手法评估其营业状况。设某理发馆设有N把理发椅，可同时为N位顾客进行理发。当顾客进门时，若有空闲理发椅，则立即入座理发，否则依次排队候理，一旦有顾客理完发离去时，排在队头的顾客便开始理发。假若理发馆每天连续营业T小时（只要有顾客等待，理发椅就不空），求一天内顾客在理发馆内的平均逗留时间（包括理发所需时间和排队等候的时间）与顾客排队等候理发的人数的平均值（排队长度的平均值）。2、基本要求（1）当给定理发椅数及营业时间后，由随机数确定顾客理发时间及进门间隔时间，求出一天内顾客在理发馆平均逗留时间、平均队长及关门后收尾工作的时间。（2）由用户读入的数据仅为理发椅数及营业时间。营业的时间以分钟计，理发椅数及关门时间均为整型，且均大于等于1。3、测试数据 理发椅数目N及关门时间由用户读入，第一个顾客进门的时刻为0，之后每个顾客的进门时刻在前一个顾客进门时设定。即在进门事件发生时随即产生两个随机数（DU，IN），DU为进门顾客理发所需的服务时间（简称理发时间）；IN为下一个顾客到达的时间间隔（简称间隔时间）。二、实现提示： R为由随机数发生器的随机数，顾客理发时间和顾客之间的间隔时间不妨假设与R有关，可以由下式确定：DU=15+R%50 IN=2+R%10确定的方法与实际越吻合，模拟的结果越接近现实的情况。#include#include#include#define XX 12 /本程序关键，XX控制随机数R的范围typedef int ElemType;struct QueueElemType *queue;int front,rear,len;int maxsize;void Init(Queue &Q,int i)Q.maxsize=i;Q.queue=new ElemTypeQ.maxsize;Q.front=Q.rear=0;Q.len=0;void str(Queue &Q,ElemType x)if(Q.rear+1)%Q.maxsize=Q.front)int k=sizeof(ElemType);Q.queue=(ElemType*)malloc(2*Q.maxsize*k);if(Q.rear!=Q.maxsize-1)for(int i=0;iQ.rear;i+)Q.queuei+Q.maxsize=Q.queuei;Q.rear+=Q.maxsize;Q.maxsize*=2;Q.queueQ.rear=x;Q.rear=(Q.rear+1)%Q.maxsize;Q.len+;void delet(Queue &Q)Q.front=(Q.front+1)%Q.maxsize;Q.len-;void main()Queue Qchair; /定义一个队列与空椅的相关联；Queue Qwait; /定义一个队列与排队人数，是否轮在理发相关联；Init(Qchair,10);Init(Qwait,10);/初始化两个队列，并赋值长度为10int n,t;cout请输入数据：endl;coutn;coutt;srand(int)time(0);int h1000; /理发所需时间int g1000; /到来时间 int x10002; /开始理发时间和开始理发时队的长度 int i=1;g1=0; /第一个顾客到来时间为0； int R;while(gi60*t) /当最后一个顾客到来时间超过营业时间，结束操作 R=rand()%XX+1; /得到随机数Rhi=15+R%50; /根据随机数计算得到第i个顾客理发所需时间，并存放h数组中； gi+1=gi+2+R%10; /得到第i+1个顾客到来所需时间，得到第i+1个顾客实际到来时间，存放g数组中；i+;int a(1),b(1),c(1);for(i=0;i60*t;i+) /当i0&(i-Qchair.queueQchair.front)=hc) /若理发顾客理发完成时，删除椅子队列首元素，空出一个位 delet(Qchair);c+;if(Qchair.len0) /当椅子不为空和排队人数不为0时delet(Qwait); /删除等待队列首元素str(Qchair,i); /增加椅子队列xb1=Qwait.len; /记下此刻排队等待人数xb+0=i; /记下顾客开始理发时间； for(;i+) /收尾工作if(Qchair.len0&(i-Qchair.queueQchair.front)=hc) /若理发顾客理发完成时，删除椅子队列首元素，空出一个位 delet(Qchair);c+;if(Qchair.lenn&Qwait.len!=0)/当椅子不为空和排队人数不为0时delet(Qwait); /删除等待队列首元素str(Qchair,i); /增加椅子队列xb1=Qwait.len; /记下此刻排队等待人数xb+0=i; /记下顾客开始理发时间；if(Qchair.len=0&Qwait.len=0) /当椅子队列为空和等待队列为空，即收尾工作结束；break;int m(0);double l(0);double k(0);for(i=1;ia;i+) k+=xi0-gi+hi; /顾客的逗留时间=顾客开始理发时间-顾客到来时间+顾客理发时间l