devbox
我家小花儿
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

手把手教数据结构与算法：优先级队列（银行排队问题）_银行排队系统数据结构课程设计

作者：我家小花儿 | 2024-06-16 23:55:07

赞

踩

银行排队系统数据结构课程设计

个人主页：

想转码的电筒人

专栏：

手把手教数据结构与算法

目录

队列

基本概念

队列的定义

队列的特点

队列的常见基本操作

优先级队列

队列的应用

银行排队问题

题目描述

提示

输入

输出

样例输入

样例输出

解题思路

代码实现

结点类（node）

自定义队列（linkQueue）

构造函数和析构函数

成员函数 isEmpty

成员函数 enQueue

成员函数 deQueue

优先级队列（priorityQueue）

成员函数 enQueue

模拟银行排队系统（simulator）

成员变量

内部结构体 eventT

构造函数和析构函数

成员函数avgWaitTime

1.定义变量并进行初始化

2.生成初始事件队列

3.模拟顾客到达和离开的过程

4.返回平均等待时间

完整代码

附录

分类专栏

本专栏上一节

队列

基本概念

队列的定义

队列（Queue）：队列是一种常见的数据结构，遵循先进先出（First-In-First-Out, FIFO）的原则。在队列中，元素按照进入队列的顺序排列。队列是一个线性的数据结构，并且这个数据结构只允许在一端进行插入，另一端进行删除，禁止直接访问除这两端以外的一切数据。


队首（Front）：最先进入队列的元素，可以被访问或移除
队尾（Rear）：最后进入队列的元素，不允许进行访问和删除的另一端。
空队列：不含任何元素的队列。

队列的特点

队列是一种先进先出（First in First out，FIFO）的数据类型。每次元素的入队都只能添加到队列尾部，出队时从队列头部开始出。

队列的常见基本操作

  1. 入队（Enqueue）：将新元素添加到队列的末尾（队尾）。

  2. 出队（Dequeue）：移除队列中的第一个元素（队首）。

  3. 获取队首元素（Front）：获取队列中的第一个元素，但不将其从队列中移除。

  4. 获取队列大小（Size）：获取队列中当前元素的数量。

  5. 检查队列是否为空（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

解题思路

该问题要求模拟银行顾客排队的过程，通过输入柜台数、顾客数、每位顾客的到达时间和服务时间，模拟了顾客在银行排队办理业务的过程，计算顾客的平均排队时间。解题思路如下：

  1. 创建优先级队列：使用优先级队列来模拟顾客的排队情况。队列中的元素按到达时间排序，即到达时间越早的顾客排在队列前面。这样，在柜台空闲时，就可以直接从队列头部取出顾客进行服务。

  2. 初始化：读取输入的柜台个数、顾客个数、到达时间数组和服务时间数组。将顾客的到达时间和对应的服务时间插入到优先级队列中。

  3. 模拟排队过程：开始模拟银行排队的过程，直到所有顾客都被服务完毕为止。在每个时间点，检查是否有柜台空闲，如果有，则从队列中取出最早到达的顾客进行服务，计算其排队时间并累加到总的排队时间中。

  4. 计算平均排队时间：将总的排队时间除以顾客总数，即可得到平均排队时间，向下取整并输出结果

代码实现

结点类（node）

首先是队列的结点设计，可以设计出两个结构体，一个结构体 Node 表示结点，其中包含有 data 域和 next 指针，如下图：


其中 data 表示数据，其可以是简单的类型，也可以是复杂的结构体，故采用泛型编程template<typename eT>。next 指针表示，下一个的指针，其指向下一个结点，通过 next 指针将各个结点链接。结点类还有构造函数，在创建结点时可以进行初始化，

  1. template<typename eT>
  2. class node {
  3. public:
  4. 	eT data;
  5. 	node* next;
  6. 	node(const eT& data_, node<eT>* next_ = NULL)
  7. 	{
  8. 		data = data_;
  9. 		next = next_;
  10. 	}
  11. 	node() : next(NULL) {}
  12. 	~node() {}
  13. };
自定义队列（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 也置为空。

最后释放原头部节点的内存，并返回其值。

  1. template<typename eT>
  2. class linkQueue{
  3. public:
  4. 	node<eT>* front, * tail;
  5. public:
  6. 	linkQueue() { front = tail = NULL; }
  7. 	~linkQueue() {
  8. 		node<eT>* tmp;
  9. 		while (front != NULL) {
  10. 			tmp = front;
  11. 			front = front->next;
  12. 			delete tmp;
  13. 		}
  14. 	}
  15. 	bool isEmpty() { return front == NULL; }
  16. 	void enQueue(const eT& x) {
  17. 		if (tail == NULL)
  18. 			front = tail = new node<eT>(x);
  19. 		else {
  20. 			tail->next = new node<eT>(x);
  21. 			tail = tail->next;
  22. 		}
  23. 	}
  24. 	eT deQueue() {
  25. 		node<eT>* tmp = front;
  26. 		eT value = front->data;
  27. 		front = front->next;
  28. 		if (front == NULL) tail = NULL;
  29. 		delete tmp;
  30. 		return value;
  31. 	}
  32. };
优先级队列（priorityQueue）

与自定义队列（linkQueue）相同，采用泛型编程，其中 eT 是模板参数，代表队列中元素的类型。front 和 tail 分别是指向队列前端和尾端的指针，用于操作队列中的元素。

同样地，优先级队列（priorityQueue）与自定义队列（linkQueue）的初始化，判断非空，出队操作基本相同，主要不同点在于入队操作。

成员函数 enQueue

enQueue 函数用于向队列尾部添加一个新元素。如果队列为空（即 tail 为空），则创建一个新节点，将 front 和 tail 都指向该节点。如果队列非空，则寻找较大元素的前继结点进行插入操作，以保持队列的有序性。

  1. template <typename eT>
  2. class priorityQueue {
  3. public:
  4. 	node<eT>* front, * tail;
  5. 	priorityQueue() { front = tail = NULL; }
  6. 	~priorityQueue() {
  7. 		node<eT>* tmp;
  8. 		while (front != NULL) {
  9. 			tmp = front;
  10. 			front = front->next;
  11. 			delete tmp;
  12. 		}
  13. 	}
  14. 	bool isEmpty() { return front == NULL; }
  15. 	eT deQueue() {
  16. 		node<eT>* tmp = front;
  17. 		eT value = front->data;
  18. 		front = front->next;
  19. 		if (front == NULL) tail = NULL;
  20. 		delete tmp;
  21. 		return value;
  22. 	}
  23. 	void enQueue(const eT& x) {
  24. 		if (tail == NULL)
  25. 			front = tail = new node<eT>(x);
  26. 		else {
  27. 			node<eT>* p;
  28. 			if (x < front->data)
  29. 			{
  30. 				p = new node<eT>(x, front);  front = p;
  31. 			}
  32. 			else {
  33. 				p = front;
  34. 				while (p->next != NULL && p->next->data < x) p = p->next;
  35. 				if (p->next == NULL)
  36. 				{
  37. 					tail->next = new node<eT>(x);
  38. 					tail = tail->next;
  39. 				}
  40. 				else  p->next = new node<eT>(x, p->next);
  41. 			}
  42. 		}
  43. 	}
  44. };

模拟银行排队系统（simulator）

成员变量

1.noOfServer：表示银行柜台的数量。

2.customNum：表示顾客的数量。

3.arrivalTimeList：存储每位顾客到达银行的时间。

4.serviceTimeList：存储每位顾客所需的服务时间。

内部结构体 eventT

1.用于描述事件，包括事件发生时间 time 和事件类型 type（0 表示到达，1 表示离开）。

2.重载了小于操作符，以便将事件按照发生时间进行排序。

  1. class simulator {
  2. 		int noOfServer;
  3. 		int customNum;
  4. 		int* arrivalTimeList;
  5. 		int* serviceTimeList;
  6. 		struct eventT
  7. 		{
  8. 			int time; //事件发生时间
  9. 			int type; //事件类型。0 为到达，1 为离开
  10. 			bool operator<(const eventT& e) const { return time < e.time; }
  11. 		};
  12. };
构造函数和析构函数

构造函数从标准输入中读取柜台数、顾客数以及每位顾客的到达时间和服务时间，然后分配内存给 arrivalTimeList 和 serviceTimeList，分别用这两个数组储存每位顾客的到达时间和服务时间

析构函数释放动态分配的内存，防止内存泄漏

  1. public:
  2. 		simulator() {
  3. 			//std::cout << "请输入柜台数：";
  4. 			std::cin >> noOfServer;
  5. 			//std::cout << "请输入模拟的顾客数：";
  6. 			std::cin >> customNum;
  7. 			arrivalTimeList = new int[customNum];
  8. 			serviceTimeList = new int[customNum];
  9. 			for (int i = 0; i < customNum; i++) {
  10. 				std::cin >> arrivalTimeList[i];
  11. 			}
  12. 			for (int i = 0; i < customNum; i++) {
  13. 				std::cin >> serviceTimeList[i];
  14. 			}
  15. 		}
  16. 		~simulator() {
  17. 			delete arrivalTimeList;
  18. 			delete serviceTimeList;
  19. 		}
成员函数avgWaitTime

该函数用来模拟顾客排队，到达和离开的过程，并且计算出平均等待时间。在该函数中我们需要用自定义队列（linkQueue）来存储等待的顾客事件和顾客的服务时间，并且用优先级队列（priorityQueue）存储顾客到达和离开的事件。

1.定义变量并进行初始化

变量表示的内容已注释

  1. int serverBusy = 0; // 记录当前服务中的柜台数量
  2. int serviceTime = 0; // 记录当前服务所需时间
  3. int currentTime = 0; // 记录当前时间
  4. int totalWaitTime = 0; // 记录总的等待时间
  5. linkQueue<eventT> waitQueue; // 等待队列，存储等待的顾客事件
  6. priorityQueue<eventT> customerQueue; // 顾客队列，存储到达和离开的顾客事件
  7. linkQueue<int> serviceTimeQueue; // 服务时间队列，存储顾客的服务时间
  8. eventT currentEvent; // 当前事件
2.生成初始事件队列
  1. for (int i = 0; i < customNum; ++i) {
  2.     currentEvent.type = 0;
  3.     currentTime = arrivalTimeList[i]; // 每个顾客的到达时刻
  4.     currentEvent.time = currentTime;
  5.     customerQueue.enQueue(currentEvent); // 将顾客到达事件加入到顾客队列中
  6.     serviceTimeQueue.enQueue(serviceTimeList[i]); // 将顾客的服务时间加入到服务时间队列中
  7. }
3.模拟顾客到达和离开的过程

（1）用while循环不断取出顾客队列，直到顾客队列为空，即所有顾客都已经离开银行。从顾客队列中取出事件，并将其赋值给 currentEvent，将当前时间更新为当前事件的发生时间，即顾客到达或离开的时间。

（2）根据事件类型进行处理

a.顾客到达

如果有空闲的柜台，则顾客直接前往柜台处理业务，将当前事件的结束时间继续存入顾客队列，即顾客离开；如果所有柜台都忙碌，则顾客加入等待队列。

b.顾客离开

如果等待队列不为空，则从等待队列中取出顾客，并计算顾客等待的时间；如果等待队列为空，则只需更新柜台的繁忙状态。

  1. while (!customerQueue.isEmpty()) {
  2.     currentEvent = customerQueue.deQueue(); // 取出顾客队列中的事件
  3.     currentTime = currentEvent.time; // 更新当前时间
  4.     switch (currentEvent.type) {
  5.         case 0: // 顾客到达事件
  6.             if (serverBusy < noOfServer) { // 如果有空闲的柜台
  7.                 serverBusy++;
  8.                 currentEvent.time = currentTime + serviceTimeQueue.deQueue(); // 计算顾客服务结束时间
  9.                 currentEvent.type = 1; // 设置事件类型为离开
  10.                 customerQueue.enQueue(currentEvent); // 将离开事件加入到顾客队列中
  11.             } else { // 如果所有柜台都忙碌
  12.                 waitQueue.enQueue(currentEvent); // 将顾客加入等待队列
  13.             }
  14.             break;
  15.         case 1: // 顾客离开事件
  16.             if (!waitQueue.isEmpty()) { // 如果等待队列不为空
  17.                 serverBusy--;
  18.                 currentEvent = waitQueue.deQueue(); // 取出等待队列中的顾客事件
  19.                 totalWaitTime += currentTime - currentEvent.time; // 计算等待时间
  20.                 currentEvent.time = currentTime + serviceTimeQueue.deQueue(); // 计算顾客服务结束时间
  21.                 currentEvent.type = 1; // 设置事件类型为离开
  22.                 customerQueue.enQueue(currentEvent); // 将离开事件加入到顾客队列中
  23.             } else {
  24.                 serverBusy--;
  25.             }
  26.             break;
  27.         default:
  28.             break;
  29.     }
  30. }
4.返回平均等待时间
return totalWaitTime / customNum; // 返回平均等待时间

完整代码

  1. #include<iostream>
  2. #include<stdlib.h>
  3. #include<queue>
  4. using namespace std;
  5. template<typename eT>
  6. class node {
  7. public:
  8. 	eT data;
  9. 	node* next;
  10. 	node(const eT& data_, node<eT>* next_ = NULL)
  11. 	{
  12. 		data = data_;
  13. 		next = next_;
  14. 	}
  15. 	node() : next(NULL) {}
  16. 	~node() {}
  17. };
  18. template<typename eT>
  19. class linkQueue{
  20. public:
  21. 	node<eT>* front, * tail;
  22. public:
  23. 	linkQueue() { front = tail = NULL; }
  24. 	~linkQueue() {
  25. 		node<eT>* tmp;
  26. 		while (front != NULL) {
  27. 			tmp = front;
  28. 			front = front->next;
  29. 			delete tmp;
  30. 		}
  31. 	}
  32. 	bool isEmpty() { return front == NULL; }
  33. 	void enQueue(const eT& x) {
  34. 		if (tail == NULL)
  35. 			front = tail = new node<eT>(x);
  36. 		else {
  37. 			tail->next = new node<eT>(x);
  38. 			tail = tail->next;
  39. 		}
  40. 	}
  41. 	eT deQueue() {
  42. 		node<eT>* tmp = front;
  43. 		eT value = front->data;
  44. 		front = front->next;
  45. 		if (front == NULL) tail = NULL;
  46. 		delete tmp;
  47. 		return value;
  48. 	}
  49. };
  50. template <typename eT>
  51. class priorityQueue {
  52. public:
  53. 	node<eT>* front, * tail;
  54. 	priorityQueue() { front = tail = NULL; }
  55. 	~priorityQueue() {
  56. 		node<eT>* tmp;
  57. 		while (front != NULL) {
  58. 			tmp = front;
  59. 			front = front->next;
  60. 			delete tmp;
  61. 		}
  62. 	}
  63. 	bool isEmpty() { return front == NULL; }
  64. 	eT deQueue() {
  65. 		node<eT>* tmp = front;
  66. 		eT value = front->data;
  67. 		front = front->next;
  68. 		if (front == NULL) tail = NULL;
  69. 		delete tmp;
  70. 		return value;
  71. 	}
  72. 	void enQueue(const eT& x) {
  73. 		if (tail == NULL)
  74. 			front = tail = new node<eT>(x);
  75. 		else {
  76. 			node<eT>* p;
  77. 			if (x < front->data)
  78. 			{
  79. 				p = new node<eT>(x, front);  front = p;
  80. 			}
  81. 			else {
  82. 				p = front;
  83. 				while (p->next != NULL && p->next->data < x) p = p->next;
  84. 				if (p->next == NULL)
  85. 				{
  86. 					tail->next = new node<eT>(x);
  87. 					tail = tail->next;
  88. 				}
  89. 				else  p->next = new node<eT>(x, p->next);
  90. 			}
  91. 		}
  92. 	}
  93. };
  94. class simulator {
  95. 		int noOfServer;
  96. 		int customNum;
  97. 		int* arrivalTimeList;
  98. 		int* serviceTimeList;
  99. 		struct eventT
  100. 		{
  101. 			int time; //事件发生时间
  102. 			int type; //事件类型。0 为到达，1 为离开
  103. 			bool operator<(const eventT& e) const { return time < e.time; }
  104. 		};
  105. 	public:
  106. 		simulator() {
  107. 			//std::cout << "请输入柜台数：";
  108. 			std::cin >> noOfServer;
  109. 			//std::cout << "请输入模拟的顾客数：";
  110. 			std::cin >> customNum;
  111. 			arrivalTimeList = new int[customNum];
  112. 			serviceTimeList = new int[customNum];
  113. 			for (int i = 0; i < customNum; i++) {
  114. 				std::cin >> arrivalTimeList[i];
  115. 			}
  116. 			for (int i = 0; i < customNum; i++) {
  117. 				std::cin >> serviceTimeList[i];
  118. 			}
  119. 		}
  120. 		~simulator() {
  121. 			delete arrivalTimeList;
  122. 			delete serviceTimeList;
  123. 		}
  124. 		int avgWaitTime() {
  125. 			int serverBusy = 0;
  126. 			int serviceTime = 0;
  127. 			int currentTime = 0;
  128. 			int totalWaitTime = 0;
  129. 			linkQueue<eventT> waitQueue;
  130. 			priorityQueue<eventT> customerQueue;
  131. 			linkQueue<int> serviceTimeQueue;
  132. 			eventT currentEvent;
  133. 			//生成初始的事件队列
  134. 			int i;
  135. 			for (i = 0; i < customNum; ++i)
  136. 			{
  137. 				currentEvent.type = 0;
  138. 				currentTime = arrivalTimeList[i];//每个顾客的到达时刻
  139. 				currentEvent.time = currentTime;
  140. 				customerQueue.enQueue(currentEvent);
  141. 				serviceTimeQueue.enQueue(serviceTimeList[i]);//每个顾客的服务时间
  142. 			}
  143. 			while (!customerQueue.isEmpty())
  144. 			{
  145. 				currentEvent = customerQueue.deQueue();
  146. 				currentTime = currentEvent.time;
  147. 				switch (currentEvent.type)
  148. 				{
  149. 				case 0:					
  150. 					if (serverBusy < noOfServer)
  151. 					{
  152. 						serverBusy++;
  153. 						currentEvent.time = currentTime + serviceTimeQueue.deQueue();
  154. 						currentEvent.type = 1;
  155. 						customerQueue.enQueue(currentEvent);
  156. 					}
  157. 					else {
  158. 						waitQueue.enQueue(currentEvent);
  159. 					}
  160. 					break;
  161. 				case 1:
  162. 				{
  163. 					if (waitQueue.isEmpty() == 0)
  164. 					{
  165. 						serverBusy--;
  166. 						currentEvent = waitQueue.deQueue();
  167. 						totalWaitTime = totalWaitTime + currentTime - currentEvent.time;
  168. 						currentEvent.time = currentTime + serviceTimeQueue.deQueue();
  169. 						currentEvent.type = 1;
  170. 						customerQueue.enQueue(currentEvent);
  171. 					}
  172. 					else serverBusy--;
  173. 					break;
  174. 				}
  175. 				default:break;
  176. 				}
  177. 			}
  178. 			return totalWaitTime / customNum;
  179. 		}
  180. 	};
  181. 	int main()
  182. 	{
  183. 		simulator sim;
  184. 		cout << sim.avgWaitTime() <<endl;
  185. 		return 0;
  186. 	}

附录

分类专栏

链接：

​​​​​手把手教数据结构与算法

本专栏上一节

链接：

手把手教数据结构与算法：栈的应用（平衡符号和简单计算器）-CSDN博客

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家小花儿/article/detail/728802
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号