C++数据结构---循环队列结构实现应用场景排队问题

男娘i 2022-12-22 13:29 116阅读 0赞

**实验三 队列**

**1** **．实验目的**

（ 1 ）理解队列的定义、特点及与线性表的异同；

（ 2 ）熟悉队列的组织方法，队列满、队列空的判断条件及其描述；

（ 3 ）掌握队列的基本操作（入队、出队等）。

**2** **．实验内容**

（ 1 ）假设以数组  sequ\[MaxSize\] 存放环形队列的元素，同时  Rear  和  Len  分别指示

环形队列中队尾元素的位置和内含元素的个数。设计相应的入队和出队算法。

（ 2 ）某汽车轮渡口，过江渡船每次能载  10  辆车过江。过江车辆分别为客车类和 货车类，上船有如下规定：同类车先到先上船，客车先于货车上渡船，且每上 4  辆客

车，才允许上一辆货车；若等待客车不足  4  辆则以货车代替；若无货车等待则允许客车都上船。设计一个算法模拟渡口管理。

**3** **．解题思路**

**（1）解决问题的关键在于以下两点：如何使用软件的方法构造环形队列和如何通过 Rear 和 Len 来确定队头元素所在的位置。对于第 1 点，通过模运算来实现，即**

**Rear=(Rear+1)%MaxSize；第 2 个问题，当队尾元素的下标大于队头元素的下标时，如图 3-1 所示，显然，Rear-Len+1即为队头元素的下标；当队尾元素的下标小于队头**

**元素的下标时，如图 3-2 所示，此时队头元素的下标为：(Rear+MaxSize)-Len+1；为 使 这 两 种 情 况 统 一 处 理 ， 采 用 以 下 表 达 式 来 计 算 队 头 元 素 的 下 标 ：**

**((Rear+MaxSize)-Len+1)%MaxSize。队空和队满的问题通过 Len 的值即可判断出， Len=0 显然是队空，Len=MaxSize 则为队满。**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70][]

**循环队列算法描述（C++ ）如下：**

#include <iostream>
    using namespace std;
    const int MaxSize = 10;//10是示例性数据 
    typedef int DataType;
    class CirQueue
    {
    	public:
    		CirQueue();//构造函数，初始化空队列
    		~CirQueue();//析构函数
    		void EnQueue(DataType x);//入队操作，将元素x入队
    		DataType DeQueue();//出队操作，将队头元素出队
    		DataType GetHead();//取出队头元素（并不删除）
    		int Empty();//判断队列是否为空
    		int GetLen();//返回队列的长度 
    	private:
    		DataType data[MaxSize];//存放队列元素的数组
    		int front,rear;//游标，队头和队尾指针 
    		int Len=0; 
    };
    
    //构造函数----循环队列的初始化
    CirQueue::CirQueue(){
    	rear=front=MaxSize-1;
    }
    
    //析构函数----循环队列的销毁
    CirQueue::~CirQueue(){
    	
    }
    
    //入队操作 
    void CirQueue::EnQueue(DataType x){
    	if(Len==MaxSize) cout<<"队列已满，不能入队"<<endl;
    	else{
    		rear = (rear+1)%MaxSize;//队尾指针在循环意义下加1
    		data[rear]=x;//在队尾处插入元素 
    		Len++;//长度加1 
    	}
    } 
    
    //出队操作
    DataType CirQueue::DeQueue(){
    	if(Len==0) cout<< "队列已空，不能出队"<<endl;
    	else{
    		front=((rear+MaxSize)-Len+1)%MaxSize;
    		Len--;//长度减1 
    		return data[front];//返回出队前的队头元素 
    	}
    } 
    
    //取队头元素
    DataType CirQueue::GetHead(){
    	//if(rear == front) throw "下溢";
    	if(Len==0) cout<< "队列已空，不能出队"<<endl;
    	else{
    		return data[rear-Len+1];//注意不修改队头指针 
    	}
    } 
    
    //判断队列是否为空
    int CirQueue::Empty(){
    	if(front == rear) return 1;
    	else return 0;
    }
    
    //返回队列长度
    int CirQueue::GetLen(){
    	return Len;
    } 
    int main(){
    	int x;
    	CirQueue Q{};//定义对象变量Q
    	cout<<"对5和8执行入队操作,";
    	Q.EnQueue(5);
    	Q.EnQueue(8);
    	cout<<"当前队列的长度为"<<Q.GetLen()<<endl;
    	cout<<"当前队头元素为："<<Q.GetHead()<<endl;//输出队头元素5
    	try{
    		x=Q.DeQueue();
    		cout<<"执行一次出队操作，出队元素是："<<x<<endl;//输出出队元素5 
    	} catch(char *str){
    		cout<<str<<endl;
    	}
    	cout<<"当前队列的长度为"<<Q.GetLen()<<endl;
    	cout<<"当前队头元素为："<<Q.GetHead()<<endl;//输出队头元素8
    	try{
    		cout<<"请输入入队元素：";
    		cin>>x;
    		Q.EnQueue(x);
    	} catch(char *str){
    		cout<<str<<endl;
    	}
    	cout<<"当前队列的长度为"<<Q.GetLen()<<endl;
    	if(Q.Empty()==1) cout<<"队列为空"<<endl;
    	else cout<<"队列非空"<<endl;//队列有2个元素，输出队列非空 
    	return 0;
    }

**（2）建立 3 个队列，分别为客车队列 bus，货车队列 truck 和渡船队列 ferry，设 置 3 个变量标识已上渡船的客车数量 busNum、货车数量 truckNum 和总数量 totalNum。** **渡口管理示意图（某个状态）如图 3-3 所示，图中以\*代表客车，\#代表货车。**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 1][]

> **当车辆到达渡口时，客车入 bus 队列，货车入 truck 队列。当上渡船的汽车数量 totalNum 小于 10 时，循环扫描客车队列和货车队列，若 busNum<4 且客车队列不为** 
> 
> **空，将客车队列的队头汽车出队上船，busNum++，totalNum++；若 busNum<4 且客车队列为空但货车队列不为空，将货车队列的队头汽车出队上船，置 busNum=0，** 
> 
> **truckNum++，totalNum++；若 busNum>=4，且货车队列不为空，将货车队列的队头 汽车出队上渡船，置 busNum＝0，totalNum++，truckNum++；若客车队列不空**
> 
> **但货车队列为空，则将客车队列的队头汽车出队上渡船，置 totalNum++，busNum++，truckNum ＝0；若客车队列和货车队列都为空时等待车辆的到达。**
> 
>

**渡口管理算法描述（伪代码）如下：**

> **1．初始化各队列为空，置 totalNum=0，busNum=0，truckNum=0；** 
> 
> **2．输入到达渡口的汽车序列，将客车和货车分别入队；** 
> 
> **3．当 totalNum<MaxSize 时，重复 3.1-3.5；** 
> 
> **     3.1 如果 busNum<4 且客车队列不为空，将客车队列的队头汽车出队上渡船，置 totalNum++，busNum++；** 
> 
> **     3.2 如果 busNum<4 且客车队列为空，但是货车队列不为空，将货车队列的队头汽车出队上渡船，置 totalNum++，truckNum++，busNum=0；** 
> 
> **     3.3 如果 busNum>=4 且货车队列不为空，将货车队列的队头汽车出队上渡船，置 totalNum++，truckNum++，busNum=0；** 
> 
> **     3.4 如果 busNum>=4 且货车队列为空，但客车队列不为空，将各车队列的队头汽车出队上渡船，置 totalNum++，truckNum=0，busNum++；** 
> 
> **     3.5 如果客车队列和货车队列都为空，中止循环；** 
> 
> **4．输出当前客车、货车汽车等待情况和渡船装载汽车情况，算法结束。**

#include <iostream>
    using namespace std;
    const int MaxSize = 100;//10是示例性数据 
    typedef char DataType;
    class CirQueue
    {
    	public:
    		CirQueue();//构造函数，初始化空队列
    		~CirQueue();//析构函数
    		void EnQueue(DataType x);//入队操作，将元素x入队
    		DataType DeQueue();//出队操作，将队头元素出队
    		DataType GetHead();//取出队头元素（并不删除）
    		int Empty();//判断队列是否为空
    		int GetLen();//返回队列的长度 
    		DataType ClearCirQueue();//清空队列 
    	private:
    		DataType data[MaxSize];//存放队列元素的数组
    		int front,rear;//游标，队头和队尾指针 
    		int Len=0; 
    };
    
    //构造函数----循环队列的初始化
    CirQueue::CirQueue(){
    	rear=front=MaxSize-1;
    }
    
    //析构函数----循环队列的销毁
    CirQueue::~CirQueue(){
    	
    }
    
    //入队操作 
    void CirQueue::EnQueue(DataType x){
    	if(Len==MaxSize) cout<<"队列已满，不能入队"<<endl;
    	else{
    		rear = (rear+1)%MaxSize;//队尾指针在循环意义下加1
    		data[rear]=x;//在队尾处插入元素 
    		Len++;//长度加1 
    	}
    } 
    
    //出队操作
    DataType CirQueue::DeQueue(){
    	if(Len==0) cout<< "队列已空，不能出队"<<endl;
    	else{
    		front=((rear+MaxSize)-Len+1)%MaxSize;
    		Len--;//长度减1 
    		return data[front];//返回出队前的队头元素 
    	}
    } 
    
    //取队头元素
    DataType CirQueue::GetHead(){
    	//if(rear == front) throw "下溢";
    	if(Len==0) cout<< "队列已空，不能出队"<<endl;
    	else{
    		return data[rear-Len+1];//注意不修改队头指针 
    	}
    } 
    
    //判断队列是否为空
    int CirQueue::Empty(){
    	if(front == rear) return 1;
    	else return 0;
    }
    
    //返回队列长度
    int CirQueue::GetLen(){
    	return Len;
    } 
    
    DataType CirQueue::ClearCirQueue(){
    	rear=front=0;
    }
    //渡船函数
    void ferryboat(int busSNum,int truckSNum){
    	CirQueue bus{};//定义对象变量bus
    	CirQueue truck{};//定义对象变量truck
    	CirQueue ferry{};//定义对象变量ferry
    	int i,j=1,FLen;
    	for (i=0; i<busSNum; i++)                // * 代表客车 
    	{
    		bus.EnQueue('*');        
    	}
    	for (i=0; i<truckSNum; i++)                // # 代表货车 
    	{
    		truck.EnQueue('#');        
    	}
    	int totalNum,busNum,truckNum;
    	while(bus.GetLen()!=0 || truck.GetLen()!=0){// 如果岸上还有车那么就循环 
    		totalNum=0,busNum=0,truckNum=0;
    		while(totalNum < 10){// 如果船没有满，那么就可以上船 
    			if(busNum < 4 && bus.GetLen()!=0){// 船上的客车没满4辆并且岸上还有客车
    				ferry.EnQueue(bus.DeQueue()); // 那么就上一辆客车
    				totalNum++;busNum++;
    			}
    			else if(busNum < 4 && bus.GetLen()==0 && truck.GetLen()!=0){//船上的客车没满4辆并且岸上没有客车，岸上还有货车 
    				ferry.EnQueue(truck.DeQueue());//那么就上一辆货车
    				totalNum++;truckNum++;
    			}
    			else if(busNum >= 4 && truck.GetLen()!=0){//如果船上已经上了四辆客车并且岸上还有货车
    				ferry.EnQueue(truck.DeQueue());//那么就上一辆货车
    				totalNum++;truckNum++;busNum=0;
    			}
    			else if(busNum >= 4 && truck.GetLen()==0 && bus.GetLen()!=0){//如果船上已经上了四辆客车并且岸上没有货车
    				ferry.EnQueue(bus.DeQueue());//那么就上一辆客车
    				totalNum++;truckNum=0;busNum++;
    			}
    			else if(bus.GetLen()==0 && truck.GetLen()==0){
    				break; 
    			} 
    		}
    		cout<<"第"<<j++<<"趟渡船过江,且船队列的进车总长度："<<ferry.GetLen()<<endl;
    		FLen=ferry.GetLen();
    		for (i=0; i<FLen; i++)           
    		{
    			cout<<ferry.DeQueue()<<" ";        
    		}
    		//ferry.ClearCirQueue();
    		cout<<endl;
    	}
    }
    
    int main(){
    	int busSNum,truckSNum;
    	cout<<"请输入想要渡船入队的客车总数目:"<<endl;
    	cin>>busSNum;
    	cout<<"请输入想要渡船入队的货车总数目:"<<endl;
    	cin>>truckSNum;
    	ferryboat(busSNum,truckSNum);
    	return 0;
    }
    //busSNum=25; truckSNum=5;

实验结果图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 2][]![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 3][]![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 4][]![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 5][]

**我是热爱学习的呵呵哒~如果你觉得文章很棒，对你有帮助的话，可以点赞收藏加关注喔~**

**如果文章有不正确的地方，欢迎交流指正，我将虚心请教~o(>ω<)o**

**我会定期更新文章，继续为您提供优质文章~o(>ω<)o**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70]: /images/20221120/39784864892e411190a2bbcfe38927be.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 1]: /images/20221120/9c25645cc14d4749b97e3bab2907006d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20201120162416266.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20201120162422917.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20201120162429472.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 5]: /images/20221120/fe4840435d974c54b280e8b5aa3282bc.png