栈及队列及其应用-理发室问题.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<iostream.h>
#include<stdlib.h>
#include<time.h>
#define XX 12 //本程序关键，XX控制随机数R的范围

typedef int ElemType;
struct Queue
{
ElemType *queue;
int front,rear,len;
int maxsize;
};

void Init(Queue &Q,int i)
{
Q.maxsize=i;
Q.queue=new ElemType[Q.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;i<Q.rear;i++)
{
Q.queue[i+Q.maxsize]=Q.queue[i];
}
Q.rear+=Q.maxsize;
}
Q.maxsize*=2;
}

Q.queue[Q.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);//初始化两个队列，并赋值长度为10

int n,t;
cout<<"请输入数据："<<endl;
cout<<"理发椅：";cin>>n;
cout<<"营业时间：";cin>>t;

srand((int)time(0));

int h[1000]; //理发所需时间
int g[1000]; //到来时间
int x[1000][2]; //开始理发时间和开始理发时队的长度

int i=1;
g[1]=0; //第一个顾客到来时间为0；

int R;
while(g[i]<60*t) //当最后一个顾客到来时间超过营业时间，结束操作
{
R=rand()%XX+1; //得到随机数R

h[i]=15+R%50; //根据随机数计算得到第i个顾客理发所需时间，并存放h数组中；

g[i+1]=g[i]+2+R%10; //得到第i+1个顾客到来所需时间，得到第i+1个顾客实际到来时间，存放g数组中；
i++;
}

int a(1),b(1),c(1);

for(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.len<n&&Qwait.len>0) //当椅子不为空和排队人数不为0时
{
delet(Qwait); //删除等待队列首元素
str(Qchair,i); //增加椅子队列
x[b][1]=Qwait.len; //记下此刻排队等待人数
x[b++][0]=i; //记下顾客开始理发时间；
}
}

for(;;i++) //收尾工作
{
if(Qchair.len>0&&(i-Qchair.queue[Qchair.front])>=h[c]) //若理发顾客理发完成时，删除椅子队列首元素，空出一个位
{
delet(Qchair);
c++;
}
if(Qchair.len<n&&Qwait.len!=0)//当椅子不为空和排队人数不为0时
{
delet(Qwait); //删除等待队列首元素
str(Qchair,i); //增加椅子队列
x[b][1]=Qwait.len; //记下此刻排队等待人数
x[b++][0]=i; //记下顾客开始理发时间；

}
if(Qchair.len==0&&Qwait.len==0) //当椅子队列为空和等待队列为空，即收尾工作结束；
break;
}

int m(0);
double l(0);
double k(0);
for(i=1;i<a;i++)
{
k+=x[i][0]-g[i]+h[i]; //顾客的逗留时间=顾客开始理发时间-顾客到来时间+顾客理发时间
l+=x[i][1]; //计算记下的等待长度的和；
}

k=k/(a-1);
l=l/(a-1);
m=x[a-1][0]+h[a-1]-60*t;
cout<<"顾客的平均逗留时间为:"<<k<<endl;
cout<<" 排队时平均队长为:"<<l<<endl;
cout<<" 关门后收尾时间为:"<<m<<endl;
}