假设现在要建立一个 ATM，并对顾客排队等待的时间进行估测，需要编写一个程序来模拟这种情况。对于这种问题，最自然的方法是使用队列。

Queue 类

类接口

首先，要设计一个 Queue 类，这里先列出队列的特征：

队列存储有序的项目序列；
队列容纳的项目数有限制；
能创建空队列；
能检查队列是否为空；
能检查队列是否为满；
能在队尾添加项目；
能在队首删除项目；
能确定队列中项目数。
链表
首先需要解决的问题就是如何表示队列数据？一种方法是使用 new 动态分配一个数组，但对于队列操作而言，数组有点不太合适，要么在添加、删除元素时进行元素的移动，要么作一些更费力的工作，如将数组视为是循环的。然而，相比数组使用列表能够满足队列要求。
```
class Queue {
private:
  struct Node {
      Item item;
      Node * next;
  };
  enum {SIZE = 10}; // 队列的项目数
  Node * front; // 头指针
  Node * rear; // 尾指针
  int num; // 队列中元素的数目
  const int size; // 队列中最大可以有多少元素
public:
  Queue(int qsize = SIZE);
  ~Queue();
  bool isEmpty() const; // 队列是否为空
  bool isFull() const; // 队列是否为满
  int getCount() const; // 获取队列中元素数目
  bool add(Item &); // 往队列中添加元素
  bool remove(Item &); // 从队列中删除元素
};
```
嵌套使用类声明
上述声明使用了 C++ 的一项特性：在类中嵌套使用结构或类声明。通过将 Node 声明放在 Queue 类中，可以使其作用域为整个类。这样不用担心 Node 声明与某些全局声明or其他类中声明的 Node 发生冲突。如果像 Node 这种嵌套的声明是在类的私有部分进行的，则 Node 只能在这个类中来使用；如果像 Node 这种嵌套的声明是在类的公有部分进行的，则可以在类外使用 Queue::Node 来声明变量。
构造函数中常量的初始化(成员初始化列表)
类构造函数应提供类成员的值。由于队列在初始化时没有元素在排队，即队列应该是空的，因此，队首和队尾指针都应该设置为 nullptr，并将 num 设置为 0，另外，还应将队列的最大长度 size 设置为构造函数的参数 qsize。但是下面的构造函数的实现将会报错：

原因在于 size 成员被声明为 const，所以可以对 size 初始化，但不能给它赋值。从概念上说，调用构造函数时，对象将在 {} 中代码执行之前被创建。因此，调用 Queue(int qsize) 将导致程序首先给 4 个成员变量分配内存，然后程序流程进入到 {} 中，使用常规的赋值方式将值存储在内存中。因此，对于 const 数据成员，必须在执行到构造函数体之前，即创建对象时进行初始化。C++ 提供了一种特殊的语法来完成上述工作，它叫做成员初始化列表。成员初始化列表由逗号分隔的初始化列表组成(前面带冒号)。成员初始化列表位于构造函数参数列表的右括号之后，函数体的左括号之前。如果类的数据成员名称为 mdate，需要将其初始化为 val，则成员初始化列表的初始化器为 mdate(val)。使用这种表示法，可以这样编写 Queue 的构造函数：
```
Queue::Queue(int qsize) : size(qsize) {
  front = rear = nullptr;
  num = 0;
}
```
通常，初始化列表中可以初始化常量或构造函数中的参数，并不是只限于初始化常量。可以将 Queue 构造函数写成如下所示：
```
Queue::Queue(int qsize) : size(qsize), front(nullptr), rear(nullptr), num(0) {}
```
注意，只有构造函数才可以使用这种初始化列表的语法。对于 const 类成员，必须使用这种语法；另外，对于被声明为引用的类成员，也必须使用这种语法：
```
class Demo {
private:
  Member & member;
  ...;
};
Demo::Demo(Member & m) : member(m) {}
```
原因在于引用与 const 数据类似，只能在被创建时进行初始化。对于简单数据成员(如，front、rear 和 num)，使用成员初始化列表和在函数体内使用赋值没什么区别。然而，对于本身就是类对象的成员来说，使用成员初始化列表的效率更高。

使用成员初始化列表需要注意以下几点：

这种格式只能用于构造函数；
初始化非静态 const 数据成员必须使用初始化列表来完成；
初始化引用数据成员必须使用初始化列表来完成。
添加队列元素
队列添加元素是从队尾添加，需要经过以下几个阶段：

如果队列已经满了，则不能添加元素；
否则，创建新节点，并将参数 Item 的值复制给新节点；

将节点添加到队尾，并更新 num 的值。

bool Queue::add(const Item & item) {
 // 队列已满不能添加元素
 if (isFull())
     return false;

 Node * node = new Node;
 node->item = item;
 node->next = nullptr;

 // 如果队列是空的, 不需要连接Node, 只需要将头指针置为添加的元素即可
 if (isEmpty())
     front = node;
 else
     rear->next = node;
 rear = node;
 num++;
 return true;
}

注意，创建 Node 节点必须用 new，否则退出函数时会被销毁。

删除队列元素

队列删除元素是从队首删除，需要经过以下阶段：

如果队列为空，则不能删除元素；
否则，创建一个临时的 Node 指针，指向队首元素(头指针指向的元素)，并将队首元素的 Item 赋值给参数，以便返回给主调函数；
将队首元素从队列中删除(front 指针指向下一个元素)，释放出队元素的内存，并更新 num；
如果删除元素之后队列是空的，将 rear 设置为 null。
```
bool Queue::remove(Item & item) {
 // 空队列不能删除元素
 if (isEmpty())
     return false;

 Node * temp = front;
 item = temp->item;

 front = front->next;
 delete temp;
 num--;

 // 如果删除元素之后队列为空，将尾指针置为 null
 if (isEmpty())
     rear = nullptr;
 return true;
}
```
析构函数
虽然类构造函数中没有使用 new 为数据对象申请内存，好像不用在析构函数中释放 new 申请的内存。这种想法是错误的，因为向队列添加对象将调用 new 来创建新的节点，虽然通过删除的节点的 remove 方法可以释放节点的内存，但是不能保证队列到期时为空。因此，类需要一个显式的析构函数删除所有剩余的节点。

禁用复制构造函数与赋值运算符
使用 new 的类通常需要包含显式的复制构造函数和执行深拷贝的赋值运算符，这个例子也是如此吗？
复制 Queue 对象的成员将生成一个新的对象，该对象的头指针和尾指针依旧指向原来队列的头和尾。因此，将 Item 添加到复制的 Queue 对象中，将添加到复制对象与原对象共享的队列，更糟糕的是只有复制对象的尾指针会更新为新添加的元素，原对象的尾指针不会修改。显然，克隆或复制队列，必须提供复制构造函数和执行深拷贝的赋值运算符。
但是这里的模拟不实现上述功能，虽然可以忽视这些问题，但是在将来的某个时候，可能需要再次使用队列且需要复制，而我们可能跟会忘记没有为复制提供适当的代码。在这种情况下，程序能够正常编译和运行，但结果是混乱的，甚至可能会崩溃。因此，最好还是提供复制构造函数和赋值运算符，尽管目前不需要他们。
但其实有一种小小的技巧避免这些额外工作，并确保程序不会崩溃，这个技巧就是将所需的方法定义为私有方法：
```
class Queue {
private:
 Queue(const Queue & q) : size(q.size) {}
 Queue & operator=(const Queue & q) { return *this;}
}
```
这样做有两个作用：第一，避免了使用自动生成的默认方法；第二，因为这些方法被声明为私有的，因此下面的代码不被允许使用：
```
Queue q1;
Queue q2(q1); // error
Queue q3;
q3 = q1; // error
```
PS：C++11 提供了另一种禁用函数的方法 —— 使用关键字 delete。

其他问题

有没有其他问题需要注意？当然有，当 Queue 对象按值传递或返回时将调用复制构造函数。因此，在使用 Queue 类的时候必须要遵循优先采用引用传递对象的习惯，这样就不会有问题。
另外，复制构造函数还被用于创建其他临时对象，但 Queue 定义中并没有导致创建临时对象的操作，例如重载加法运算符。

Client 类

其次，需要设计一个顾客类。通常，顾客有很多属性，例如，姓名，账号，密码，账号余额等。然而这里只需要记录顾客到达的时间、交易所需的时间。
当模拟生成新顾客时，程序将创建一个新的顾客对象，并在其中保存顾客到达的时间以及一个随机生成的交易时间。当客户到达队首时，程序将记录此时的时间，并将其与进入队列的时间相减，得到顾客的等候时间。

typedef class Client {
private:
    long arrive_time;// 顾客到达时间
    int process_time;// 顾客处理时间
public:
    Client() { arrive_time = process_time = 0; }
    Client(long at, int pt) { arrive_time = at; process_time = pt; }

    void set(long at);
    long get_arrive_time() const { return arrive_time; };
    int get_process_time() const { return process_time; };
} Item;

void Client::set(long at) {
    arrive_time = at;
    process_time = std::rand() % 3 + 1;
}

Client 的默认构造函数创建一个空顾客，set() 成员函数将到达时间设置为参数，并将处理时间设置为 1~3 中的一个随机值。

ATM 模拟

现在已经拥有模拟 ATM 所需要的工具。程序允许用户输入 3 个数：队列的长度、程序模拟的持续时间(单位为小时)以及平均每小时的客户数。程序将使用循环 —— 每次循环代表一分钟，在每分钟的循环中，程序完成下面的工作：

判断是否来了新客户。如果来了，并且队列未满，则新客户入队，否则拒绝客户入队；
如果没有客户在进行交易，则选取队列的第一个客户进行交易。确定该客户的等候时间，并将 wait_time 计数器设置为新客户所需的处理时间；
如果客户正在处理，则将 wait_time 计数器减 1；
记录各种数据，包括获取服务的客户数目、拒绝的客户数目、排队等候的累计时间以及累计的队列长度等；
当模拟的循环结束时，程序将报告各种统计结果。

这里还存在一个问题是，程序如何确定是否有新客户的到来？这里我们假设平均每 6 分钟将会有一位新客户，但正好 6 分钟来一个客户不太现实，我们将通过 rand() 函数实现一个更随机的过程：

// 在循环中判断当前循环是否有新顾客到来
bool isNewClient(double x) {
    return x * std::rand() / RAND_MAX < 1;
}

x * std::rand() / RAND_MAX将返回 0 ~ x 的数值，因此 isNewClient() 函数将有 1/x 的概率返回 true。

#include "client.h"
#include <ctime>
#include <cstdlib>
#include <iostream>
const int MIN_PER_HOURS = 60;

// 在循环中判断当前循环是否有新顾客到来
bool isNewClient(double x) {
    return x * std::rand() / RAND_MAX < 1;
}

int main(int args, char* arg[]) {
    int queue_size, hours;
    double perhour;
    std::cout << "Please input maximum size of Queue:\n";
    std::cin >> queue_size;
    std::cout << "Please input number of simulation hours:\n";
    std::cin >> hours;
    std::cout << "Please input average number of client per hour:\n";
    std::cin >> perhour;

    int cycle = hours * MIN_PER_HOURS; // 循环的轮次, 一轮等于一分钟
    double min_per_client = 1.0 * MIN_PER_HOURS / perhour; // 平均每个顾客到达的时间


    Queue queue(queue_size); // 创建队列
    Item temp; // 临时对象
    long turnaways = 0; // 由于队列满了被拒绝的人数
    long clients = 0; // 记录排队的顾客总数目
    long served = 0; // 模拟期间的服务次数
    long sum_queue = 0; // 累积长度
    long wait_time = 0; // 顾客处理时间
    long queue_wait = 0; // 顾客总的等待时间

    for(int i = 0; i < cycle; i++) {
        if(isNewClient(min_per_client)) {
            // 本轮循环有新顾客到来
            if(queue.isFull()) {
                // 此时队列是满的, 将拒绝该顾客
                turnaways++;
            } else {
                // 此时队列没有满, 顾客入队
                clients++;
                temp.set(i);
                queue.add(temp);
            }
        }
        if (wait_time <= 0 && !queue.isEmpty()) {
            // 当前顾客处理完毕, 从队列中选取下一个服务的顾客
            queue.remove(temp);
            wait_time = temp.get_process_time();
            queue_wait += i - temp.get_arrive_time(); // 已经服务完的顾客总的等待时间需要加上最新被选中的顾客等待的时间
            served++; // ATM 服务顾客的次数加 1
        }
        if (wait_time > 0)
            wait_time--;
        sum_queue += queue.getCount();
    }

    // 展示统计的信息
    if (clients > 0) {
        std::cout << clients << " clients arrived.\n";
        std::cout << served << " clients use ATM.\n";
        std::cout << turnaways << " clients leave.\n";
        std::cout << "Queue average size is " << (double) sum_queue / cycle << std::endl;
        std::cout << "Client average wait time is " << (double) queue_wait / served << std::endl;
    } else
        std::cout << "No clients.\n";
    std::cout << "Finished.\n";
    return 0;
}

Please input maximum size of Queue:
10
Please input number of simulation hours:
100
Please input average number of client per hour:
30
2857 clients arrived.
2849 clients use ATM.
71 clients leave.
Queue average size is 4.48133
Client average wait time is 9.4198
Finished.

编程语言

4. 练习：队列模拟

Queue 类

类接口

链表

嵌套使用类声明

构造函数中常量的初始化(成员初始化列表)

添加队列元素

删除队列元素

析构函数

禁用复制构造函数与赋值运算符

其他问题

Client 类

ATM 模拟