C++：队列模拟（第十二章）

队列模拟分为队列类和顾客类,模拟顾客排队（链表模型），主要功能是记录在指定的时间内，一共访问了多少个顾客，一共服务了多少个顾客，一共离开了（未完成交易）多少个顾客以及计算出每个顾客平均等待时间和平均队伍长度。

队列类

队列类特征

队列存储有序项目序列

队列所能容纳的项目数有一定的限额

能创建空队列

能够检查队列是否为空

能够检查队列是否已满

能够在队尾添加元素

能够在队首删除元素

能够确定队列中元素数

类接口（声明）

class Queue{
    enum {Q_Size =10}; 
    private:
        struct Node{
            Item item;
            struct Node* next;
                    }; 
        Node* front;
        Node* rear;
        int items;
        const int qsize;
        
    public:
        Queue(int qs = Q_Size);
        ~Quene();
        bool isempty() const;
        bool isfull() const;
        int queuecount () const;
        bool enqueue(const Item& item);
        bool dequeue(Item& item) ;
};

程序解析：

用枚举的方法规定最大的顾客数为10，因为enum声明的是静态常量，所以需要同样在private部分声明常量整数qsize

声明一个结点的结构体，内容有Item类对象和下一个结点的指针。Item类对象将在顾客类之后用typedef声明

声明两个指向结点结构体的指针，一个指向头部，一个指向尾部。

用到单向链表知识。每一个node表示的是顾客已经顾客当前在队伍（链表）中的位置。

C++特性：类中嵌套结构或类声明。将Node声明放在类中，可以使Node的作用域为整个类。可以用它来声明类成员，也可以将它作为类方法中的类名称。

items 为队伍中的总顾客数

类方法：

Queue::Queue(int qs): qsize(qs),items(0)
{
    front = rear = nullptr;
}

Queue::~Queue()
{
    Node* temp;
    while(front!= nullptr)
    {
        temp = front;
        front = front->next;
        delete temp;
    }
}

bool Queue::isempty() const
{
    return items==0;
}

bool Queue::isfull() const
{
    return items==qsize
}

int Queue::queuecount() const
{
    return items;
}

bool Queue::enqueue(const Item& item)
{
    if(isfull()!=0)
        return false;
    Node* add = new Node;
    add->item = item;
    add->next = nullptr;
    if(front == nullptr)
        front = add;
    else
        rear->next= add;
    rear = add;
    items++;
    return true; 
}

bool Queue::dequeue(Item& item)
{
    if(isempty()==1)
        return false;
    item = front->item;
    Node* temp = front;
    front = front->next;
    delete temp;
    items--;
    if(items==0) 
        rear = nullptr;
    return true;
}

程序解析：

在构造函数中是无法赋值给const成员的，解决方法就是成员初始化列表，由逗号分割开来。对于const成员必须使用这种方法。
比如Quene::Quene(int qs) : qsize(qs)就相当于初始化了qs。对于本身就是类对象的成员来说，使用这种方法将大大提高效率。

入队方法思路：
判断队列是否为满。创建一个新结点（顾客），然后复制信息到这个结点里。然后判断这个顾客是否为第一个顾客，若是，则front设为她。然后rear的next指针指向她，随后rear设置为这个顾客。items加一。

出队方法思路：
判断队伍是否为空。将要出队的那个结点保存到变量引用里（参数），然后创造一个新节点指向front，然后front指到front->next，items减一。判断items是否为0。若是则rear = null。

由于不能保证类过期后所有创建的内存都会被删除，所以析构函数负责从头到尾delete内存。

Question1:使用new的类通常需要包含显式复制构造函数和执行深度复制的赋值运算符，默认的成员复制OK不？
Ans：不OK，复制Queue成员对象将生成一个新对象，该对象指向链表原来的头和尾，这样破坏了原来的链表。要不就是编写复制构造函数和赋值运算符，要不就利用一个小技巧避免这些额外工作。
class Queue
{
   private:
         Queue ( const Queue& q) : qsize(0) {}
         Queue& operator= (const Queue& q) {return *this}
这样做避免了本来自动生成的默认方法定义，而且因为方法是私有的所以不能广泛使用。所以Queue snick(nip) 和 tuck = nip是不被允许的（假如nip和tuck是Queue对象）

customer类

customer只要包含到达时间以及交易所需时间就可以了

class Customer{
    private:
        long arrive;
        int processtime;
    public:
        Customer(){arrive = processtime =0;}
        void set(long when);
        long when() const {return arrive;}
        int ptime() const {return processtime;}
}; 

typedef Customer Item;

//源代码文件内：
void Customer::set(long when)
{
    processtime = std::rand()%3+1;
    arrive = when;
}

程序解析：

假设每个顾客的交易时间是1~3分钟。 set()程序里使用rand（）

主程序

思路：

输入队伍最大容纳数、模拟排队时长、平均每小时访问顾客数

需要记录的数据：拒绝客户数、服务客户数、队伍中客户数、累计队伍长度、一个客户的交易时长、队伍总等待市场

如何判断是否有客户来：假设平均每6分钟来一个顾客
bool newcustomer(double x)
{      
     return (std::rand() * 6 / RAND_MAX < 1 );
}
RAND_MAX是rand（）可能返回的最大值，
这样rand() * x/ RAND_MAX就属于0~6了，小于1时就有1/6的几率，这样平均每6分钟就来一个顾客。

拒绝客户数——客户出现且队伍已满

服务客户数——客户离开队伍

累计队伍长度——每一分钟都加
程序如下：

#include<iostream>
#include"queue.h"
#include<cstdlib>
#include<ctime>
const int MIN_PER_HR = 60;
bool newcustomer(double x);
int main()
{
    using std::cout;
    using std::endl;
    using std::cin;
    using std::ios_base;
    std::srand(std::time(0));
    cout<<"输入队列的最大容纳数：\n" ;
    int qs;
    cin>>qs;
    Queue line(qs);  //创建队列
    
    cout<<"输入模拟时长：(hours))\n" ;
    int hours;
    cin>>hours;
    long cyclelimit = MIN_PER_HR * hours;  //转换为分钟
    
    cout<<"输入平均每小时的顾客数\n";
    double perhour;
    cin>>perhour;
    double min_per_cus;
    min_per_cus = MIN_PER_HR / perhour;   //就是平均几分钟来一个customer
    
    Item temp;
    long turnaways = 0 ;  //拒绝客户数量
    long customers = 0 ; //队伍中的客户数
    long served = 0;  //已服务的客户数
    long sum_line = 0 ; //累计队伍长度
    long wait_time = 0 ; //一个客户正在交易需要等待时长
    long line_wait = 0 ; //队伍总等待时长
    
    for(int cycle =0; cycle<cyclelimit ; cycle++)
    {
        if(newcustomer(min_per_cus))
        {
            if(line.isfull())
                turnaways ++;
            else
            {
                customers++;
                temp.set(cycle);
                line.enqueue(temp);
            }
        }
        if(wait_time<=0&&!line.isempty())
            {
                wait_time = temp.ptime();
                line_wait += cycle - temp.when();
                line.dequeue(temp);
                served++;
            }
        if(wait_time > 0)
            wait_time --;
        sum_line += line.queuecount();
     } 
     
     
    if(customers>0)
    {
        cout<<"已访问顾客: "<<customers<<endl;
        cout<<"已服务顾客："<<served<<endl;
        cout<<"已拒绝顾客："<<turnaways<<endl;
        cout<<"平均队伍长度: ";
        cout.precision(2);
        cout.setf(ios_base::fixed, ios_base::floatfield);
        cout<<(double) sum_line / cyclelimit<<endl;
        cout<<"平均等待时长：" <<(double)line_wait / served<<endl; 
    }
    else
        cout<<"没顾客\n";
    return 0;   
}

bool newcustomer(double x)
{
    return (std::rand()*x/RAND_MAX <1);
}

结果：

image.png

可以发现，最大容纳数越多，每小时来的顾客越多，等待时间和队伍长度越长……