看的两本教科书（《数据结构（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 << "\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 几点说明 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个柜台是合适的——现在的银行大部分都是这样的。

评论