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，已經長到會讓顧客放棄付款。

以上程式碼還可以做更多改進，讓模擬更加真實，例如，均勻分配並不符合實際，顧客通常成群結隊到來。可以增加一些其他的因素，比如收銀員休息時間、某個收銀員生病工作狀態不佳，這些都會導致顧客不選擇這個櫃台結賬。