我看的兩本教科書（《數據結構（C語言版）》還有這本黃皮書）都是以這個講解隊列應用的，而且都是銀行營業模擬（太沒新意了）。細比較，這兩本書模擬的銀行營業的方式還是不同的。1997版的《數據結構（C語言版）》的銀行還是老式的營業模式（畢竟是1997年的事了），現在的很多地方還是這種營業模式——幾個窗口同時排隊。這種方式其實不太合理，經常會出現先來的還沒有后來的先辦理業務（常常前面一個人磨磨蹭蹭，別的隊越來越短，讓你恨不得把前面那人干掉）。1999版的這本黃皮書的銀行改成了一種掛牌的營業方式，每個來到的顧客發一個號碼，如果哪個柜臺空閑了，就叫號碼最靠前的顧客來辦理業務；如果同時幾個柜臺空閑，就按照一種法則來決定這幾個柜臺叫號的順序（最簡單的是按柜臺號碼順序）。這樣，就能保證顧客按照先來后到的順序接受服務——因為大家排在一個隊里。這樣的營業模式我在北京的西直門工商銀行見過，應該說這是比較合理的一種營業模式。不過，在本文中最重要的是，這樣的營業模式比較好模擬（一個隊列總比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 << "輸入模擬參數" << 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 << " TELLER " << 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 << ' ' << customerNum + 1 << '(' << customer.GetFront() << ',' << t << ')';
#endif
CustomerDeparture();
tellers[i].totalCustomerCount++;
tellers[i].totalServiceTime += t;
tellers[i].finishServiceTime += t;
}
#ifdef PRINTPROCESS
else cout << " ";
#endif
}
#ifdef PRINTPROCESS
cout << endl;
#endif
}
PrintResult();
}
void PtintSimuPara()
{
cout << endl << "模擬參數" << endl;
cout << "柜臺數量： " << tellerNum << " 營業時間：" << 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 ServiceNum ServiceTime AverageTime" << endl;
for (int i = 1; i <= tellerNum; i++)
{
cout << "TELLER " << i;
cout << ' ' << tellers[i].totalCustomerCount << " "; tSN += tellers[i].totalCustomerCount;
cout << ' ' << tellers[i].totalServiceTime << " "; tST += (long)tellers[i].totalServiceTime;
cout << ' ';
if (tellers[i].totalCustomerCount)
cout << (float)tellers[i].totalServiceTime/(float)tellers[i].totalCustomerCount;
else cout << 0;
cout << " " << endl;
}
cout << "TOTAL " << tSN << " " << tST << " ";
if (tSN) cout << (float)tST/(float)tSN; else cout << 0;
cout << " " << endl;
cout << "Customer Number: " << customerNum << " no Service: " << customerNum - tSN << endl;
cout << "Customer WaitTime: " << customerTime << " AvgWaitTime: ";
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
幾點說明
l Run()的過程是這樣的：curTime是時鐘，從開始營業計時，自然流逝到停止營業。當顧客到的事件發生時（顧客到時間等于當前時間，小于判定是因為個別時候顧客同時到達——輸入arrivalLow＝0的情況，而在同一時間，只給一個顧客發號碼），給這個顧客發號碼（用顧客到時間標示這個顧客，入隊，來到顧客數增1）。當柜臺服務完畢時（柜臺服務完時間等于當前時間），該柜臺服務人數增1，服務時間累加，顧客離開事件發生，下一個顧客到該柜臺。因為柜臺開始都是空閑的，所以實際代碼和這個有點出入。最后，停止營業的時候，停止發號碼，還在接受服務的顧客繼續到服務完，其他還在排隊的就散伙了。
l 模擬結果分別是：各個柜臺的服務人數、服務時間、平均服務時間，總的服務人數、服務時間、平均服務時間，來的顧客總數、沒被服務的數目（來的太晚了）、接受服務顧客總等待時間、平均等待時間。
l 這個算法效率是比較低的，實際上可以不用隊列完成這個模擬（用顧客到時間推動當前時鐘，柜臺直接公告服務完成時間），但這樣就和實際情況有很大差別了——出納員沒等看見人就知道什么時候完？雖然結果是一樣的，但是理解起來很莫名其妙，尤其是作為教學目的講解的時候。當然了，實際中為了提高模擬效率，本文的這個算法是不值得提倡的。
l 注釋掉的#define PRINTPROCESS，去掉注釋符后，在運行模擬的時候，能打印出每個時刻柜臺的服務情況（第幾個顧客，顧客到達時間，接受服務時間），但只限4個柜臺以下，多了的話屏幕就滿了（格式就亂了）。
【后記】本來我沒打算寫這篇，后來，當我開始實現模擬的時候，竟欲罷不能了。這是數據結構這本書中第一個實際應用的例子，而且也有現實意義。你可以看出各個柜臺在不同的業務密度下的工作強度（要么給哪個柜臺出納員發獎金，要么輪換柜臺），各種情況下顧客的等待時間（人都是輪到自己就不著急了），還有各種情況下設立幾個柜臺合理（很少的空閑時間，很短的等待時間，幾乎為零的未服務人數）。例如這樣：
for (int i = 1; i < 16; i++)
{
Simulation a(i,240,1,4,8,15);
a.Run();
}
你模擬一下就會得出，在不太繁忙的銀行，4～5個柜臺是合適的——現在的銀行大部分都是這樣的。