C++數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)之隊(duì)列的應(yīng)用
在學(xué)習(xí)C++隊(duì)列的運(yùn)用中，我看了兩本書(shū)，都是講解隊(duì)列應(yīng)用的，而且都是銀行營(yíng)業(yè)模擬。細(xì)比較，這兩本書(shū)模擬的銀行營(yíng)業(yè)的方式還是不同的。老式的營(yíng)業(yè)模式，現(xiàn)在的很多地方還是這種營(yíng)業(yè)模式——幾個(gè)窗口同時(shí)排隊(duì)。這種方式其實(shí)不太合理，經(jīng)常會(huì)出現(xiàn)先來(lái)的還沒(méi)有后來(lái)的先辦理業(yè)務(wù)(常常前面一個(gè)人磨磨蹭蹭，別的隊(duì)越來(lái)越短，讓你恨不得把前面那人干掉)。另一種營(yíng)業(yè)模式——掛牌的營(yíng)業(yè)方式，每個(gè)來(lái)到的顧客發(fā)一個(gè)號(hào)碼，如果哪個(gè)柜臺(tái)空閑了，就叫號(hào)碼最靠前的顧客來(lái)辦理業(yè)務(wù)；如果同時(shí)幾個(gè)柜臺(tái)空閑，就按照一種法則來(lái)決定這幾個(gè)柜臺(tái)叫號(hào)的順序(最簡(jiǎn)單的是按柜臺(tái)號(hào)碼順序)。這樣，就能保證顧客按照先來(lái)后到的順序接受服務(wù)——因?yàn)榇蠹遗旁谝粋€(gè)隊(duì)里。這樣的營(yíng)業(yè)模式我在北京的西直門(mén)工商銀行見(jiàn)過(guò)，應(yīng)該說(shuō)這是比較合理的一種營(yíng)業(yè)模式。
我按照實(shí)際情況模擬，實(shí)現(xiàn)如下：
- #ifndef Simulation_H
- #define Simulation_H
- #include <iostream.h>
- #include <stdlib.h>
- #include <time.h>
- class Teller
- {
- public:
- int totalCustomerCount;
- int totalServiceTime;
- int finishServiceTime;
- Teller() :totalCustomerCount(0), totalServiceTime(0),
- finishServiceTime(0) {}
- };
- //#define PRINTPROCESS
- class Simulation
- {
- public:
- Simulation()
- {
- cout << endl << "輸入模擬參數(shù)" << endl;
- cout << "柜臺(tái)數(shù)量："; cin >> tellerNum;
- cout << "營(yíng)業(yè)時(shí)間："; cin >> simuTime;
- cout << "兩個(gè)顧客來(lái)到的最小間隔時(shí)間："; cin >> arrivalLow;
- cout << "兩個(gè)顧客來(lái)到的最大間隔時(shí)間："; cin >> arrivalHigh;
- cout << "柜臺(tái)服務(wù)最短時(shí)間："; cin >> serviceLow;
- cout << "柜臺(tái)服務(wù)最長(zhǎng)時(shí)間："; cin >> serviceHigh;
- arrivalRange = arrivalHigh - arrivalLow + 1;
- serviceRange = serviceHigh - serviceLow + 1;
- srand((unsigned)time(NULL));
- }
- Simulation(int tellerNum, int simuTime, int arrivalLow, int arrivalHigh, int serviceLow, int serviceHigh)
- : tellerNum(tellerNum), simuTime(simuTime), arrivalLow(arrivalLow), arrivalHigh(arrivalHigh),
- serviceLow(serviceLow), serviceHigh(serviceHigh),
- arrivalRange(arrivalHigh - arrivalLow + 1), serviceRange(serviceHigh - serviceLow + 1)
- { srand((unsigned)time(NULL)); }
- void Initialize()
- {
- curTime = nextTime = 0;
- customerNum = customerTime = 0;
- for (int i = 1; i <= tellerNum; i++)
- {
- tellers[i].totalCustomerCount = 0;
- tellers[i].totalServiceTime = 0;
- tellers[i].finishServiceTime = 0;
- }
- customer.MakeEmpty();
- }
- void Run()
- {
- Initialize();
- NextArrived();
- #ifdef PRINTPROCESS
- cout << endl;
- cout << "tellerID";
- for (int k = 1; k <= tellerNum; k++) cout << "\tTELLER " << k;
- cout << endl;
- #endif
- for (curTime = 0; curTime <= simuTime; curTime++)
- {
- if (curTime >= nextTime)
- {
- CustomerArrived();
- NextArrived();
- }
- #ifdef PRINTPROCESS
- cout << "Time: " << curTime << " ";
- #endif
- for (int i = 1; i <= tellerNum; i++)
- {
- if (tellers[i].finishServiceTime < curTime) tellers[i].finishServiceTime = curTime;
- if (tellers[i].finishServiceTime == curTime && !customer.IsEmpty())
- {
- int t = NextService();
- #ifdef PRINTPROCESS
- cout << '\t' << customerNum + 1 << '(' << customer.GetFront() << ',' << t << ')';
- #endif
- CustomerDeparture();
- tellers[i].totalCustomerCount++;
- tellers[i].totalServiceTime += t;
- tellers[i].finishServiceTime += t;
- }
- #ifdef PRINTPROCESS
- else cout << "\t ";
- #endif
- }
- #ifdef PRINTPROCESS
- cout << endl;
- #endif
- }
- PrintResult();
- }
- void PtintSimuPara()
- {
- cout << endl << "模擬參數(shù)" << endl;
- cout << "柜臺(tái)數(shù)量： " << tellerNum << "\t營(yíng)業(yè)時(shí)間：" << simuTime << endl;
- cout << "兩個(gè)顧客來(lái)到的最小間隔時(shí)間：" << arrivalLow << endl;
- cout << "兩個(gè)顧客來(lái)到的最大間隔時(shí)間：" << arrivalHigh << endl;;
- cout << "柜臺(tái)服務(wù)最短時(shí)間：" << serviceLow << endl;
- cout << "柜臺(tái)服務(wù)最長(zhǎng)時(shí)間：" << serviceHigh << endl;
- }
- void PrintResult()
- {
- int tSN = 0;
- long tST = 0;
- cout << endl;
- cout << "－－－－－－－－－－－－－模擬結(jié)果－－－－－－－－－－－－－－－－－－－";
- cout << endl << "tellerID\tServiceNum\tServiceTime\tAverageTime" << endl;
- for (int i = 1; i <= tellerNum; i++)
- {
- cout << "TELLER " << i;
- cout << '\t' << tellers[i].totalCustomerCount << " "; tSN += tellers[i].totalCustomerCount;
- cout << '\t' << tellers[i].totalServiceTime << " "; tST += (long)tellers[i].totalServiceTime;
- cout << '\t';
- if (tellers[i].totalCustomerCount)
- cout << (float)tellers[i].totalServiceTime/(float)tellers[i].totalCustomerCount;
- else cout << 0;
- cout << " " << endl;
- }
- cout << "TOTAL \t" << tSN << " \t" << tST << " \t";
- if (tSN) cout << (float)tST/(float)tSN; else cout << 0;
- cout << " " << endl;
- cout << "Customer Number:\t" << customerNum << "\tno Service:\t" << customerNum - tSN << endl;
- cout << "Customer WaitTime:\t" << customerTime << "\tAvgWaitTime:\t";
- if (tSN) cout << (float)customerTime/(float)tSN; else cout << 0;
- cout << endl;
- }
- private:
- int tellerNum;
- int simuTime;
- int curTime, nextTime;
- int customerNum;
- long customerTime;
- int arrivalLow, arrivalHigh, arrivalRange;
- int serviceLow, serviceHigh, serviceRange;
- Teller tellers[21];
- Queue<int> customer;
- void NextArrived()
- {
- nextTime += arrivalLow + rand() % arrivalRange;
- }
- int NextService()
- {
- return serviceLow + rand() % serviceRange;
- }
- void CustomerArrived()
- {
- customerNum++;
- customer.EnQueue(nextTime);
- }
- void CustomerDeparture()
- {
- customerTime += (long)curTime - (long)customer.DeQueue();
- }
- };
- #endif
幾點(diǎn)說(shuō)明
1、Run()的過(guò)程是這樣的：curTime是時(shí)鐘，從開(kāi)始營(yíng)業(yè)計(jì)時(shí)，自然流逝到停止?fàn)I業(yè)。當(dāng)顧客到的事件發(fā)生時(shí)(顧客到時(shí)間等于當(dāng)前時(shí)間，小于判定是因?yàn)閭€(gè)別時(shí)候顧客同時(shí)到達(dá)——輸入arrivalLow=0的情況，而在同一時(shí)間，只給一個(gè)顧客發(fā)號(hào)碼)，給這個(gè)顧客發(fā)號(hào)碼(用顧客到時(shí)間標(biāo)示這個(gè)顧客，入隊(duì)，來(lái)到顧客數(shù)增1)。當(dāng)柜臺(tái)服務(wù)完畢時(shí)(柜臺(tái)服務(wù)完時(shí)間等于當(dāng)前時(shí)間)，該柜臺(tái)服務(wù)人數(shù)增1，服務(wù)時(shí)間累加，顧客離開(kāi)事件發(fā)生，下一個(gè)顧客到該柜臺(tái)。因?yàn)楣衽_(tái)開(kāi)始都是空閑的，所以實(shí)際代碼和這個(gè)有點(diǎn)出入。最后，停止?fàn)I業(yè)的時(shí)候，停止發(fā)號(hào)碼，還在接受服務(wù)的顧客繼續(xù)到服務(wù)完，其他還在排隊(duì)的就散伙了。
2、模擬結(jié)果分別是：各個(gè)柜臺(tái)的服務(wù)人數(shù)、服務(wù)時(shí)間、平均服務(wù)時(shí)間，總的服務(wù)人數(shù)、服務(wù)時(shí)間、平均服務(wù)時(shí)間，來(lái)的顧客總數(shù)、沒(méi)被服務(wù)的數(shù)目(來(lái)的太晚了)、接受服務(wù)顧客總等待時(shí)間、平均等待時(shí)間。
3、這個(gè)算法效率是比較低的，實(shí)際上可以不用隊(duì)列完成這個(gè)模擬(用顧客到時(shí)間推動(dòng)當(dāng)前時(shí)鐘，柜臺(tái)直接公告服務(wù)完成時(shí)間)，但這樣就和實(shí)際情況有很大差別了——出納員沒(méi)等看見(jiàn)人就知道什么時(shí)候完?雖然結(jié)果是一樣的，但是理解起來(lái)很莫名其妙，尤其是作為教學(xué)目的講解的時(shí)候。當(dāng)然了，實(shí)際中為了提高模擬效率，本文的這個(gè)算法是不值得提倡的。
4、注釋掉的#define PRINTPROCESS，去掉注釋符后，在運(yùn)行模擬的時(shí)候，能打印出每個(gè)時(shí)刻柜臺(tái)的服務(wù)情況(第幾個(gè)顧客，顧客到達(dá)時(shí)間，接受服務(wù)時(shí)間)，但只限4個(gè)柜臺(tái)以下，多了的話(huà)屏幕就滿(mǎn)了(格式就亂了)。
這是數(shù)據(jù)結(jié)構(gòu)中第一個(gè)實(shí)際應(yīng)用的例子，而且也有現(xiàn)實(shí)意義。你可以看出各個(gè)柜臺(tái)在不同的業(yè)務(wù)密度下的工作強(qiáng)度(要么給哪個(gè)柜臺(tái)出納員發(fā)獎(jiǎng)金，要么輪換柜臺(tái))，各種情況下顧客的等待時(shí)間(人都是輪到自己就不著急了)，還有各種情況下設(shè)立幾個(gè)柜臺(tái)合理(很少的空閑時(shí)間，很短的等待時(shí)間，幾乎為零的未服務(wù)人數(shù))。例如這樣：
- for (int i = 1; i < 16; i++)
- {
- Simulation a(i,240,1,4,8,15);
- a.Run();
- }
你模擬一下就會(huì)得出，在不太繁忙的銀行，4～5個(gè)柜臺(tái)是合適的——現(xiàn)在的銀行大部分都是這樣的。
【編輯推薦】
