C++數據結構學習之隊列的應用

在學習C++隊列的運用中，我看了兩本書，都是講解隊列應用的，而且都是銀行營業模擬。細比較，這兩本書模擬的銀行營業的方式還是不同的。老式的營業模式，現在的很多地方還是這種營業模式——幾個窗口同時排隊。這種方式其實不太合理，經常會出現先來的還沒有後來的先辦理業務(常常前面一個人磨磨蹭蹭，別的隊越來越短，讓你恨不得把前面那人干掉)。另一種營業模式——掛牌的營業方式，每個來到的顧客發一個號碼，如果哪個櫃台空閒了，就叫號碼最靠前的顧客來辦理業務；如果同時幾個櫃台空閒，就按照一種法則來決定這幾個櫃台叫號的順序(最簡單的是按櫃台號碼順序)。這樣，就能保證顧客按照先來後到的順序接受服務——因為大家排在一個隊裡。這樣的營業模式我在北京的西直門工商銀行見過，應該說這是比較合理的一種營業模式。

我按照實際情況模擬，實現如下：

#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 << "輸入模擬參數" << endl;  
　cout << "櫃台數量："; cin >> tellerNum;  
　cout << "營業時間："; cin >> simuTime;  
　cout << "兩個顧客來到的最小間隔時間："; cin >> arrivalLow;  
　cout << "兩個顧客來到的最大間隔時間："; cin >> arrivalHigh;  
　cout << "櫃台服務最短時間："; cin >> serviceLow;  
　cout << "櫃台服務最長時間："; 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 << "模擬參數" << endl;  
　cout << "櫃台數量： " << tellerNum << "\t營業時間：" << simuTime << endl;  
　cout << "兩個顧客來到的最小間隔時間：" << arrivalLow << endl;  
　cout << "兩個顧客來到的最大間隔時間：" << arrivalHigh << endl;;  
　cout << "櫃台服務最短時間：" << serviceLow << endl;  
　cout << "櫃台服務最長時間：" << serviceHigh << endl;  
}  
 
void PrintResult()  
{  
　int tSN = 0;  
　long tST = 0;  
　cout << endl;  
　cout << "－－－－－－－－－－－－－模擬結果－－－－－－－－－－－－－－－－－－－";  
　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 

幾點說明

1、Run()的過程是這樣的：curTime是時鐘，從開始營業計時，自然流逝到停止營業。當顧客到的事件發生時(顧客到時間等於當前時間，小於判定是因為個別時候顧客同時到達——輸入arrivalLow=0的情況，而在同一時間，只給一個顧客發號碼)，給這個顧客發號碼(用顧客到時間標示這個顧客，入隊，來到顧客數增1)。當櫃台服務完畢時(櫃台服務完時間等於當前時間)，該櫃台服務人數增1，服務時間累加，顧客離開事件發生，下一個顧客到該櫃台。因為櫃台開始都是空閒的，所以實際代碼和這個有點出入。最後，停止營業的時候，停止發號碼，還在接受服務的顧客繼續到服務完，其他還在排隊的就散伙了。

2、模擬結果分別是：各個櫃台的服務人數、服務時間、平均服務時間，總的服務人數、服務時間、平均服務時間，來的顧客總數、沒被服務的數目(來的太晚了)、接受服務顧客總等待時間、平均等待時間。

3、這個算法效率是比較低的，實際上可以不用隊列完成這個模擬(用顧客到時間推動當前時鐘，櫃台直接公告服務完成時間)，但這樣就和實際情況有很大差別了——出納員沒等看見人就知道什麼時候完?雖然結果是一樣的，但是理解起來很莫名其妙，尤其是作為教學目的講解的時候。當然了，實際中為了提高模擬效率，本文的這個算法是不值得提倡的。

4、注釋掉的#define PRINTPROCESS，去掉注釋符後，在運行模擬的時候，能打印出每個時刻櫃台的服務情況(第幾個顧客，顧客到達時間，接受服務時間)，但只限4個櫃台以下，多了的話屏幕就滿了(格式就亂了)。

這是數據結構中第一個實際應用的例子，而且也有現實意義。你可以看出各個櫃台在不同的業務密度下的工作強度(要麼給哪個櫃台出納員發獎金，要麼輪換櫃台)，各種情況下顧客的等待時間(人都是輪到自己就不著急了)，還有各種情況下設立幾個櫃台合理(很少的空閒時間，很短的等待時間，幾乎為零的未服務人數)。例如這樣：

for (int i = 1; i < 16; i++)  
{  
　Simulation a(i,240,1,4,8,15);  
　a.Run();  
}  

你模擬一下就會得出，在不太繁忙的銀行，4～5個櫃台是合適的——現在的銀行大部分都是這樣的。