最近重拾之前半途而廢的C++，恰好看到了《C++ 實現(xiàn)銀行排隊服務(wù)模擬》，但是沒有實驗樓的會員，看不到具體的實現(xiàn)，正好用來作為練習(xí)。
模擬的是銀行的排隊叫號系統(tǒng)，所有顧客以先來后到的順序在同一個隊列中等待，當(dāng)有服務(wù)窗口空閑時，則隊首的顧客接受服務(wù)，完成后則下一位顧客開始接受服務(wù)。
本實現(xiàn)是事件驅(qū)動型的，處理對象是事件而不是顧客：
有2種事件：顧客到事件和顧客離開事件。
有2個隊列：顧客隊列和事件隊列。
程序的邏輯如下：
1.初始化事件隊列，填充顧客到達(dá)事件；
2.處理事件隊列的頭部（總是為最早發(fā)生的事件），若為“顧客到達(dá)事件”，轉(zhuǎn)向處理“顧客到達(dá)事件”，若為“顧客離開事件”，轉(zhuǎn)向處理“顧客離開事件”；
3.循環(huán)進(jìn)行2，直到事件隊列為空或超出營業(yè)時間；
4.進(jìn)行清理工作。
事件處理
主流程
永遠(yuǎn)處理事件隊列的頭部――即最早發(fā)生的事件。
void Manager::run() { while (_event_queue.size() != 0) { _current_event = _event_queue.front(); if (_current_event->occur_time >= _total_serve_time)//超出營業(yè)時間 break; if(_customer_queue.size() == 0 && _event_queue.size() <= _service_num)//生成新的顧客到達(dá)事件 { generate_arrived_event(_generate_arrived_time); _current_event = _event_queue.front();//update current event, deal it with order } if (_current_event->event_type == EventType::ARRIVIED)//處理顧客到達(dá)事件 customer_arrived(); else if (_current_event->event_type == EventType::DEPARTURE)//處理顧客離開事件 customer_departure(); }} 生成顧客到達(dá)事件
有2種方法：
（1）一次性生成全部顧客到達(dá)事件
設(shè)定單位時間內(nèi)到達(dá)的顧客數(shù)量，生成銀行營業(yè)時間內(nèi)所有的到達(dá)事件，處理這些事件，直到事件隊列為空或是超過了銀行的營業(yè)時間。
void Manager::generate_arrived_event(int& current_time) {//生成單位時間內(nèi)的顧客到達(dá)事件并入隊，current_time是共享的 Event* event; int customer_per_minute = Random::uniform(RANDOM_PER_MINUTE);//單位時間內(nèi)隨機(jī)到達(dá)的顧客數(shù)量，至少為1例 while (customer_per_minute > 0) { event = new Event(current_time); _event_queue.enqueue(event); --customer_per_minute; } ++current_time; } _generate_arrived_time = 0; while(_generate_arrived_time < _total_serve_time) { //_total_serve_time是銀行的總營業(yè)時間 generate_arrived_event(_generate_arrived_time); } （2）分批生成顧客到達(dá)事件
僅在需要時生成顧客到達(dá)事件，因為顧客接受服務(wù)需要一定的時間，通常來說第1種方法生成的到達(dá)事件在達(dá)到銀行營業(yè)時間后不能全部處理完成，這就造成了時間和空間上的浪費。分批生成到達(dá)事件的實現(xiàn)是基于這樣的事實：如果顧客隊列為空且事件隊列的長度小于等于服務(wù)窗口的數(shù)量時，說明余下的事件將不能讓服務(wù)窗口滿載并產(chǎn)生等待服務(wù)的顧客，此時就需要生成新的顧客到達(dá)事件。
初始化事件隊列：
_generate_arrived_time = 0;//依舊是以時間順序生成顧客到達(dá)事件 while(_generate_arrived_time < INIT_ARRIVIED_EVENT_NUM) {//選擇合適的值，使最初生成的顧客到達(dá)事件略多于服務(wù)窗口數(shù)量，保證服務(wù)窗口滿載且有等待顧客即可 generate_arrived_event(_generate_arrived_time); } 判斷條件并生成到達(dá)事件：
if(_customer_queue.empty() && _event_queue.size() <= _service_num){ generate_arrived_event(_generate_arrived_time); _current_event = &_event_queue.top();//update current event, deal it with order} 由于顧客到達(dá)事件仍是以時間順序從0到營業(yè)時間結(jié)束來生成的，之所以能夠保證不會在處理了98分鐘時的顧客離開事件（可能是5分鐘時到達(dá)的顧客產(chǎn)生的）后再去處理新插入的10分鐘時的顧客到達(dá)事件，就是初始化事件隊列時選擇合適的INIT_ARRIVIED_EVENT_NUM的意義所在：時刻保證事件隊列的長度大于服務(wù)窗口的數(shù)量，新生成的顧客到達(dá)事件的時間若早于顧客離開事件的時間（以時間為順序生成顧客到達(dá)事件就保證了新生成的顧客到達(dá)事件的時間不小于事件隊列中已有的顧客到達(dá)事件，而顧客離開事件的時間是隨機(jī)的，若提前于新生成的顧客到事件處理，可能會失序）也能被正確處理。
生成顧客離開事件
顧客隊列頭部顧客接受服務(wù)并出隊，生成顧客離開事件并入隊事件隊列。顧客離開事件的發(fā)生時間 = 當(dāng)前時間 + 顧客接受服務(wù)的時長。
void Manager::generate_departure_event(int service_index, int current_time) { _services[service_index].serve_customer(*_customer_queue.front()); _services[service_index].set_busy();//服務(wù)窗口置為“忙” _services[service_index].set_service_start_time(current_time);//服務(wù)開始時間 _customer_queue.dequeue(); int duration = _services[service_index].get_customer_duration(); Event* event = new Event(current_time + duration, EventType::DEPARTURE, service_index);//生成顧客離開事件 _event_queue.enqueue(event);} 處理顧客到達(dá)事件
處理“顧客到達(dá)事件”的邏輯：
1.生成1個顧客，入隊顧客隊列；
2.出隊事件隊列；
3.若有空閑的服務(wù)窗口，則生成“顧客離開事件”。
下面是代碼：
void Manager::customer_arrived() { int idle_service_num = get_idle_service_index();//獲取空閑的服務(wù)窗口，返回-1說明未找到 int current_time = _current_event->occur_time; Customer* customer = new Customer(current_time);//顧客到達(dá)事件發(fā)生時間即為顧客到達(dá)時間， 顧客接受服務(wù)的時長隨機(jī) _customer_queue.enqueue(customer); _event_queue.dequeue(); if (idle_service_num != -1) generate_departure_event(idle_service_num, current_time);} 處理顧客離開事件
處理“顧客離開事件”的邏輯：
1.顧客所在服務(wù)窗口置為空閑，統(tǒng)計顧客信息；
2.出隊事件隊列；
3.若顧客隊列不為空且有空閑的服務(wù)窗口，生成“顧客離開事件”。
下面是代碼：
void Manager::customer_departure() { int current_time = _current_event->occur_time; int service_index = _current_event->service_index;//顧客離開的服務(wù)窗口 _customer_stay_time += current_time - _services[service_index].get_customer_arrive_time();//統(tǒng)計顧客在銀行的滯留時間 ++_total_served_customer_num;//接受服務(wù)的顧客數(shù)目加1 _services[service_index].set_idle(); _event_queue.dequeue(); if(_customer_queue.size() > 0) { service_index = get_idle_service_index();//有顧客離開，必然可以獲得1個空閑服務(wù)窗口，這里獲取最小序號的服務(wù)窗口 generate_departure_event(service_index, current_time); }} 清理工作：
1.尋找仍在接受服務(wù)的顧客并統(tǒng)計他們的信息；
2.釋放動態(tài)申請的內(nèi)存。
下面是代碼：
void Manager::end() { for (int i = 0; i < _service_num; i++) { if (!_services[i].is_idle()) {//統(tǒng)計正在接受服務(wù)的顧客的信息 int service_start_time = _services[i].get_service_start_time(); int arrive_time = _services[i].get_customer_arrive_time(); int duration = _services[i].get_customer_duration(); _customer_stay_time += service_start_time + duration - arrive_time; ++_total_served_customer_num; } } //釋放動態(tài)申請的內(nèi)存 _customer_queue.clear(); _event_queue.clear(); delete[] _services;} 關(guān)于隊列的說明
程序中使用的是自定義的隊列，根據(jù)需求，可以使用STL中的優(yōu)先隊列和隊列，前者用于事件隊列，后者用于顧客隊列。
優(yōu)先隊列的頭部總是優(yōu)先級最高的節(jié)點，對于事件來說，就是發(fā)生的時間越早，事件優(yōu)先級越高，所以這是一個最小堆――時間發(fā)生的時間最小（最早）的位于堆頂。這涉及到對Event類型的比較，使用STL的greater<Event>（需要重載operator>）或是自定義的函數(shù)對象來比較2個Event對象：
（1）重載operator>運算符
//聲明使用greater<Event>作為比較函數(shù)的優(yōu)先隊列std::priority_queue<Event, std::vector<Event>, std::greater<Event>> _event_queue; //event_queue.h#ifndef BANKQUEUE_EVENT_QUEUE_H#define BANKQUEUE_EVENT_QUEUE_H#include "random.h"enum class EventType : int { ARRIVIED, DEPARTURE};class Event { public: Event():occur_time(Random::uniform(RANDOM_PARAMETER)), event_type(EventType::ARRIVIED), service_index(-1), next(nullptr){} Event(int occur_time):occur_time(occur_time), event_type(EventType::ARRIVIED), service_index(-1), next(nullptr){} Event(int occur_time, EventType event_type, int service_index): occur_time(occur_time), event_type(event_type), service_index(service_index), next(nullptr) {} friend bool operator< (const Event& event1, const Event& event2);//模仿STL的實現(xiàn)，都是通過'<'來完成余下的比較操作符 friend bool operator> (const Event& event1, const Event& event2);//供`greater<Event>`使用 public: int occur_time; int service_index; EventType event_type; Event *next;};inline bool operator< (const Event& event1, const Event& event2) { return event1.occur_time < event2.occur_time;}inline bool operator> (const Event& event1, const Event& event2) { return event2 < event1;//通過'<'實現(xiàn)'>'的功能}#endif //BANKQUEUE_EVENT_QUEUE_H （2）比較直觀且簡單的做法是自定義用于比較的函數(shù)對象：
//聲明使用EventComp作為比較函數(shù)的優(yōu)先隊列std::priority_queue<Event, std::vector<Event>, EventComp> _event_queue; struct EventComp{ bool operator()(const Event& lhs, const Event& rhs) const { return lhs.occur_time > rhs.occur_time;//occur_time是公有的，若是私有的，則需要提供接口 }}; 可以在test.h中通過USE_SELF_DEFINE_QUEUE宏來切換2種隊列的使用。
事件隊列的順序
事件隊列要求隊首總是發(fā)生時間最早的事件，最小堆是非常好的選擇，通過前面介紹的STL優(yōu)先隊列可以輕松實現(xiàn)。自定義的隊列則使用的是蠻力法，在事件入隊時就進(jìn)行排序，保證隊列是以發(fā)生時間升序的，在隊列中元素較多時（如幾百個），效率是低于使用STL優(yōu)先隊列的方法的，這也是為何要分批生成顧客到達(dá)事件的原因之一：防止事件隊列的元素過多。
顧客隊列是不需要排序的，所以以模板特例化的方式實現(xiàn)了事件隊列的入隊方法：
template<>
void Queue<Event>::enqueue(Event* event) { Event *cur = _front, *prev = nullptr; while (cur != nullptr) { if (cur->occur_time < event->occur_time) { prev = cur; cur = cur->next; } else break; } if (prev == nullptr) { event->next = _front; _front = event; if (_rear == nullptr) _rear = event;//_rear is useless to Event queue } else { event->next = prev->next; prev->next = event; if (prev == _rear) _rear = event; } ++length;} 完整代碼在這里。
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持武林網(wǎng)。
新聞熱點
疑難解答
