这里我们模拟一下银行排队叫号系统的实现：
假设一个银行有4个窗口对外接待客户。由于每个窗口在某一时刻只能接待一个客户，在客户众多的时候需要排队，对于刚进入银行的客户，如果某个窗口正空闲，
则可上前办理业务，如果所有窗口都不空闲则排在人数最少的窗口。
现在要求模拟银行的某一时间段内的4个窗口的客户排队情况。这里客户到达的时刻和办理业务的时间都是随机的。
首先我们银行发生事件，我们得有一个类表示事件对象
/* *功能：这个实现的是我们事件的数据单元节点 *文件：Event.h *时间：2015年7月8日20:55:32 *作者：cutter_point */ #ifndef EVENT_H #define EVENT_H class Event { int OccurTime; //事件发生的时刻 int NType; //事件类型，0表示到达事件，1到4表示四个窗口的离开事件 public: Event() //初始化，我们把事件发生的事件和事件类型都首先视为0 { this->OccurTime = 0; this->NType = 0; } Event(int Occur,int type) { this->OccurTime = Occur; this->NType = type; } //重写=操作符，运算符的重载 /* Event& operator=(const Event& event) { if (event == NULL) { } } */ //set和get方法 void setOccurTime(int OccurTime) { this->OccurTime = OccurTime; } int getOccurTime() { return this->OccurTime; } void setNType(int type) { this->NType = type; } int getNType() { return this->NType; } }; #endif
接着我们用一个链表来存放我们的事件发生链
/* *功能：这个实现的是链表的功能 *文件：LinkList.h *时间：2015年7月7日20:33:18,2015年7月8日20:01:31 *作者：cutter_point */ #ifndef LINKLIST_H #define LINKLIST_H #include "Event.h" #include <stdio.h> using namespace std; //链表的一个节点 class Node { Event event; //创建我们的数据元对象，包含一个事件发生时间和一个事件类型 Node* next; public: Node() { this->next = nullptr; } Node(Event e) { this->event = e; this->next = nullptr; } //set和get方法 void setEvent(Event e) { this->event = e; } Event getEvent() { return this->event; } void setNext(Node* n) { this->next = n; } Node* getNext() { return this->next; } }; //我们的链表 class LinkList { Node* head; //头指针 Node* getTail(); //得到尾部指针 public: LinkList(){ this->head = new Node(); } void insert(Event e); //给链表末尾添加一个元素 Node* pop(); //删除最后一个节点 bool listEmpty(); //判断是否是空链表 Node* getHead(); //取得头指针 }; #endif
实现：
/* *功能：这个实现的是链表的功能 *文件：LinkList.cpp *时间：2015年7月7日20:33:18,2015年7月8日20:01:31,2015年7月9日20:42:11 *作者：cutter_point */ #include "LinkList.h" #include <iostream> using namespace std; /*******************************************************Node****************************************************************************/ /*******************************************************LinkList****************************************************************************/ //void insert(Event e); //给链表末尾添加一个元素 void LinkList::insert(Event e) { //插入一个元素,首先我们判断链表中是否含有元素 bool a; if (a = this->listEmpty()) //为true就是真 this->head = new Node(); //现在不管是否含有元素都有一个元素了，但是这个元素时空的，来作为头，接着我们把新的元素添加进去 Node *p = this->head; //用一个游标指针 Node* val = new Node(e); //然后把新的val接到元素的末尾 p = this->getTail(); //现在p指向尾元素，我们把元素接到末尾 p->setNext(val); //吧val设为尾部的元素 } //Node* getHead(); //取得头指针 Node* LinkList::getHead() { return this->head; } Node* LinkList::getTail() { Node* p = this->head; while (p->getNext() != nullptr) { p = p->getNext(); //循环到最后一个节点 } return p; } //Node* pop(); //删除最后一个节点 Node* LinkList::pop() { //用一个游标指针 Node* p = this->getHead(); Node* q = this->getHead(); //首先判断是否还有元素可以删除,这个的判断条件就是头指针后面那个是不是为空的 if (p->getNext() == nullptr) { cout << "事件表为空" << endl; return nullptr; } //循环到最后一个和倒数第二个 while (p->getNext() != nullptr) { q = p; //得到上一个节点 p = p->getNext(); //去下一个节点 } //如果末尾不为空，说明还有元素，那么我们就删除掉最后一个,并返回最后一个 q->setNext(nullptr); //吧倒数第二个设定为空，断开连接 return p; //返回断开后的那个数据的指针 } //bool listEmpty(); //判断是否是空链表 bool LinkList::listEmpty() { //判断是否为空的标识就是头指针和尾指针是同一个节点，那么就代表为空 if (this->getHead() == this->getTail()) { //没有下一个节点 return true; } return false; //头结点的下一个不为空 }
然后我们用一个队列对象，来表示银行窗口的队列：
/* *功能：这个实现的是我们事件的队列 *文件：LinkQueue.h *时间：2015年7月9日17:17:09 *作者：cutter_point */ #ifndef LINKQUEUE_H #define LINKQUEUE_H class QNode { int arrivalTime; //时间到达时间 int duration; //处理业务所需要的时间 QNode* next; //指向下一个节点 public: QNode() { this->arrivalTime = 0; this->duration = 0; this->next = nullptr; } QNode(QNode* e) { this->arrivalTime = e->arrivalTime; this->duration = e->duration; this->next = nullptr; } //set和get方法 void setArrivalTime(int arrival) { this->arrivalTime = arrival; } int getArrivalTime() { return this->arrivalTime; } void setDuration(int dur) { this->duration = dur; } int getDuration() { return this->duration; } void setNext(QNode* n) { this->next = n; } QNode* getNext() { return this->next; } }; class LinkQueue { //QNode* base; //初始化的动态分配存储空间 QNode* front; //队列的头 QNode* rear; //队列的尾 public: LinkQueue(); //初始化 void enQueue(QNode* e); //插入数据 QNode deQueue(); //删除一个数据 bool queueEmpty(); //判断队列是否为空 QNode getHead(); //获取队列的头元素 int length(); //set和get方法 void setFront(QNode* qn) { this->front = qn; } QNode* getFront() { return this->front; } void setRear(QNode* qn) { this->rear = qn; } QNode* getRear() { return this->rear; } }; #endif
实现：
/* *功能：这个实现的是我们事件的队列 *文件：LinkQueue.h *时间：2015年7月9日17:17:09,2015年7月10日15:18:58 *作者：cutter_point */ #include "LinkQueue.h" //LinkQueue(); //初始化 LinkQueue::LinkQueue() { //初始化队列的时候，队列是先进先出 //首先我们创建一个新的空节点 this->rear = this->front = new QNode(); this->front->setNext(nullptr); //初始化的时候只有一个节点，后面的设置为nullptr } //得到队列的长度 int LinkQueue::length() { //由于第一个是空的，所以我们判断队列的长度就是尾部和首部的长度 int length = 0; QNode* p = this->front; //用一个游标当做指针，指向相应的位置 while (p != this->rear) { p = p->getNext(); ++length; } return length; //返回队列的长度 } //void enQueue(QNode* e); //插入数据 void LinkQueue::enQueue(QNode* e) { //吧原始e插入到队列中，由于我们的是链表，不用考虑队列会不会满的问题，如果是线性表，我们还要考虑队列是否满的问题，因为初始化的时候，线性表示一次性申请完全的 this->rear->setNext(e); //然后重置尾节点 this->rear = this->rear->getNext(); } //QNode deQueue(); //删除一个数据,删除的是队首元素 QNode LinkQueue::deQueue() { //这个就是出队列的动作 QNode e; //设置两个游标 QNode* p,* q; //我们首先得判断一下是不是只有一个节点，如果是只有一个有效节点，那么就得更新rear if (this->getFront()->getNext() == this->getRear()) { this->setRear(this->getFront()); //设置到头结点上 } //我们的操作就是把头后面的那个节点拿出来，抛出来 p = this->getFront(); q = p->getNext(); //断裂头和第一个元素的指针，吧指针指向后面一个节点 p->setNext(q->getNext()); q->setNext(nullptr); //吧q这个节点的值赋值给e然后返回，并回收q的内存 e.setArrivalTime(q->getArrivalTime()); e.setDuration(q->getDuration()); e.setNext(nullptr); delete q; return e; } //bool queueEmpty(); //判断队列是否为空 bool LinkQueue::queueEmpty() { //判断是不是为空的理由就是头和尾是不是指向一个地方 if (this->getFront() == this->getRear()) { return true; } else { return false; } } //QNode getHead(); //获取队列的第一个元素,这里只是返回第一个元素的拷贝元素 QNode LinkQueue::getHead() { QNode e; e.setArrivalTime(this->getFront()->getNext()->getArrivalTime()); e.setDuration(this->getFront()->getNext()->getDuration()); e.setNext(nullptr); return e; }
我们的主函数：
/* *功能：假设一个银行有4个窗口对外接待客户。由于每个窗口在某一时刻只能接待一个客户，在客户众多的时候需要排队，对于刚进入银行的客户，如果某个窗口正空闲， 则可上前办理业务，如果所有窗口都不空闲则排在人数最少的窗口。 现在要求模拟银行的某一时间段内的4个窗口的客户排队情况。这里客户到达的时刻和办理业务的时间都是随机的。 ************************************************************************** ****这里没有用到线程，其实更好的办法是使用线程，一个线程用来不断产生 **** ****事件（客户的到达）,一个线程不断的处理事件，客户的离开，只要银行不 **** ****关门，当事件表为空的时候我们就wait()一个线程，当队列中还有客户的 **** ****时候就吧线程notify，知道银行关门我们就interrupt线程，结束退出 **** ************************************************************************** *文件：queue.cpp *时间：2015年7月7日20:33:18,2015年7月9日20:02:20,2015年7月10日16:45:52,2015年7月12日15:16:41 *作者：cutter_point */ #include "Event.h" #include "LinkList.h" #include "LinkQueue.h" #include <iostream> #include <ctime> using namespace std; const static int COUNTER = 5; //一共4个窗口 const static int MAX_TIME = 30; //这个是最大的事务处理时间 const static int INTERVAL = 5; //每五分钟内出现一个客户 LinkList ev; //事件表 Event en; LinkQueue* q[COUNTER]; //这个设定为指针数组，数组里面的每个元素是一个指向LinkQueue的指针 QNode customer; int TotalTime,CustomerNum,closeTime = 50; void open_for_day() { cout << "************************************************************************" << endl; cout << "***** 银行开门 *****" << endl; cout << "***** 银行开门 *****" << endl; cout << "************************************************************************" << endl; //初始化所有的数据 TotalTime = 0; CustomerNum = 0; en.setOccurTime(0); en.setNType(0); //初始化所有队列 for (int i = 1; i < COUNTER; ++i) { q[i] = new LinkQueue(); } }//open_for_day() //求得最短的队列 int min_queue(LinkQueue* q[COUNTER]) { int max = 0,usei = 1; for (int i = 1; i < COUNTER; ++i) { //循环遍历所有的队列选出最大的那个队列 int testmax = q[i]->length(); if (testmax > max) { max = testmax; usei = i; } } //循环完毕之后max是所有队列中最大的那个 return usei; } void customer_arrived() { cout << "======================一位客户到达======================" << endl; //处理客户到达事件，en.NType=0 QNode *qe = new QNode(); //客户到达时间，处理业务所需要的时间，指向下一个对象 int durtime,intertime; //一个是处理业务所需要的时间，一个是下一个客户到达的所需时间 ++CustomerNum; //人数++ //参数两个随机数，代表处理业务需要的时间，下一个客户到达的时间 durtime = rand() % (MAX_TIME + 1); //这个额是[0 ~ MAX_TIME(30)] intertime = rand() % (INTERVAL + 1); //这个是下一个客户进入银行要等待的时间[0~INTERVAL(5)] //如果银行没有关门，我们要产生下一个事件到达 int t = en.getOccurTime() + intertime; if (t < closeTime) { //插入事件表下一个事件 Event ei; ei.setOccurTime(t); ei.setNType(0); ev.insert(ei); } int i = min_queue(q); //求得最短的队列，注意我们有1到4队列，没有0队列 //吧事件插入到最短的队列中 //首先我们的事件发生时间(事件到达时间)和执行时间 qe->setArrivalTime(en.getOccurTime()); qe->setDuration(durtime); //时间的执行时间 q[i]->enQueue(qe); //吧qe插入到链表中 //判断我们插入的队列是不是长度是1，如果是代表在插入之前这个窗口是空的，这个的作用 //客户离开事件，是要首先计算该客户在银行逗留的时间，然后从队列中删除该客户之后查看队列是否为空，若不为空则设定一个新的对头客户离开事件 en.setOccurTime(en.getOccurTime() + durtime); //设置新的时间到达事件 en.setNType(i); //0代表新的客户到达，1是1号窗口客户离开，2是2号窗口客户离开，3是3号窗口客户离开，4是。。。,这里是客户到达事件，所以是0 if (q[i]->length() == 1) { //吧第i个队列的离开事件插入事件表，等会用来计算窗口的客户总时间 ev.insert(en); } }//customer_arrived() //处理客户离开事件，是要首先计算该客户在银行逗留的时间，然后从队列中删除该客户之后查看队列是否为空，若不为空则设定一个新的对头客户离开事件 void customer_departure() { cout << "======================一位客户离开======================" << endl; //处理客户离开事件，就是Ntype > 0 int i = en.getNType(); //得到事件的类型 q[i]->deQueue(); //吧排头删除,表示排头客户离开 TotalTime += en.getOccurTime() - customer.getArrivalTime(); //这个是客户逗留事件，不包含处理业务的时间，这个计算的也就是客户等待时间 //如果走了这个客户，队列不是空，则设定一个新的排头客户 if (q[i]->length() != 0) { Event e; customer = q[i]->getHead(); //得到排头的客户 e.setOccurTime(en.getOccurTime() + customer.getDuration()); //客户开始办理业务时间+客户使用时间，也就是到了客户离开时间 e.setNType(i); //那个窗口的 ev.insert(e); } } //这个函数用来产生一系列事件,我们首先产生20个事件 void create_event() { for (int i = 1; i < 2; ++i) { customer_arrived(); } } void bank_smiulation(int closeTime) { open_for_day(); //银行开始业务 create_event(); //产生事件 while (!ev.listEmpty()) //只要事件表还没空 { //Node* p = ev.getHead(); //从事件链表中弹出事件 Node* p = ev.pop(); en = p->getEvent(); //取出时间 if (en.getNType() == 0) { //客户到达事件 customer_arrived(); } else { //客户离开 customer_departure(); } }//while //计算并输出平均逗留时间 cout << "平均逗留时间是：" << (float)TotalTime/CustomerNum << endl; } int main() { bank_smiulation(closeTime); //ev.getHead()->getEvent().getOccurTime(); //cout << "hello world" << ev.getHead()->getEvent().getOccurTime()<<endl; return 0; }
实现效果：
