STL实践项目之用queue模拟超市结账环节

前面章节介绍了 queue 容器适配器的具有用法，本节将利用 queue 模拟超市中结账环节运转的程序。

在超市营业过程中，结账队列的长度是超市运转的关键因素。它会影响超市可容纳的顾客数，因为太长的队伍会使顾客感到气馁，从而放弃排队，这和医院可用病床数会严重影响应急处理设施的运转，是同样的道理。

首先，我们要在头文件 Customer.h 中定义一个类来模拟顾客：

#ifndef CUSTOMER_H
#define CUSTOMER_H

class Customer
{
protected:
    size_t service_t {}; //顾客结账需要的时间
public:
    explicit Customer(size_t st = 10) :service_t {st}{}

    //模拟随着时间的变化，顾客结账所需时间也会减短
    Customer& time_decrement()
    {
        if (service_t > 0)
            --service_t;
        return *this;
    }
    bool done() const { return service_t == 0; }
};
#endif

这里只有一个成员变量 service_t，用来记录顾客结账需要的时间。每个顾客的结账时间都不同。每过一分钟，会调用一次 time_decrement() 函数，这个函数会减少 service_t 的值，它可以反映顾客结账所花费的时间。当 service_t 的值为 0 时，成员函数 done() 返回 true。

超市的每个结账柜台都有一队排队等待的顾客。Checkout.h 中定义的 Checkout 类如下：

#ifndef CHECKOUT_H
#define CHECKOUT_H
#include <queue> // For queue container
#include "Customer.h"

class Checkout
{
private:
    std::queue<Customer> customers; //该队列等到结账的顾客数量
public:
    void add(const Customer& customer) { customers.push(customer); }
    size_t qlength() const { return customers.size(); }
   
    void time_increment()
    {
        if (!customers.empty())
        { 
            //有顾客正在等待结账，如果顾客结账了，就出队列
            if (customers.front().time_decrement().done())
                customers.pop(); 
        }
    }
    bool operator<(const Checkout& other) const { return qlength() < other.qlength(); }
    bool operator>(const Checkout& other) const { return qlength() > other.qlength(); }
};
#endif

可以看到，queue 容器是 Checkout 唯一的成员变量，用来保存等待结账的 Customer 对象。成员函数 add() 可以向队列中添加新顾客。只能处理队列中的第一个元素。 每过一分钟，调用一次 Checkout 对象的成员函数 time_increment(}，它会调用第一个 Customer 对象的成员函数 time_decrement() 来减少剩余的等待时间，然后再调用成员函数 done()。如果 done() 返回 true，表明顾客结账完成，因此把他从队列中移除。Checkout 对象的比较运算符可以比较队列的长度。

为了模拟超市结账，我们需要有随机数生成的功能。因此打算使用 <random> 头文件中的一个非常简单的工具，但不打算深入解释它。我们会在教程后面的章节深入探讨 random 头文件中的内容。程序使用了一个 uniform_int_distribution() 类型的实例。顾名思义，它定义的整数值在最大值和最小值之间均匀分布。在均匀分布中，所有这个范围内的值都可能相等。可以在 10 和 100 之间定义如下分布：

std::uniform_int_distribution<> d {10, 100};

这里只定义了分布对象 d，它指定了整数值分布的范围。为了获取这个范围内的随机数，我们需要使用一个随机数生成器，然后把它作为参数传给 d 的调用运算符，从而返回一个随机整数。 random 头文件中定义了几种随机数生成器。这里我们使用最简单的一个，可以按如下方式定义：

std::random_device random_number_engine;

为了在 d 分布范围内生成随机数，我们可以这样写：

auto value = d(random_number_engine);

value 的值在 d 分布范围内。

完整模拟器的源文件如下：

#include <iostream> // For standard streams
#include <iomanip>  // For stream manipulators
#include <vector>   // For vector container
#include <string>   // For string class
#include <numeric>  // For accumulate()
#include <algorithm> // For min_element & max_element
#include <random> // For random number generation
#include "Customer.h"
#include "Checkout.h"

using std::string;
using distribution = std::uniform_int_distribution<>;

// 以横向柱形图的方式输出每个服务时间出现的次数
void histogram(const std::vector<int>& v, int min)
{
    string bar (60, '*');                       
    for (size_t i {}; i < v.size(); ++i)
    {
        std::cout << std::setw(3) << i+min << " "    //结账等待时间为 index + min
        << std::setw(4) << v[i] << " "             //输出出现的次数
        << bar.substr(0, v[i])                     
        << (v[i] > static_cast<int>(bar.size()) ? "...": "")
        << std::endl;
    }
}

int main()
{
    std::random_device random_n;

    //设置最大和最小的结账时间，以分钟为单位
    int service_t_min {2}, service_t_max {15};
    distribution service_t_d {service_t_min, service_t_max};

    //设置在超市开业时顾客的人数
    int min_customers {15}, max_customers {20};
    distribution n_1st_customers_d {min_customers, max_customers};

    // 设置顾客到达的最大和最小的时间间隔
    int min_arr_interval {1}, max_arr_interval {5};
    distribution arrival_interval_d {min_arr_interval, max_arr_interval};

    size_t n_checkouts {};
    std::cout << "输入超市中结账柜台的数量：";
    std::cin >> n_checkouts;
    if (!n_checkouts)
    {
        std::cout << "结账柜台的数量必须大于 0，这里将默认设置为 1" << std::endl;
        n_checkouts = 1;
    }

    std::vector<Checkout> checkouts {n_checkouts};
    std::vector<int> service_times(service_t_max-service_t_min+1);

    //等待超市营业的顾客人数
    int count {n_1st_customers_d(random_n)};
    std::cout << "等待超市营业的顾客人数：" << count << std::endl;
    int added {};
    int service_t {};
    while (added++ < count)
    {
        service_t = service_t_d(random_n);
        std::min_element(std::begin(checkouts), std::end(checkouts))->add(Customer(service_t));
        ++service_times[service_t - service_t_min];
    }

    size_t time {};
    const size_t total_time {600};                 // 设置超市持续营业的时间
    size_t longest_q {};                           // 等待结账最长队列的长度

    // 新顾客到达的时间
    int new_cust_interval {arrival_interval_d(random_n)};

    //模拟超市运转的过程
    while (time < total_time)                      
    {
        ++time; //时间增长

        // 新顾客到达
        if (--new_cust_interval == 0)
        {
            service_t = service_t_d(random_n);         // 设置顾客结账所需要的时间
            std::min_element(std::begin(checkouts), std::end(checkouts))->add(Customer(service_t));
            ++service_times[service_t - service_t_min];  // 记录结账需要等待的时间

            //记录最长队列的长度
            for (auto & checkout : checkouts)
                longest_q = std::max(longest_q, checkout.qlength());

            new_cust_interval = arrival_interval_d(random_n);
        }
        // 更新每个队列中第一个顾客的结账时间
        for (auto & checkout : checkouts)
            checkout.time_increment();
    }

    std::cout << "最大的队列长度为：" << longest_q << std::endl;
    std::cout << "\n各个结账时间出现的次数：:\n";
    histogram(service_times, service_t_min);

    std::cout << "\n总的顾客数："
            << std::accumulate(std::begin(service_times), std::end(service_times), 0)
            << std::endl;
    return 0;
}

直接使用 using 指令可以减少代码输入，简化代码。顾客结账信息记录在 vector 中。结账时间减去 service_times 的最小值可以用来索引需要自增的 vector 元素，这导致 vector 的第一个元素会记录下最少结账时间出现的次数。histogram() 函数会以水平条形图的形式生成每个服务时间出现次数的柱状图。

程序中 checkouts 的值为 600，意味着将模拟开业时间设置为 600 分钟，也可以用参数输入这个时间。main() 函数生成了顾客结账时间，超市开门时等在门外的顾客数，以及顾客到达时间间隔的分布对象。我们可以轻松地将这个程序扩展为每次到达的顾客数是一个处于一定范围内的随机数。

通过调用 min_element() 算法可以找到最短的 Checkout 对象队列，因此顾客总是可以被分配到最短的结账队列。在这次模拟开始前，当超市开门营业时，在门外等待的顾客的初始序列被添加到 Checkout 对象中，然后结账时间记录被更新。

模拟在 while 循环中进行，在每次循环中，time 都会增加 1 分钟。在下一个顾客到达期间，new_cust_interval 会在每次循环中减小，直到等于 0。用新的随机结账时间生成新的顾客，然后把它加到最短的 Checkout 对象队列中。这个时候也会更新变量 longest_q，因为在添加新顾客后，可能出现新的最长队列。然后调用每个 Checkout 对象的 time_increment() 函数来处理队列中的第一个顾客。

下面是一些示例输出：

输入超级中结账柜台的数量：2
等待超市营业的顾客人数：20
最大的队列长度为：43

各个结账时间出现的次数：
  2   13 *************
  3   20 ********************
  4   11 ***********
  5   16 ****************
  6   12 ************
  7   18 ******************
  8   17 *****************
  9   18 ******************
10   10 **********
11   22 **********************
12   19 *******************
13   13 *************
14   16 ****************
15   18 ******************

总的顾客数：223

这里有 2 个结账柜台，最长队列的长度达到 43，已经长到会让顾客放弃付款。

以上代码还可以做更多改进，让模拟更加真实，例如，均匀分配并不符合实际，顾客通常成群结队到来。可以增加一些其他的因素，比如收银员休息时间、某个收银员生病工作状态不佳，这些都会导致顾客不选择这个柜台结账。