银行排队模拟算法描述
（要完整查看算法的伪代码，请在计算机端浏览此文档）
在日常生活中，我们经常会遇到许多需要排队才能维持秩序的情况。这类事情的模拟程序通常需要数据结构，如队列和线性表。因此，它是队列的一个很好的应用实例。这是一个银行模拟程序。
假设某银行有四个窗口对外接待客户，从早晨银行开门起不断有客户进入银行。由于每个窗口只能接待一个客户，因此在客户人数众多时需在每个窗口前顺次排队，对于刚进入银行的客户，如果某个窗口的业务员正在空闲，则可上前办理业务，反之，若四个窗口均有客户所占，他便会排在队伍的后面。现在需要编制一个程序以模拟银行的这种业务活动并计算一天中客户在银行逗留的平均时间。
为了计算这个平均值，我们要掌握每个客户到达银行和离开银行这两个时间，后者减去前者即为每个客户在银行的逗留事件。所有客户逗留时间的总和被一天内进入银行的客户数除便是所求的平均时间。
每个客户到达银行的时间是自然形成的，而离开银行的时间则和银行的整个对外业务活动有关。假设客户到达后即可办理业务，则他在银行的逗留时间即为他办理业务所需的时间；否则尚需加上他排队等候的时间。
下面我们来讨论模拟程序所需的数据结构。显然，需要四个队列以表示四个窗口前的客户队列，队列中每个元素标识排队等会的客户，队尾元素为最迟进入银行的客户，而队头元素则表示正被银行业务员接待的客户。只有下列五种情况发生会促使队列发生变化：一种情况是新的客户进入银行，他将加入元素最少的队列而成为该队列新的队尾元素；另四种情况是某个正被业务员接待的客户办理完业务离开银行。整个模拟程序就是按时间先后顺序一个接一个处理这些事件。这样一种模拟程序称作事件驱动模拟。
假设事件表中最早发生的事件是新客户到达，则随之应得到两个时间：一是本客户办理业务所需时间；二是下一个客户将到达银行的时间间隔。此时模拟程序应做的工作是：1）比较四个队列中的个数，将新到客户加入到元素个数最少的队列中成为新的队尾元素。若该队列原为空，则刚插入的队尾元素也是队头元素，此时应设定一个事件——刚进入银行的客户办理完业务离开银行的事件，并插入事件表；2）设定一个新的事件——下一个客户即将到达银行的事件，插入事件表；若最早发生的事件是某个队列中的客户离开银行，则模拟程序需要做的工作是：1）该客户出队列，并计算他在银行逗留时间；2）当该队列非空时，计算新的队头元素将离开银行的时间，并由此设立一个新的离开事件，并插入事件表。
由此，可考虑如下存储结构：
1）由于队列中的最大长度无法预测，而且长度变化较大，故采用单链表做存储结构为宜。每个结点表示一个排队等待的客户，Client它包含两个数据域：arriveTime 和 duration（分别表示客户到达银行的时间和办理业务所需时间）。同时，为查找方便，设定LinkQueue队列类，包含三个属性front、rear和length（分别指示队头、队尾和队列中元素个数），设置队列对象数组，包含四个队列，每个队列反映0-3号窗口的排队情况。
//定义银行客户，Client作为队列的data域
typedef struct client{
int arrivalTime;// 客户到达银行的时间
int duration; // 办理业务所需时间
}Client;
//定义队列结点类型
struct Node{
Client data;
struct Node *next;
};
//定义队列类
class LinkQueue{
private:
Node *front, *rear;
int length; //队列元素个数
public:
LinkQueue(); //建立头结点，初始化属性
~LinkQueue(); //释放队列空间
void enQueue(Client x); //入队
bool deQueue(Client *item); //出队
bool getFront(Client *item); //获取队头元素到item所指单元
bool isEmpty();
void clearQueue(); //清空队列
void displayQueue(); //显示队列内容
int queueLength(); //获取队列元素个数
};
用以上方式实现的队列，采用如下命令，可以定义4个队列数组：
LinkQueue queue[4];
要求按照上述类的声明，编写LinkQueue链队列。
2）由于事件表需按事件发生的先后顺序排列，需经常进行插入动作，则也采用单链表做存储结构。每个结点包含两个数据域：occurTime和nType（分别表示事件发生的时间和事件的类型-1表示新用户，0-3表示客户离开1-4个窗口）。
typedef struct evnode{
int occurTime; //事件发生时间
int nType; //事件类型，-1表示到达事件，0-3表示四个窗口的离开事件
struct evnode *next; //指针域
}evNode;
我们需要定义一个链表处理类，来完成银行事件的处理流程，这个链表处理类是一个有序链表，最多5个结点，分别对应新到达客户，和四个不同的窗口队列的离开事件。链表处理类的类定义如下：
class EventList{
private:
evNode *head;
public:
EventList();
~EventList();
bool isEmpty();
void addNode(evNode ev);
bool deleteNode(evNode *firstEv);
void displayNode();
};
要求按照上述类的声明，编写EventList类，此类的结点是按照occurTime从小到大排序的。
现写出银行业务活动如下：
double simulation(){
int totalTime = 0; //为客户服务的总时长
int customerNum= 0; //客户人数
//定义队列数组queue，下标0至3分别代表4个排队窗口队列
LinkQueue<Client> queue[4];
//建立事件链表对象，设定第一个客户到达的事件
EventList evList;
//初始化事件列表，加入第一个结点，起始时间为0，第一个事件为-1（新客户到达事件）
//设置evItem值为[0,-1,NULL];
evItem = [0,-1,NULL];
evList.addNode(evItem);
//扫描并处理事件列表
while(!evList.isEmpty()){
//删除事件链表中第一个结点存入evItem
evList.deleteNode(&evItem);
if(evItem.nType == -1){
/* –是新客户到达事件– */
// 客户人数加1
customerNum++;
// 输入随机数durTime 和interTime，（durTime代表当前客户服务时间,
// interTimed代表下一个客户到来的间隔时间）
if (evItem.occurTime+interTime < CLOSE_TIME) { //在银行关门之前
//设定下一位客户到达的事件插入事件表
evTemp.occurTime = evItem.occurTime + interTime;
evTemp.nType = -1;
evTemp.next = NULL;
evList.addNode(evTemp);
}
//为当前客户找到排队人数最少的队列下标
int min = findMin(queue,4);
//当前客户进入人数最少的队列
client.arrivalTime=evItem.occurTime;
client.duration = durTime;
queue[min].enQueue(client); //入队
//如果当前客户到达的窗口没有人在排队(他是第一个客户)
if(queue[min].queueLength()==1) {
//设定第一个客户离开银行的事件，插入事件表
evTemp.occurTime = evItem.occurTime + durTime;
evTemp.nType = min;
evList.addNode(evTemp);
}
}
else{
/* –是客户离开事件– */
//获得客户所在的窗口号(队列号)
int win= evItem.nType;
//将当前要离开的客户从队列中删除，并将当前客户信息存入client
queue[win].deQueue(&client);//出队
//计算客户在银行逗留时间，把当前客户的服务时间累加到totalTime中
totalTime = totalTime + client.duration;
//如果还有人在排队，则把队头客户的离开事件插入事件表
if (queue[win].queueLength()!=0){
//获取队头结点数据
queue[win].getFront(&client);
//把队头结点的离开事件插入到事件表中
evTemp.occurTime = evItem.occurTime+client.duration;
evTemp.nType = win;
evList.addNode(evTemp);
}
}
}
//计算客户平均处理时间
return totalTime*1.0/customerNum; //返回客户平均处理时间
}
参考文献：