银行业务模拟是队列中非常经典的应用之一，各种版本的数据结构教材在队列这一章节援引这一应用。
本程序算法来源于《数据结构（C语言版）》（清华大学出版社 严蔚敏，吴伟民编著）第65页。
本程序在Ubuntu14.10平台上，利用g++编译通过。
#include <stdio.h> #include <stdlib.h> #include <malloc.h> #include <time.h> #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERLOW -2 #define QNUMBER 5 //The bank has 4 windows //You can set the number of bank windows here!! //Note:the number of windows must lower than 4 !! #define OPENTIME 8 //Bank opens at 8:00 #define CLOSETIME 18 //Bank closes at 18:00 #define Q1_CUSTNUM 10000 //The first numberical order for first customer in queue1 #define Q2_CUSTNUM 20000 //The first numberical order for first customer in queue2 #define Q3_CUSTNUM 30000 //The first numberical order for first customer in queue3 #define Q4_CUSTNUM 40000 //The first numberical order for first customer in queue4 #define INTERTIME_LOWER 1 //You can set the range of intertime and durtime here!! #define INTERTIME_UPPER 10 #define DURTIME_LOWER 5 #define DURTIME_UPPER 20 /*------------------------------------------------------- definition of the storage structure -------------------------------------------------------*/ typedef struct { int OccurTime; //when event occur int NType; //0 re customer arrives,1-4 re customer at 1-4 window depart }Event,ElemType; typedef struct EventNode { Event event; struct EventNode *next; }EventNode,*EventPtr; typedef struct { EventPtr head; EventPtr rear; int length; }EventList; typedef struct { int ArrivalTime; //the time customer arrives int Durtime; //the time customer in service int CustNum; //a code for every customer }QElemType; typedef struct QNode { QElemType customer; struct QNode *next; }QNode,*QueuePtr; typedef struct { QueuePtr head; QueuePtr rear; int length; }LinkQueue; EventList ev; Event en; LinkQueue q[QNUMBER]; //four customer queues QElemType customer; //custromer record int TotalTime,CustomerNum,CloseTime;//record for the total time customers in bank, //and how many customers in bank one day. int q1,q2,q3,q4; //customer counter for matching queue. typedef int Status; /*----------------------------------------------------- function of element OP of LinkQueue -----------------------------------------------------*/ Status InitQueue(LinkQueue &Q){ Q.head = Q.rear = (QueuePtr)malloc(sizeof(QNode)); if(!Q.head) exit(OVERLOW); Q.head->next = NULL; Q.length = 0; return OK; } Status EnQueue(LinkQueue &Q,QElemType e){ QueuePtr p; p = (QueuePtr)malloc(sizeof(QNode)); if(!p) exit(OVERLOW); p->customer = e; p->next = NULL; Q.rear->next = p; Q.rear = p; Q.length++; return OK; } Status IsQEmpty(LinkQueue Q){ if(Q.head == Q.rear) return TRUE; //Q.length ==0; else return FALSE; } Status GetQHead(LinkQueue Q,QElemType &e){ e = Q.head->next->customer; return OK; } Status DelQueue(LinkQueue &Q,QElemType &e){ QueuePtr p; if(IsQEmpty(Q)) return ERROR; p = Q.head->next; e = p->customer; Q.head->next = p->next; if(Q.rear == p) //Queue only has one elememt Q.rear = Q.head; free(p); Q.length--; return OK; } Status QueueLength(LinkQueue Q){ return Q.length; } Status TypeQueue(LinkQueue Q,int qnum){ QueuePtr p; p = Q.head->next; int atime; if(p == NULL){ printf("Empty ListQueue:%d ",qnum); return OK; } printf("ListQueue:%-3dlength=%d ",qnum,Q.length); printf("ArrivalTime Customer_Num Durtime "); while(p!=NULL){ atime = p->customer.ArrivalTime; printf("%d:%d%d %d %d ",OPENTIME+atime/60,atime%60/10,atime%10, p->customer.CustNum,p->customer.Durtime); p = p->next; } return OK; } /*----------------------------------------------------- function of element OP of EventList -----------------------------------------------------*/ typedef int (*fp)(Event,Event); int compare(Event a,Event b){ if(a.OccurTime < b.OccurTime) return -1; if(a.OccurTime == b.OccurTime) return 0; if(a.OccurTime > b.OccurTime) return 1; } Status InitList(EventList &E){ E.head = E.rear = (EventPtr)malloc(sizeof(EventNode)); if(!E.head) exit(OVERLOW); E.head->next = NULL; //E.rear->next == NULL; E.length = 0; return OK; } Status ListEmpty(EventList E){ if(E.length == 0) return TRUE; else return FALSE; } Status OrderInsert(EventList &E,Event e,fp cmp){ //ascending order according the occurtime. Status TypeEventList(EventList E); EventPtr p,q,s; p = (EventPtr)malloc(sizeof(EventNode)); if(!p) exit(OVERLOW); p->event = e; p->next = NULL; if(E.head == E.rear){ E.rear->next = p; //E.head->next = p;(E.head = E.rear;) E.rear = p; E.length++; return OK; } if(E.head != E.rear){ q = E.head->next; if(cmp(e,q->event) < 0){ E.head->next = p; p->next = q; E.length++; return OK; } while(cmp(e,q->event) >= 0){ s = q; q = q->next; if(q == NULL){ E.rear = p; break; } } s->next = p; p->next = q; E.length++; } return OK; } Status GetEHead(EventList E,Event &e){ e = E.head->next->event; return OK; } Status DelFirst(EventList &E,Event &e){ Status TypeEventList(EventList E); GetEHead(E,e); EventPtr ep; ep = E.head->next; E.head->next = ep->next; if(E.rear == ep) E.rear = E.head; free(ep); E.length--; return OK; } Status TypeEventList(EventList E){ EventPtr p; int otime; p = E.head->next; if(p == NULL){ printf("Empty List "); return OK; } printf("EventList:length=%d ",E.length); printf("OccurTime NType "); while(p!=NULL){ otime = p->event.OccurTime; printf("%d:%d%d %2d ",OPENTIME+otime/60,otime%60/10, otime%10,p->event.NType); p = p->next; } return OK; } /*----------------------------------------------------- function of element OP Bank Business simulation -----------------------------------------------------*/ fp cmp = compare; void Note_CustomerArrived(QElemType Q){ printf(" %d:%d%d customer %d arrived: ",OPENTIME+en.OccurTime/60, en.OccurTime%60/10,en.OccurTime%10,Q.CustNum); TypeEventList(ev); for(int i=1 ; i<QNUMBER ; i++) TypeQueue(q[i],i); printf(" "); } void Note_CustomerDeparture(){ printf(" %d:%d%d queue%d customer %d departure: ",OPENTIME+en.OccurTime/60, en.OccurTime%60/10,en.OccurTime%10,en.NType,customer.CustNum); TypeEventList(ev); for(int i=1 ; i<QNUMBER ; i++) TypeQueue(q[i],i); printf(" "); } int Minimum(LinkQueue q[]){ int i,imin,min = 10000; for(i = 1 ; i < QNUMBER ; i++) if(q[i].length < min){ min = q[i].length; imin = i; } return imin; } void Random(int &durtime,int &intertime){ durtime = rand()%(DURTIME_UPPER - DURTIME_LOWER) + DURTIME_LOWER; //durtime re service time [5,15(min)] intertime = rand()%(INTERTIME_UPPER - INTERTIME_LOWER) + INTERTIME_LOWER;//intertime re the time between two customer reaching //[1,10(min)] } void OpenForDay(){ //Initialization for Band Queue model. TotalTime =0; CustomerNum =0; InitList(ev); en.OccurTime = 0; en.NType = 0; OrderInsert(ev,en,cmp); for(int i = 1 ; i <= 4 ; i++) InitQueue(q[i]); printf("%d:%d%d Bank Open!!! ",8,0,0); } Status CustomerArrived(){ //Handle the event that customers reaching. Event Etemp; QElemType Qtemp; int durtime,intertime; ++CustomerNum; Random(durtime,intertime); Qtemp.ArrivalTime = en.OccurTime; Qtemp.Durtime = durtime; Etemp.OccurTime = en.OccurTime + intertime; Etemp.NType = 0; if(Etemp.OccurTime < CloseTime) OrderInsert(ev,Etemp,cmp); else{ printf("%d:%d%d Bank Closed!! ",OPENTIME+CloseTime/60,CloseTime%60/10,CloseTime%10); return OK; } int i = Minimum(q); switch(i){ //Each customer was given a numerical order. case 1: Qtemp.CustNum = Q1_CUSTNUM + q1; q1++; break; case 2: Qtemp.CustNum = Q2_CUSTNUM + q2; q2++; break; case 3: Qtemp.CustNum = Q3_CUSTNUM + q3; q3++; break; case 4: Qtemp.CustNum = Q4_CUSTNUM + q4; q4++; break; } EnQueue(q[i],Qtemp); if(QueueLength(q[i]) == 1){ Etemp.OccurTime = en.OccurTime + durtime; Etemp.NType = i; OrderInsert(ev,Etemp,cmp); } Note_CustomerArrived(Qtemp); } void CustomerDeparture(){ //Handle the event that customers leaving. int i = en.NType; DelQueue(q[i],customer); Note_CustomerDeparture(); TotalTime += en.OccurTime - customer.ArrivalTime; if(!IsQEmpty(q[i])){ GetQHead(q[i],customer); Event temp; temp.OccurTime = en.OccurTime + customer.Durtime; temp.NType = i; OrderInsert(ev,temp,cmp); } } void Bank_Stimulation(){ //This is a event drived program,simulating the average serving //time on each customer. OpenForDay(); q1=q2=q3=q4=0; while(!ListEmpty(ev)){ DelFirst(ev,en); if(en.NType == 0) CustomerArrived(); else CustomerDeparture(); }//while printf("Today we sereved for %d customers. ",CustomerNum); printf("The average time is %.2f ",(float)TotalTime/CustomerNum); } /*----------------------------------------------------- function of main -----------------------------------------------------*/ int main(){ CloseTime = (CLOSETIME - OPENTIME)*60; int winnum = QNUMBER - 1; printf("Today there is %d windows open. ",winnum); srand((unsigned)time(NULL)); Bank_Stimulation(); }