数据结构：思想与方法-翁惠玉-27783第六章幻灯片.ppt

* STL中的优先级队列 头文件：queue 类模版：priority_queue 实现方式：二叉堆 主要成员： Void push( const Object x) Const Object top() const Void pop() Bool empty() Void clear() * 使用实例 #include iostream #include queue using namespace std; int main() { priority_queueint q; q.push(10); q.push(1); q.push(5); q.push(8); q.push(0); q.push(4); q.push(9); q.push(7); q.push(3); q.push(6); q.push(2); while (!q.empty()) {cout q.top() ; q.pop();} return 0; } * 第6章 优先级队列 基本的优先级队列 二叉堆 D堆 归并优先级队列 STL中的优先级队列 排队系统的模拟 * 单服务台的排队系统 在单服务台系统中，先到达的顾客先获得服务，也肯定先离开 事件处理的次序是：顾客1到达、顾客1离开、顾客2到达、顾客2离开、……、顾客n到达、顾客n离开 只需要一个普通队列保存顾客到达信息 * 多服务台的排队系统 在多服务台系统中，先到达的顾客先获得服务，但后获得服务的顾客可能先离开； 事件处理的次序可能是：顾客1到达、顾客2到达、顾客2离开、顾客3到达、顾客1离开、顾客3离开……、顾客n到达、顾客n离开、…… 发生时间早的事件先处理，发生时间晚的事件后处理。因而需要一个优先级队列存放事件。事件的优先级就是发生的时间 * 模拟过程 模拟开始时，产生所有的到达事件，存入优先级队列。 模拟器开始处理事件： 从队列中取出一个事件。这是第一个顾客的到达事件。生成所需的服务时间。当前时间加上这个服务时间就是这个顾客的离开时间。生成一个在这个时候离开的事件，插入到事件队列。 同样模拟器从队列中取出的事件也可能是离开事件，这时只要将这个离开事件从队列中删去，为他服务的服务台变成了空闲状态，可以继续为别的顾客服务。 * 产生CustomNum个顾客的到达事件， 按时间的大小存入事件队列； 置等待队列为空； 置所有柜台为空闲； 设置等待时间为0； 多服务台的排队系统过程 * While （事件队列非空） { 队头元素出队； 设置当前时间为该事件发生的时间； switch(事件类型） { case 到达：if (柜台有空) { 柜台数减1； 生成所需的服务时间 ； 修改事件类型为“离开” 设置事件发生时间为当前时间加上服务时间； 重新存入事件队列；} else 将该事件存入等待队列； case 离开：if （等待队列非空） { 队头元素出队； 统计该顾客的等待时间； 生成所需的服务时间 ；修改事件类型为“离开” 设置事件发生时间为当前时间加上服务时间； 存入事件队列； } else 空闲柜台数加1； } } 计算平均等待时间； 返回； } * 模拟类 设计一个模拟类，告诉它顾客到达时间间隔的分布、服务时间的分布、模拟的柜台数以及想要模拟多少个顾客。能提供在本次服务中顾客的平均等待时间是多少。 因此这个类应该有两个公有函数：构造函数接受用户输入的参数，另外一个就是执行模拟并最终给出平均等待时间的函数avgWaitTime。这个类要保存的数据就是模拟的参数。 * 模拟类的定义 class simulator{ int noOfServer; //服务台个数 int arr