16-用队列进行模拟
17.5 用队列进行模拟
经过测试，队列没问题。现在，我们用它来做一些有趣的事情。许多现实生活的情形都涉及队列。例如，在银行或超市的顾客队列、机场的飞机队列、多任务计算机系统中的任务队列等。我们可以用队列包来模拟这些情形。
假设Sigmund Landers在商业街设置了一个提供建议的摊位。顾客可以购买1分钟、2分钟或3分钟的建议。为确保交通畅通，商业街规定每个摊位前排队等待的顾客最多为10人（相当于程序中的最大队列长度）。假设顾客都是随机出现的，并且他们花在咨询上的时间也是随机选择的（1分钟、2分钟、3分钟）。那么Sigmund平均每小时要接待多少名顾客？每位顾客平均要花多长时间？排队等待的顾客平均有多少人？队列模拟能回答类似的问题。
首先，要确定在队列中放什么。可以根据顾客加入队列的时间和顾客咨询时花费的时间来描述每一位顾客。因此，可以这样定义 Item 类型。
typedef struct item
{
long arrive; /* 一位顾客加入队列的时间 */
int processtime; /* 该顾客咨询时花费的时间 */
} Item;要用队列包来处理这个结构，必须用 typedef 定义的 Item 替换上一个示例的 int 类型。这样做就不用担心队列的具体工作机制，可以集中精力分析实际问题，即模拟咨询Sigmund的顾客队列。
这里有一种方法，让时间以1分钟为单位递增。每递增1分钟，就检查是否有新顾客到来。如果有一位顾客且队列未满，将该顾客添加到队列中。这涉及把顾客到来的时间和顾客所需的咨询时间记录在 Item 类型的结构中，然后在队列中添加该项。然而，如果队列已满，就让这位顾客离开。为了做统计，要记录顾客的总数和被拒顾客（队列已满不能加入队列的人）的总数。
接下来，处理队列的首端。也就是说，如果队列不为空且前面的顾客没有在咨询Sigmund，则删除队列首端的项。记住，该项中存储着这位顾客加入队列的时间，把该时间与当前时间作比较，就可得出该顾客在队列中等待的时间。该项还存储着这位顾客需要咨询的分钟数，即还要咨询Sigmund多长时间。因此还要用一个变量存储这个时长。如果Sigmund正忙，则不用让任何人离开队列。尽管如此，记录等待时间的变量应该递减1。
核心代码类似下面这样，每一轮迭代对应1分钟的行为：
for (cycle = 0; cycle < cyclelimit; cycle++)
{
if (newcustomer(min_per_cust))
{
if (QueueIsFull(&line))
turnaways++;
else
{
customers++;
temp = customertime(cycle);
EnQueue(temp, &line);
}
}
if (wait_time <= 0 && !QueueIsEmpty(&line))
{
DeQueue(&temp, &line);
wait_time = temp.processtime;
line_wait += cycle - temp.arrive;
served++;
}
if (wait_time > 0)
wait_time––;
sum_line += QueueItemCount(&line);
}注意，时间的表示比较粗糙（1分钟），所以一小时最多60位顾客。下面是一些变量和函数的含义。
min_per_cus是顾客到达的平均间隔时间。newcustomer()使用C的rand()函数确定在特定时间内是否有顾客到来。turnaways是被拒绝的顾客数量。customers是加入队列的顾客数量。temp是表示新顾客的Item类型变量。customertime()设置temp结构中的arrive和processtime成员。wait_time是Sigmund完成当前顾客的咨询还需多长时间。line_wait是到目前为止队列中所有顾客的等待总时间。served是咨询过Sigmund的顾客数量。sum_line是到目前为止统计的队列长度。
如果到处都是 malloc() 、 free() 和指向节点的指针，整个程序代码会非常混乱和晦涩。队列包让你把注意力集中在模拟问题上，而不是编程细节上。
程序清单17.9演示了模拟商业街咨询摊位队列的完整代码。根据第12章介绍的方法，使用标准函数 rand() 、 srand() 和 time() 来产生随机数。另外要特别注意，必须用下面的代码更新 queue.h 中的 Item ，该程序才能正常工作：
typedef struct item
{
long arrive; //一位顾客加入队列的时间
int processtime; //该顾客咨询时花费的时间
} Item;记住，还要把 mall.c 和 queue.c 一起链接。
程序清单17.9 mall.c 程序
// mall.c -- 使用 Queue 接口
// 和 queue.c 一起编译
#include <stdio.h>
#include <stdlib.h> // 提供 rand() 和 srand() 的原型
#include <time.h> // 提供 time() 的原型
#include "queue.h" // 更改 Item 的 typedef
#define MIN_PER_HR 60.0
bool newcustomer(double x); // 是否有新顾客到来？
Item customertime(long when); // 设置顾客参数
int main(void)
{
Queue line;
Item temp; // 新的顾客数据
int hours; // 模拟的小时数
int perhour; // 每小时平均多少位顾客
long cycle, cyclelimit; // 循环计数器、计数器的上限
long turnaways = 0; // 因队列已满被拒的顾客数量
long customers = 0; // 加入队列的顾客数量
long served = 0; // 在模拟期间咨询过Sigmund的顾客数量
long sum_line = 0; // 累计的队列总长
int wait_time = 0; // 从当前到Sigmund空闲所需的时间
double min_per_cust; // 顾客到来的平均时间
long line_wait = 0; // 队列累计的等待时间
InitializeQueue(&line);
srand((unsigned int) time(0)); // rand() 随机初始化
puts("Case Study: Sigmund Lander's Advice Booth");
puts("Enter the number of simulation hours:");
scanf("%d", &hours);
cyclelimit = MIN_PER_HR * hours;
puts("Enter the average number of customers per hour:");
scanf("%d", &perhour);
min_per_cust = MIN_PER_HR / perhour;
for (cycle = 0; cycle < cyclelimit; cycle++)
{
if (newcustomer(min_per_cust))
{
if (QueueIsFull(&line))
turnaways++;
else
{
customers++;
temp = customertime(cycle);
EnQueue(temp, &line);
}
}
if (wait_time <= 0 && !QueueIsEmpty(&line))
{
DeQueue(&temp, &line);
wait_time = temp.processtime;
line_wait += cycle - temp.arrive;
served++;
}
if (wait_time > 0)
wait_time--;
sum_line += QueueItemCount(&line);
}
if (customers > 0)
{
printf("customers accepted: %ld\n", customers);
printf(" customers served: %ld\n", served);
printf(" turnaways: %ld\n", turnaways);
printf("average queue size: %.2f\n",
(double) sum_line / cyclelimit);
printf(" average wait time: %.2f minutes\n",
(double) line_wait / served);
}
else
puts("No customers!");
EmptyTheQueue(&line);
puts("Bye!");
return 0;
}
// x是顾客到来的平均时间（单位：分钟）
// 如果1分钟内有顾客到来，则返回true
bool newcustomer(double x)
{
if (rand() * x / RAND_MAX < 1)
return true;
else
return false;
}
// when是顾客到来的时间
// 该函数返回一个Item结构，该顾客到达的时间设置为when，
// 咨询时间设置为1～3的随机值
Item customertime(long when)
{
Item cust;
cust.processtime = rand() % 3 + 1;
cust.arrive = when;
return cust;
}该程序允许用户指定模拟运行的小时数和每小时平均有多少位顾客。模拟时间较长得出的值较为平均，模拟时间较短得出的值随时间的变化而随机变化。下面的运行示例解释了这一点（先保持每小时的顾客平均数量不变）。注意，在模拟80小时和800小时的情况下，平均队伍长度和等待时间基本相同。但是，在模拟1小时的情况下这两个量差别很大，而且与长时间模拟的情况差别也很大。这是因为小数量的统计样本往往更容易受相对变化的影响。
Case Study: Sigmund Lander's Advice Booth
Enter the number of simulation hours:
80
Enter the average number of customers per hour:
20
customers accepted: 1633
customers served: 1633
turnaways: 0
average queue size: 0.46
average wait time: 1.35 minutes
Case Study: Sigmund Lander's Advice Booth
Enter the number of simulation hours:
800
Enter the average number of customers per hour:
20
customers accepted: 16020
customers served: 16019
turnaways: 0
average queue size: 0.44
average wait time: 1.32 minutes
Case Study: Sigmund Lander's Advice Booth
Enter the number of simulation hours:
1
Enter the average number of customers per hour:
20
customers accepted: 20
customers served: 20
turnaways: 0
average queue size: 0.23
average wait time: 0.70 minutes
Case Study: Sigmund Lander's Advice Booth
Enter the number of simulation hours:
1
Enter the average number of customers per hour:
20
customers accepted: 22
customers served: 22
turnaways: 0
average queue size: 0.75
average wait time: 2.05 minutes
然后保持模拟的时间不变，改变每小时的顾客平均数量：
Case Study: Sigmund Lander's Advice Booth
Enter the number of simulation hours:
80
Enter the average number of customers per hour:
25
customers accepted: 1960
customers served: 1959
turnaways: 3
average queue size: 1.43
average wait time: 3.50 minutes
Case Study: Sigmund Lander's Advice Booth
Enter the number of simulation hours:
80
Enter the average number of customers per hour:
30
customers accepted: 2376
customers served: 2373
turnaways: 94
average queue size: 5.85
average wait time: 11.83 minutes
注意，随着每小时顾客平均数量的增加，顾客的平均等待时间迅速增加。在每小时20位顾客（80小时模拟时间）的情况下，每位顾客的平均等待时间是1.35分钟；在每小时25位顾客的情况下，平均等待时间增加至3.50分钟；在每小时30位顾客的情况下，该数值攀升至11.83分钟。而且，这3种情况下被拒顾客分别从0位增加至3位最后陡增至94位。Sigmund可以根据程序模拟的结果决定是否要增加一个摊位。