队列的基本概念·循环队列·银行排队场景驱动管理

╰半夏微凉° 2023-07-10 08:19 35阅读 0赞

1.链队列  
结点：

typedef struct QNode{
    	QElemType data;
    	struct QNode *next;
    }QNode,*QueuePTR;

队列：

typedef struct{
    	QueuePtr front; //队头指针 
    	QueuePtr rear; //队尾指针 
    }LinkQueue;

2.循环队列（线性）  
（最大表长为定值，没有增量）  
银行排队，四个窗口，计算顾客平均逗留时间

#define MAXQSIZE 100
    typedef struct{
    	QElemType *base; //初始化的动态分配存储空间 
    	int front; //头指针，若队列不空，指向队列列头元素 
    	int rear; //尾指针，若队列不空，指向列尾元素的下一个位置 
    }SqQueue;

驱动模拟：模拟程序按照事件发生的先后顺序进行处理，如先后处理客户到达银行和客户离开银行  
3.队列的应用（离散时间模拟·驱动模拟）  
①写出模拟程序的大纲（伪代码），能根据意思写函数名

void Bank_Simulation(int CloseTime){ //统计一天内客户在银行逗留的平均时间 
    	OpenForDay();//初始化
    	while(MoveMent){
    		EventDrived(OccurTime,EventType); //事件驱动
    		switch(EventType){
    			case'A':CustomerArrived();break;
    			case'D':CustomerDeparture();break;
    			default:Invalid();
    		} //switch-
    	} //while
    	CloseForDay;//计算平均逗留时间 
    }//Bank_Simulation

②分析数据类型，构造结构体（数据类型）  
从大面上看，程序驱动按照事件发生先后顺序进行，故时间表应为有序表，主要操作为插入和删除，所以要用链表；  
排队问题，队头出，队尾进，所以需要用到栈

事件类型（有序链表LinkList中的元素类型）：

typedef struct{
    	int OccurTime;//事件发生时刻
    	int NType;//事件类型，0为到达时间，1至4为四个窗口的离开事件 
    }Event,QElemType; 
    
    typedef LinkList EventList //链表类型定义事件

队列的数据元素的类型：

typedef struct{
    	int ArrivalTime;
    	int Duration;
    }QElemType;

③函数细节填写  
EventList ev;//时间表

Event en;//时间
    LinkQueue q[5];//4个客户队列
    QElemType customer;//客户记录
    int TotalTime,CustomerNum;//累计客户逗留时间，客户数
    
    int cmp(Event a,Event b); //a事件发生时间早则返回-1,；=；1 
    
    void OpenForDay(){
    	TotalTime=0; CustomerNum=0;
    	InitList(ev); //初始化时间链为空表
    	en.OccurTime=0; en.NType=0; 
        OrderInsert(ev,en,cmp); //插入事件表
    	for(i=1;i<=4;i++) InitQueue(q[i]); //置空队列 
    } //OpenForDay
    
    void CustomerArrived(){ //处理客户到达事件，en.Ntype=0 
       ++CustomerNum;
       Random(durtime,intertiom); //durtime为客户在银行逗留时间，intertime为下一个客户（occurtime+intertime）过多久才会进来
       t=en.OccurTime+intertime;
       if(t<CloseTime)  //银行还没关门
       orderInsert(ev,(t,0),cmp);
       i=Minimum(q); //求长度最短队列
       EnQueue(q[i],(en.OccurTime,durtime));
       if(QueueLength(q[i]==1))
       OrderInsert(ev.(en.OccurTime+durtime,i)cmp); //设置第i个队列的一个离开时间并插入时间 
    }//CustomerArrived;
    
    void CustomerDepature(){ //处理客户离开事件，en.NType>0
     i=en.NType;DelQueue(q[i],customer); //删除第i队列的排头客户
     TotalTime+=en.OccurTime-customer.ArrivalTime;
     if(!QueueEmpty(q[i])){ //设置第i队列的一个离开事件，并插入事件表 
     	GetHead(q[i],customer);
     	OrderInsert(ev,(en.OccurTime+customer.Duration,i),(*cmp)();)
     } //if
    } //CustomerDepature
    
    void Bank_Simulation(int CloseTime){
    	OpenForDay();
    	while(!ListEmpty(ev)){
    		DelFirst(GetHead(ev),p);
    		en=GetCurElem(p);
    		if(en.NType==0) CusomerArrived();
    		else CusomerDepature();
    	}
    	printf("The Average Time is %f\n",(float)TotalTime/CustomerNum); //输出顾客平均逗留时间 
    }//Bank_Simulation