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

《栈和队列及其应用-理发室问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、栈和队列及其应用目的：（1）了解栈和队列的特性，以便在实际问题背景下灵活运用应用；（2）巩固对这两种结构的构造方法的理解。一、问题描述：1、题目内容：使用队列模拟理发馆的排队现象，通过仿真手法评估其营业状况。设某理发馆设有N把理发椅，可同时为N位顾客进行理发。当顾客进门时，若有空闲理发椅，则立即入座理发，否则依次排队候理，一旦有顾客理完发离去时，排在队头的顾客便开始理发。假若理发馆每天连续营业T小时（只要有顾客等待，理发椅就不空），求一天内顾客在理发馆内的平均逗留时间（包括理发所需时间和排队等候的时间）与顾客排队等候理发的人数的平均值（排队长度的平均值）。2、基本要求（1）当给定

2、理发椅数及营业时间后，由随机数确定顾客理发时间及进门间隔时间，求出一天内顾客在理发馆平均逗留时间、平均队长及关门后收尾工作的时间。（2）由用户读入的数据仅为理发椅数及营业时间。营业的时间以分钟计，理发椅数及关门时间均为整型，且均大于等于1。3、测试数据理发椅数目N及关门时间由用户读入，第一个顾客进门的时刻为0，之后每个顾客的进门时刻在前一个顾客进门时设定。即在进门事件发生时随即产生两个随机数（DU，IN），DU为进门顾客理发所需的服务时间（简称理发时间）；IN为下一个顾客到达的时间间隔（简称间隔时间）。二、实现提示：R为由随机数发生器的随机数，顾客理发时间和顾客之间的间隔时间不妨

3、假设与R有关，可以由下式确定：DU=15+R%50IN=2+R%10确定的方法与实际越吻合，模拟的结果越接近现实的情况。#include#include#include#defineXX12//本程序关键，XX控制随机数R的范围typedefintElemType;structQueue{ElemType*queue;intfront,rear,len;intmaxsize;};voidInit(Queue&Q,inti){Q.maxsize=i;Q.queue=newElemType[Q.maxsize];Q.fron

4、t=Q.rear=0;Q.len=0;}voidstr(Queue&Q,ElemTypex){if((Q.rear+1)%Q.maxsize==Q.front){intk=sizeof(ElemType);Q.queue=(ElemType*)malloc(2*Q.maxsize*k);if(Q.rear!=Q.maxsize-1){for(inti=0;i

5、)%Q.maxsize;Q.len++;}voiddelet(Queue&Q){Q.front=(Q.front+1)%Q.maxsize;Q.len--;}voidmain(){QueueQchair;//定义一个队列与空椅的相关联；QueueQwait;//定义一个队列与排队人数，是否轮在理发相关联；Init(Qchair,10);Init(Qwait,10);//初始化两个队列，并赋值长度为10intn,t;cout<<"请输入数据："<>n;cout<<"营业时间：";cin>>t;srand((int)time(0));in

6、th[1000];//理发所需时间intg[1000];//到来时间intx[1000][2];//开始理发时间和开始理发时队的长度inti=1;g[1]=0;//第一个顾客到来时间为0；intR;while(g[i]<60*t)//当最后一个顾客到来时间超过营业时间，结束操作{R=rand()%XX+1;//得到随机数Rh[i]=15+R%50;//根据随机数计算得到第i个顾客理发所需时间，并存放h数组中；g[i+1]=g[i]+2+R%10;//得到第i+1个顾客到来所需时间，得到第i+1个顾客实际到来时间，存放g数组中；i++;}inta(1),b(1),c(1);for(

7、i=0;i<60*t;i++)//当i<营业时间，执行{if(i==g[a])//若第a个顾客到达，让顾客加入排队队列{str(Qwait,i);a++;}if(Qchair.len>0&&(i-Qchair.queue[Qchair.front])>=h[c])//若理发顾客理发完成时，删除椅子队列首元素，空出一个位{delet(Qchair);c++;}if(Qchair.len0)//当椅子不为空和排队人数不为0时{delet(Qwait);//