数据结构3

数据结构 3 队列

Where 队列？

计算机中CPU将时间切成很多个小的时间单元，实际上是轮流在为用户服务，存在一个等待运行的过程——尽情期待《操作系统》（bushi）

银行ATM 取款机 排队的过程

循环队列

难以判断是满是空时，我们一般选择牺牲一个单元（但似乎记录一下队列的长度也可以解决问题）

循环队列类同样需要由队列的抽象类派生
即便是循环队列同样可能存在存储空间不够的情况，所以我们仍然需要私有成员函数doubleSpace，需要注意的是，这里的doubleSpace函数在平移数据时，需要从front开始

队列链接实现

使用不带头结点的单链表实现，同时需要记录头尾结点的位置（空间换时间），这样就使得入队（在链表尾处实现）和出队（在链表头实现）的复杂度都是O(1)的时间复杂度。
注意：这里是因为在链表头插入删除都很方便，但在链表尾处插入操作是O(1)的，但删除操作需要将队尾元素前一个元素的next指针置空，复杂度达到了O(n)，故我们考虑在头处删除（对应出队操作），在尾处插入（对应入队操作）

更要注意的是，在enQueue（入队操作）时，如果尾结点是空指针，需要进行特判（RE启动！）
deQueue操作需要返回出队元素的值，所以还要先保存那个值，同时记得delete（leak启动！）还有一个特殊情况，就是当队中只有一个元素时，将其出队后，需要将尾结点也置空。

STL中的队列

和栈一样，是容器适配器，借助已有线性表。由于vector在表头操作很糟糕，所以我们一般采用list和deque。
包含头文件
#include<queue>

队列应用

列车车厢重排

一列货运列车共有n节车厢，每节车厢将被放在不同的车站。假定n个车站的编号分别为1 – n，货运列车按照第n站到第1站的次序经过这些车站。车厢的编号与它们的目的地相同。为了便于从列车上卸掉相应的车厢，必须重新排列这些车厢，将第n节车厢放在最后，第1节车厢放在最前面。

Thought：利用k根轨道重排n节车厢，初始排列次序在数组in中

void arrange(int in[],int k,int n){
    linkQueue<int> *buffer = new linkQueue<int>;
    int last = 0;
    for(int i = 0;i < n;i ++){
        if(!putbuffer(buffer,k,in[i])) return;
        checkbuffer(buffer,k,last);
    }
}

bool putbuffer(linkQueue<int>*buffer,int size,int in){
    int avail = -1;
    int max = 0;
    for(int j = 0;j < size;j ++){
        if(buffer[j].isEmpty()){
            if(avail == -1){
                avail = j;
            }else if(buffer[j].getTail() < in && buffer[j].getTail() > max){
                avail = j;
                max = buffer[j].getTail();
            }
        }
    }
    if(avail != -1){
        buffer[avail].enQueue(in);
        return true;
    }else{
        return false;
    }
}

void checkbuffer(linkQueue<int>*buffer,int size,int &last){
    int j;
    bool flag = true;
    while(flag){
        flag = false;
        for(int j = 0;j < size;j ++){
            if(!buffer[j].isEmpty()&& buffer[j].getHead() == last + 1){
                last ++;
                flag = true;
                break;
            }
        }
    }
}

排队系统的模拟

模拟（simulation）是计算机的一个重要应用，是指用计算机来仿真现实系统的操作并收集统计数据。

虚拟时间
模拟系统是一个虚拟的系统，一般不需要使用真实的精确时间，只要用一个时间单位即可，这个时间单位叫做一个嘀嗒。一个嘀嗒可以表示1秒，也可以表示1分钟，也可以表示一小时，这根据应用来决定。

时间驱动的模拟
工作过程：沿着时间轴模拟这一时刻发生的事情，并做相应的处理
如龟兔赛跑

事件驱动的模拟

工作过程：按事件发生的时间一件一件处理
如排队系统的模拟
特点:

• 事件不是连续发生的
• 没有必要模拟没有事件发生的时间

如何产生顾客到达事件和服务时间

尽管服务时间和顾客到达的间隔时间是可变的，但从统计上来看是服从一定的概率分布。
要生成顾客的到达时间或生成服务时间必须掌握如何按照某个概率生成事件。
如顾客到达的间隔时间服从[a，b]之间的均匀分布，则可以生成一个[a，b]之间的一个随机数x，表示前一个顾客到达后，经过了x的时间后又有一个顾客到达了。
rand() * (b – a + 1)/(RAND_MAX + 1) + a

设计单服务台排队系统

设计一个只有一个服务台的排队系统，希望通过这个模拟器得到顾客的平均排队时间。顾客到达的时间间隔服从[arrivaLow, arrivalHigh]的均匀分布；服务时间长度服从[serviceTimeLow, serviceTimeHigh]间的均匀分布；一共模拟customNum个顾客。要求统计顾客的平均排队时间。

模拟过程

生成所有的顾客到达事件，按到达时间排成一个队列。

• 依次处理队列中的每个元素，直到队列为空
• 检查顾客的到达时间和当前时间，计算等待时间，记入累计值；
• 生成顾客服务时间
• 将当前事件拨到该顾客的离开时间
• 返回累计值除以顾客数的结果。