银行排队模拟（数据结构--队列）

前言

既然你点进了这篇博客，想必大概是大一 ，而且学到了队列，刚好严蔚敏老师的数据结构在讲队列的那章讲了银行排队的模拟，为什么我知道呢？因为我就是,好了谢谢你有耐心地看完我说的“废话”，下面我就简述一下，队列的实现就不讲了，很简单就是一个先进先出。

效果演示：

分析

情景再现:

人们去银行办理业务的时候往往需要排队，而且一个银行往往有几个窗口，不同的人办理的时间一般不一样，不同的人到达的时间也一般不一样
要求:利用队列模拟银行排队的流程 并计算人们在银行逗留的平均时间

问题分析（实际问题的拆分):

1、正常情况下 人们去排队的时候都会选择排在人数最少的队伍
2、不同的人到达银行的时间一般不同
3、不同的人业务办理的时间一般不一样 

从编程的角度分析:

1、两个目的 ：一是模拟排队的过程 二是计算人们在银行逗留的平均时间
2、对于排队过程的模拟，我们知道不同的队伍的业务办理是同时执行的 
所以为了还原实际情况啊 我们的多个队列应该同时处理 但是这就涉及到多线程 鉴于还没有学习多线程 所以我们采用一个事件链表来模拟同时执行，
这个事件表之储存两种事件  一种是进入事件代表一个人进入银行了  一种是离开事件 代表一个人办理完业务离开银行了
3、对于队列  假设银行有四个业务办理窗口 那么我们就创建四个队列 因为你不清楚一条队列 最多有多少人 所以这里选择链式队列比较合适
4、数据的范围 业务办理时间的范围 和银行的关门时刻  两个人进入银行的时间间隔的范围

数据结构分析:

1、事件:事件的标志(用来区分时离开事件 还是进入事件)，事件发生的时间
2、队伍中的人:  进入银行的时间   业务办理的时间   在银行逗留的时间
这里进入银行的时间和业务办理的时间都是随机产生的  要计算的就是在因银行逗留的时

 文章来源地址https://www.toymoban.com/news/detail-770476.html

这个也是我要重点讲的，我看很多博客 或者b站上的视频 就简单地把这个逗留时间看作时进入时刻加上业务办理时间  他们忽略了排队的时间 难道每个人一进来都有空的队伍吗，而且为什么他们错的那么一致，看来是照搬的别人的没有自己的思考

怎么计算这个逗留的时间呢     

1、如果进到队伍的时候我就是第一个那么逗留时间就是业务办理时间 

2、如果前一个客户的离开时间比自己的到达时间早 那么逗留时间就是自己业务办理时间

（既然他都排在我前面了，为什么他还会在我进入之前就走了呢，这里我们只是在实现先后上模拟了排队并不是在物理上模拟了)

3、如果前一个客户的离开时间比自己的到达时间晚 那么逗留时间就是前一个客户离开的时刻加上自己业务办理时间（这两个加起来就是自己的离开时刻，这里像半分钟）然后减去自己的进入时间就是逗留时间

乍一想，是不是觉得很复杂，一条队伍那么长前一个人的离开时间怎么知道呢  其实我们只要追根溯源就行了 从问题最初的形态开始想象  从银行开门开始 这条队伍 排的第一个人 是不是就是就是上面的情况1那么他的逗留时间就是它的业务办理时间 ，那么第二个进入这个队伍的人排在他后面不就知道他前面的人的逗留时间了从而就知道他前面的人的离开时间了吗，一次类推 后面的人的逗留时间不久都知道了吗（有点迭代的意思）

事件处理:

1、事件的顺序：肯定时刻在前面的事件先处理  所以向事件表中插入事件的时候要按照事件发生的先后顺序插入

  2、 处理进入事件: 随机生成这个人办理业务的时间和继他之后下一个进入银行的人和他进入银行的时间间隔然后删除该进入事件  将他后面这个人的进入事件加入按照时间顺序加入到事件表（这是为了模拟不停地有人进来，注意如果他的进入时刻已经超出银行关门的时刻了，就不添加了)  然后将这个人插入到最短队列的末尾 如果这个队列只有他一个人 那么就立马加入他的离开事件  如果加入队伍时他不是第一个那么就不要管  

  3、 处理离开事件: 如果到一个人的离开事件处理了说明他已经办理完业务了
   说明他此时在队首  所以将他踢出队列 然后将他的离开事件删除 然后还要开他在的这队还有没有人 如果有人就将他离开队伍之后队首的人的离开事件加入事件表
   

# 代码

代码分为四个部分:1、链表的实现的头文件（学数据结构的时候不可以用现成的，你们老师应该都说过吧）

2、队列的实现的头文件

3、时间处理流程的头文件 

4、测试的源文件

 

1、（这个链表的实现我就直接粘贴之前自己写过的了，有些功能在此情景下用不到，可以删除，这个你们自行把握）

#pragma once
#include<iostream>
using namespace std;
//事件链表
//事件数据结构
typedef struct Thing {
	int begin;//事件发生的时刻
	int type;//事件的类型 -1 表示进入  0 1 2 3表示离开并且分别对应相应的队列
	Thing* next;
	Thing(int a, int b, Thing* n = nullptr) :begin(a), type(b), next(n)
	{};
	Thing() = default;
	friend ostream operator<<(ostream& os, const Thing& a);
};
ostream& operator<<(ostream& os, Thing& a)
{
	os << '[' << a.begin << ',' << a.type << ']';
	return os;
}
//实现事件链表:
class ChainList {
private:
	Thing* head;//头指针
	int length;//长度
public:
	ChainList();//初始化
	bool insert(int begin, int type);//插入 注意这里要按照事件发生时刻的先后顺序插入
	bool Pop();//将处理完的事件删除
	Thing Getfirst();
	int GetLength();//获取长度
	bool IsEmpty();//判空
	void Destroy();//销毁
	void print();//打印所有事件
	~ChainList();//析构
};
inline ChainList::ChainList()
{
	length = 0;
	head = nullptr;
}

inline bool ChainList::insert(int begin, int type)
{
	Thing* thing = new Thing;
	thing->begin = begin;
	thing->type = type;
	thing->next = nullptr;
	if (head == nullptr)
	{
		head = thing;
		++length;
	}
	else //按发生时刻先后插入
	{
		Thing* temp = head;
		Thing* pre = nullptr;
		while (temp)
		{
			if (begin >= temp->begin)
			{
				pre = temp;
				temp = temp->next;
			}
			else
				break;
		}//当循环退出的时候就说明此时的temp的begin>=begin了 或者temp为nullptr 所以我们把thing 插入temp前面
		
			if (temp == head)
			{
				thing->next = temp;
				head = thing;
			}
			else
			{
				pre->next = thing;
				thing->next = temp;
			}

		++length;
	}
	return true;
}

inline bool ChainList::Pop()
{
	if (IsEmpty())
		return false;
	else
	{
		Thing* temp = head;
		head = head->next;
		delete temp;
		length--;
		return true;
	}
}

inline Thing ChainList::Getfirst()
{
	if (!head)
	{
		throw std::out_of_range("The List is empty!");
	}
	else
	{
		Thing a;
		a.begin = head->begin;
		a.type = head->type;
		a.next = nullptr;
		return a;
	}
}

inline int ChainList::GetLength()
{
	return length;
}

inline bool ChainList::IsEmpty()
{
	if (!head)
		return true;
	return false;
}

inline void ChainList::Destroy()
{
	Thing* temp = head;
	Thing* temp1;
	while (temp)
	{
		temp1 = temp;
		temp = temp->next;
		delete temp1;
	}
	length = 0;
}

inline void ChainList::print()
{
	Thing* temp = head;
	cout << "事件表:";
	while (temp)
	{
		cout << *temp << " ";
		temp = temp->next;
	}
	cout << endl;
}


inline ChainList::~ChainList()
{
	if (head)
		Destroy();
}

2、

#pragma once
#include<iostream>
using namespace std;
struct Client {
	int start;//进入银行时间
	int process;//办理业务的时间
	int all=0;//逗留时间 默认为0  要计算逗留的时间只需要知道这个客户离开的时间就行了 要想知道而离开的时间有和前一个人离开的时刻有关
	friend ostream operator<<(ostream& os, const Client& a);
	Client(int a, int b) :start(a), process(b) 
	{};
	Client() = default;
};
ostream& operator<<(ostream& os, Client& a)
{
	os <<'[' << a.start<<','<< a.process<<']';
	return os;
}

struct Node {
	Client data;//数据
	Node* next;//指向下一个结点
};
class Myqueue {
private:
	Node* head;//头指针
	Node* tail;//尾指针
	int length;//队列长度，元素个数
public:
	Myqueue();//构造函数 完成初始化
	int GetLength();//获取队列的长度
	bool IsEmpty();//判断队列是否为空
	bool Push(Client elem);//从后面插入元素
	Client Pop();//从前面踢出元素
	Client FirstElem();//返回第一个元素
	void Destroy();//销毁队列
	void print();
	~Myqueue();
};

inline Myqueue::Myqueue()
{
	head = tail = nullptr;
	length = 0;
}


inline int Myqueue::GetLength()
{
	return length;
}

inline bool Myqueue::IsEmpty()
{
	if (head == nullptr)
		return true;
	return false;
}


inline bool Myqueue::Push(Client elem)
{
	Node* newNode =  new Node;
	newNode->data = elem;
	newNode->next = nullptr;
	// 如果队列为空，新节点既是队头也是队尾
	if (IsEmpty()) {
		head = newNode;
		tail = newNode;
		head->data.all = elem.process;//如果该队列没有人 那么进入的这个人的逗留时间就是办理业务的时间
		length++;
		return true;
	}
	// 如果队列不为空，新节点成为队尾
	else {
		int pre_depart = tail->data.all+tail->data.start;//保存插入之前最后一个客户的离开时刻
		tail->next = newNode;
		tail = newNode;
		if (pre_depart <= tail->data.start)
		{
			tail->data.all = tail->data.process;//如果前一个客户的离开时间比自己的到达时间早 那么逗留时间就是业务办理时间
		}
		else
		{
			tail->data.all = pre_depart + tail->data.process - tail->data.start;
		}
		length++;
		return true;
	}
}


inline Client Myqueue::Pop()
{
	if (IsEmpty())
	{
		throw std::out_of_range("Queue is empty!");
	}
	Client temp = head->data;
	Node* node = head;
	head = head->next;
	delete node;
	length--;
	return temp;
}


inline Client Myqueue::FirstElem()
{
	if (IsEmpty())
	{
		throw std::out_of_range("Queue is empty!");
	}
	return head->data;
}




inline void Myqueue::Destroy()
{
	Node* temp = head;
	while (head != nullptr)
	{
		head = head->next;
		if (temp)
			delete temp;
		temp = this->head;
	}
	length = 0;
	head = tail = nullptr;
}

inline void Myqueue::print()
{
	Node* temp = head;
	while (temp)
	{
		cout << temp->data << " ";
		temp = temp->next;
	}
	cout << endl;
}

inline Myqueue::~Myqueue()
{
	//如果没有手动销毁队列，那么就交给析构函数来做善后工作
	if (head)
		Destroy();
}

3、

#pragma once
#include"ChainList.h"
#include"myqueue.h"
#include<windows.h>
#include<ctime>
static int processTime()//办理业务的时间
{
	static bool seedInitialized = false;//只初始化一次随机数种子
	if (!seedInitialized) {
		srand(time(nullptr));
		seedInitialized = true;
	}
	return (5 + rand() % 21);
}
static int intervalTime()//下一个客户进入的时刻和该用户进入时刻的间隔时间
{
	static bool seedInitialized1 = false;
	if (!seedInitialized1) {
		srand(time(nullptr));
		seedInitialized1 = true;
	}
	return rand() % 11;
}

class imitation {
private:
	ChainList list;//时间表;
	Myqueue que[4];//四个队列
	double total;//总逗留时间
	int cnum;//总客户数
	int end;//银行下班时间
public:
	imitation();
	int minque();//返回人数最少的队列的编号
	void deal();//事件处理函数
	void run();//模拟全过程控制函数
};
inline  imitation::imitation()
{
	list.insert(0, -1);//先加入第一个人进入银行的事件
	cnum = 1;
	total = 0;
	cout << "请输入银行下班时间:";
	cin >> end;
}
inline int imitation::minque()
{
	int min = 0;//人数最少的队列的编号
	for (int i = 1; i < 4; i++)
	{
		if (que[i].GetLength() < que[min].GetLength())
			min = i;
	}
	return min;
}
inline void imitation::deal()
{
	int a = list.Getfirst().begin;
	int b = list.Getfirst().type;
	list.Pop();//踢出事件表

	if (b == -1) //进入事件
	{
		int m = processTime();//办理时间
		int n = intervalTime();//间隔时间
		Client c(a, m);
		int min = minque();
		if (n + a < end)
		{
			list.insert(n + a, -1);//加入事件表
			cnum++;
		}
		if (que[min].IsEmpty())
		{
			list.insert(a + m, min);//插入离开事件
		}

		que[min].Push(c);//开始排队
		
	}
	else//离开事件
	{
		total += que[b].FirstElem().all;
		que[b].Pop();
		if (!que[b].IsEmpty())//如果队列不为空的话 为队首客户向事件表中加入离开事件
		{
			list.insert(que[b].FirstElem().start + que[b].FirstElem().process, b);//插入离开事件
		}
	}
}
inline void imitation::run()
{
	while (!list.IsEmpty())
	{
		system("cls");
		list.print();
		cout << "--------------------------------------------------" << endl;
		for (int i = 0; i < 4; i++)
		{
			cout << "第" << i + 1 << "个队列数据:";
			que[i].print();
			cout << "--------------------------------------------------" << endl;
		}
		deal();
		Sleep(100);//暂停1毫秒
	}
	system("cls");
	cout << "总接待客户数为:" << cnum << endl;
	cout << "客户平均逗留时间:" << total * 1.0 / cnum;
}

4、

#include"myqueue.h"
#include<iostream>
using namespace std;
#include"银行离散事件模拟.h"
int main()
{
	imitation im;
	im.run();
	return 0;
}

//最后，写文章不易，要是觉得对你帮助的话，可以点个赞吗，这是我向外输出的动力，谢谢啦！！！

到了这里，关于银行排队模拟（数据结构--队列）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！