网站设计人员就业要求,上海知名 网站设计公司,南通网站制作价格,网站上投放广告队列
基本概念
队列的定义
队列#xff08;Queue#xff09;#xff1a;队列是一种常见的数据结构#xff0c;遵循先进先出#xff08;First-In-First-Out, FIFO#xff09;的原则。在队列中#xff0c;元素按照进入队列的顺序排列。队列是一个线性的数据结构#x…队列
基本概念
队列的定义
队列Queue队列是一种常见的数据结构遵循先进先出First-In-First-Out, FIFO的原则。在队列中元素按照进入队列的顺序排列。队列是一个线性的数据结构并且这个数据结构只允许在一端进行插入另一端进行删除禁止直接访问除这两端以外的一切数据。
队首Front最先进入队列的元素可以被访问或移除队尾Rear最后进入队列的元素不允许进行访问和删除的另一端。空队列不含任何元素的队列。
队列的特点
队列是一种先进先出First in First outFIFO的数据类型。每次元素的入队都只能添加到队列尾部出队时从队列头部开始出。 队列的常见基本操作 入队Enqueue将新元素添加到队列的末尾队尾。 出队Dequeue移除队列中的第一个元素队首。 获取队首元素Front获取队列中的第一个元素但不将其从队列中移除。 获取队列大小Size获取队列中当前元素的数量。 检查队列是否为空IsEmpty检查队列中是否有元素。
优先级队列
上文已经提到了队列先进先出的特点而优先级队列不满足先进先出的条件更像是数据类型中的“堆”。
入队Enqueue优先级队列入队时会根据优先级来考虑哪个元素先入队优先级可以通过元素的大小等进行定义。比如定义元素越大优先级越高则元素大的先入队。
出队Dequeue优先级队列每次出队的元素是队列中优先级最高的那个元素而不是队首的元素。比如定义元素越大优先级越高那么每次出队都是将当前队列中最大的那个元素出队。
队列通常用于模拟排队的场景如任务调度、消息传递等。在计算机科学中队列也是广泛应用的一种数据结构在算法设计和实现中发挥着重要作用。所以下面让我们动手实现一个优先级队列用来模拟银行排队问题
队列的应用
银行排队问题 题目描述
假设银行有 K 个柜台所有顾客按到达时间排队当有柜台空闲队伍最前面的顾客前往空闲柜台处理事务求顾客的平均排队时间排队时间到空闲柜台开始处理事务时间-到达时间。
提示
用优先级队列实现并且以到达时间和服务时间作为数组输入
输入
第一行输入柜台个数≥1——int 型 第二行输入顾客个数≥1——int 型 第三行输入每位顾客的到达时间≥0——int 型数组默认升序。 第四行输入每位顾客的服务时间≥0——int 型数组
输出
第一行输出顾客的平均排队时间——int 型向下取整。
样例输入
1
10
0 1 2 3 4 5 6 7 8 9
10 10 10 10 10 10 10 10 10 10
样例输出
40
解题思路
该问题要求模拟银行顾客排队的过程通过输入柜台数、顾客数、每位顾客的到达时间和服务时间模拟了顾客在银行排队办理业务的过程计算顾客的平均排队时间。解题思路如下 创建优先级队列使用优先级队列来模拟顾客的排队情况。队列中的元素按到达时间排序即到达时间越早的顾客排在队列前面。这样在柜台空闲时就可以直接从队列头部取出顾客进行服务。 初始化读取输入的柜台个数、顾客个数、到达时间数组和服务时间数组。将顾客的到达时间和对应的服务时间插入到优先级队列中。 模拟排队过程开始模拟银行排队的过程直到所有顾客都被服务完毕为止。在每个时间点检查是否有柜台空闲如果有则从队列中取出最早到达的顾客进行服务计算其排队时间并累加到总的排队时间中。 计算平均排队时间将总的排队时间除以顾客总数即可得到平均排队时间向下取整并输出结果
代码实现
结点类node
首先是队列的结点设计可以设计出两个结构体一个结构体 Node 表示结点其中包含有 data 域和 next 指针如下图 其中 data 表示数据其可以是简单的类型也可以是复杂的结构体故采用泛型编程templatetypename eT。next 指针表示下一个的指针其指向下一个结点通过 next 指针将各个结点链接。结点类还有构造函数在创建结点时可以进行初始化
templatetypename eT
class node {
public:eT data;node* next;node(const eT data_, nodeeT* next_ NULL){data data_;next next_;}node() : next(NULL) {}~node() {}
};
自定义队列linkQueue
自定义队列linkQueue采用泛型编程其中 eT 是模板参数代表队列中元素的类型。
front 和 tail 分别是指向队列前端和尾端的指针用于操作队列中的元素。 构造函数和析构函数
构造函数用于初始化队列将 front 和 tail 初始化为 NULL表示队列为空。
析构函数用于释放队列中所有节点的内存。它通过循环遍历队列中的所有节点逐个删除节点并更新 front 指针直到队列为空。
成员函数 isEmpty
isEmpty函数用于检查队列是否为空如果front指针为空则队列为空返回true否则返回false
成员函数 enQueue
enQueue 函数用于向队列尾部添加一个新元素。如果队列为空即 tail 为空则创建一个新节点将 front 和 tail 都指向该节点。如果队列非空则在 tail 指向的节点后面添加一个新节点并更新 tail 指针。
成员函数 deQueue
deQueue 函数用于从队列头部移除一个元素并返回其值。
首先保存队列头部节点的指针 tmp并保存头部节点的值到 value 中。
然后更新 front 指针指向原头部节点的下一个节点。如果队列只有一个节点即移除后为空则将 tail 也置为空。
最后释放原头部节点的内存并返回其值。
templatetypename eT
class linkQueue{
public:nodeeT* front, * tail;
public:linkQueue() { front tail NULL; }~linkQueue() {nodeeT* tmp;while (front ! NULL) {tmp front;front front-next;delete tmp;}}bool isEmpty() { return front NULL; }void enQueue(const eT x) {if (tail NULL)front tail new nodeeT(x);else {tail-next new nodeeT(x);tail tail-next;}}eT deQueue() {nodeeT* tmp front;eT value front-data;front front-next;if (front NULL) tail NULL;delete tmp;return value;}
};
优先级队列priorityQueue
与自定义队列linkQueue相同采用泛型编程其中 eT 是模板参数代表队列中元素的类型。front 和 tail 分别是指向队列前端和尾端的指针用于操作队列中的元素。
同样地优先级队列priorityQueue与自定义队列linkQueue的初始化判断非空出队操作基本相同主要不同点在于入队操作。
成员函数 enQueue
enQueue 函数用于向队列尾部添加一个新元素。如果队列为空即 tail 为空则创建一个新节点将 front 和 tail 都指向该节点。如果队列非空则寻找较大元素的前继结点进行插入操作以保持队列的有序性。 template typename eT
class priorityQueue {
public:nodeeT* front, * tail;priorityQueue() { front tail NULL; }~priorityQueue() {nodeeT* tmp;while (front ! NULL) {tmp front;front front-next;delete tmp;}}bool isEmpty() { return front NULL; }eT deQueue() {nodeeT* tmp front;eT value front-data;front front-next;if (front NULL) tail NULL;delete tmp;return value;}void enQueue(const eT x) {if (tail NULL)front tail new nodeeT(x);else {nodeeT* p;if (x front-data){p new nodeeT(x, front); front p;}else {p front;while (p-next ! NULL p-next-data x) p p-next;if (p-next NULL){tail-next new nodeeT(x);tail tail-next;}else p-next new nodeeT(x, p-next);}}}
}; 模拟银行排队系统simulator 成员变量 1.noOfServer表示银行柜台的数量。 2.customNum表示顾客的数量。 3.arrivalTimeList存储每位顾客到达银行的时间。 4.serviceTimeList存储每位顾客所需的服务时间。 内部结构体 eventT 1.用于描述事件包括事件发生时间 time 和事件类型 type0 表示到达1 表示离开。 2.重载了小于操作符以便将事件按照发生时间进行排序。 class simulator {int noOfServer;int customNum;int* arrivalTimeList;int* serviceTimeList;struct eventT{int time; //事件发生时间int type; //事件类型。0 为到达1 为离开bool operator(const eventT e) const { return time e.time; }};
}; 构造函数和析构函数 构造函数从标准输入中读取柜台数、顾客数以及每位顾客的到达时间和服务时间然后分配内存给 arrivalTimeList 和 serviceTimeList分别用这两个数组储存每位顾客的到达时间和服务时间 析构函数释放动态分配的内存防止内存泄漏 public:simulator() {//std::cout 请输入柜台数;std::cin noOfServer;//std::cout 请输入模拟的顾客数;std::cin customNum;arrivalTimeList new int[customNum];serviceTimeList new int[customNum];for (int i 0; i customNum; i) {std::cin arrivalTimeList[i];}for (int i 0; i customNum; i) {std::cin serviceTimeList[i];}}~simulator() {delete arrivalTimeList;delete serviceTimeList;} 成员函数avgWaitTime 该函数用来模拟顾客排队到达和离开的过程并且计算出平均等待时间。在该函数中我们需要用自定义队列linkQueue来存储等待的顾客事件和顾客的服务时间并且用优先级队列priorityQueue存储顾客到达和离开的事件。 1.定义变量并进行初始化 变量表示的内容已注释 int serverBusy 0; // 记录当前服务中的柜台数量
int serviceTime 0; // 记录当前服务所需时间
int currentTime 0; // 记录当前时间
int totalWaitTime 0; // 记录总的等待时间
linkQueueeventT waitQueue; // 等待队列存储等待的顾客事件
priorityQueueeventT customerQueue; // 顾客队列存储到达和离开的顾客事件
linkQueueint serviceTimeQueue; // 服务时间队列存储顾客的服务时间
eventT currentEvent; // 当前事件2.生成初始事件队列 for (int i 0; i customNum; i) {currentEvent.type 0;currentTime arrivalTimeList[i]; // 每个顾客的到达时刻currentEvent.time currentTime;customerQueue.enQueue(currentEvent); // 将顾客到达事件加入到顾客队列中serviceTimeQueue.enQueue(serviceTimeList[i]); // 将顾客的服务时间加入到服务时间队列中
}3.模拟顾客到达和离开的过程 1用while循环不断取出顾客队列直到顾客队列为空即所有顾客都已经离开银行。从顾客队列中取出事件并将其赋值给 currentEvent将当前时间更新为当前事件的发生时间即顾客到达或离开的时间。 2根据事件类型进行处理 a.顾客到达 如果有空闲的柜台则顾客直接前往柜台处理业务将当前事件的结束时间继续存入顾客队列即顾客离开如果所有柜台都忙碌则顾客加入等待队列。 b.顾客离开 如果等待队列不为空则从等待队列中取出顾客并计算顾客等待的时间如果等待队列为空则只需更新柜台的繁忙状态。 while (!customerQueue.isEmpty()) {currentEvent customerQueue.deQueue(); // 取出顾客队列中的事件currentTime currentEvent.time; // 更新当前时间switch (currentEvent.type) {case 0: // 顾客到达事件if (serverBusy noOfServer) { // 如果有空闲的柜台serverBusy;currentEvent.time currentTime serviceTimeQueue.deQueue(); // 计算顾客服务结束时间currentEvent.type 1; // 设置事件类型为离开customerQueue.enQueue(currentEvent); // 将离开事件加入到顾客队列中} else { // 如果所有柜台都忙碌waitQueue.enQueue(currentEvent); // 将顾客加入等待队列}break;case 1: // 顾客离开事件if (!waitQueue.isEmpty()) { // 如果等待队列不为空serverBusy--;currentEvent waitQueue.deQueue(); // 取出等待队列中的顾客事件totalWaitTime currentTime - currentEvent.time; // 计算等待时间currentEvent.time currentTime serviceTimeQueue.deQueue(); // 计算顾客服务结束时间currentEvent.type 1; // 设置事件类型为离开customerQueue.enQueue(currentEvent); // 将离开事件加入到顾客队列中} else {serverBusy--;}break;default:break;}
}4.返回平均等待时间 return totalWaitTime / customNum; // 返回平均等待时间完整代码
#includeiostream
#includestdlib.h
#includequeue
using namespace std;
templatetypename eT
class node {
public:eT data;node* next;node(const eT data_, nodeeT* next_ NULL){data data_;next next_;}node() : next(NULL) {}~node() {}
};
templatetypename eT
class linkQueue{
public:nodeeT* front, * tail;
public:linkQueue() { front tail NULL; }~linkQueue() {nodeeT* tmp;while (front ! NULL) {tmp front;front front-next;delete tmp;}}bool isEmpty() { return front NULL; }void enQueue(const eT x) {if (tail NULL)front tail new nodeeT(x);else {tail-next new nodeeT(x);tail tail-next;}}eT deQueue() {nodeeT* tmp front;eT value front-data;front front-next;if (front NULL) tail NULL;delete tmp;return value;}
};
template typename eT
class priorityQueue {
public:nodeeT* front, * tail;priorityQueue() { front tail NULL; }~priorityQueue() {nodeeT* tmp;while (front ! NULL) {tmp front;front front-next;delete tmp;}}bool isEmpty() { return front NULL; }eT deQueue() {nodeeT* tmp front;eT value front-data;front front-next;if (front NULL) tail NULL;delete tmp;return value;}void enQueue(const eT x) {if (tail NULL)front tail new nodeeT(x);else {nodeeT* p;if (x front-data){p new nodeeT(x, front); front p;}else {p front;while (p-next ! NULL p-next-data x) p p-next;if (p-next NULL){tail-next new nodeeT(x);tail tail-next;}else p-next new nodeeT(x, p-next);}}}
};
class simulator {int noOfServer;int customNum;int* arrivalTimeList;int* serviceTimeList;struct eventT{int time; //事件发生时间int type; //事件类型。0 为到达1 为离开bool operator(const eventT e) const { return time e.time; }};public:simulator() {//std::cout 请输入柜台数;std::cin noOfServer;//std::cout 请输入模拟的顾客数;std::cin customNum;arrivalTimeList new int[customNum];serviceTimeList new int[customNum];for (int i 0; i customNum; i) {std::cin arrivalTimeList[i];}for (int i 0; i customNum; i) {std::cin serviceTimeList[i];}}~simulator() {delete arrivalTimeList;delete serviceTimeList;}int avgWaitTime() {int serverBusy 0;int serviceTime 0;int currentTime 0;int totalWaitTime 0;linkQueueeventT waitQueue;priorityQueueeventT customerQueue;linkQueueint serviceTimeQueue;eventT currentEvent;//生成初始的事件队列int i;for (i 0; i customNum; i){currentEvent.type 0;currentTime arrivalTimeList[i];//每个顾客的到达时刻currentEvent.time currentTime;customerQueue.enQueue(currentEvent);serviceTimeQueue.enQueue(serviceTimeList[i]);//每个顾客的服务时间}while (!customerQueue.isEmpty()){currentEvent customerQueue.deQueue();currentTime currentEvent.time;switch (currentEvent.type){case 0: if (serverBusy noOfServer){serverBusy;currentEvent.time currentTime serviceTimeQueue.deQueue();currentEvent.type 1;customerQueue.enQueue(currentEvent);}else {waitQueue.enQueue(currentEvent);}break;case 1:{if (waitQueue.isEmpty() 0){serverBusy--;currentEvent waitQueue.deQueue();totalWaitTime totalWaitTime currentTime - currentEvent.time;currentEvent.time currentTime serviceTimeQueue.deQueue();currentEvent.type 1;customerQueue.enQueue(currentEvent);}else serverBusy--;break;}default:break;}}return totalWaitTime / customNum;}};int main(){simulator sim;cout sim.avgWaitTime() endl;return 0;}
附录
分类专栏
链接
手把手教数据结构与算法
本专栏上一节
链接
手把手教数据结构与算法栈的应用平衡符号和简单计算器-CSDN博客
