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

约定不等于承诺〃 2022-12-22 15:24 119阅读 0赞

**链队列：队列的链接存储结构称为链队列，通常用单链表表示。其结点的结构与单链表的结点结构相同。根据队列的先进先出特性，为了操作上的方便，设置队头指针指向链队列的头结点，队尾指针指向终端结点。**

**相关博客链接：**[https://blog.csdn.net/weixin\_41987016/article/details/109856416][https_blog.csdn.net_weixin_41987016_article_details_109856416]

**相关博客链接：**[https://blog.csdn.net/weixin\_41987016/article/details/109852812][https_blog.csdn.net_weixin_41987016_article_details_109852812]  
**链队列的实现 ：**

//队列的链接存储结构称为链队列，通常用单链表表示。其结点的结构与单链表的结点结构相同。
    //根据队列的先进先出特性，为了操作上的方便，设置队头指针指向链队列的头结点，队尾指针指向终端结点。
    //链队列的实现
    #include <iostream>
    using namespace std;
    typedef char DataType;
    struct Node{
    	DataType data;
    	Node *next;
    };
    class LinkQueue{
    	public:
    		LinkQueue();//初始化空的链表队列
    		~LinkQueue();//释放链队列的存储空间
    		void EnQueue(DataType x);//入队操作，将元素x出队
    		DataType DeQueue();//出队操作，将队头元素出队 
    		DataType GetHead();//取链队列队头元素
    		int Empty();//判断队列是否为空
    		int GetLen();
    	private:
    		Node *front,*rear;//队头和队尾指针 
    		int Len=0;
    };
    //链队列基本操作的实现本质上是单链表操作的简单化，且时间复杂度均为O(1)
    
    //构造函数----链队列的初始化
    LinkQueue::LinkQueue(){
    	Node *s=nullptr;
    	s=new Node;
    	s->next = nullptr;
    	front=rear=s;//将队头指针和队尾指针都指向头结点s 
    }
    
    //析构函数----链队列的销毁【链队列是动态存储分配，需要释放链队列的所有结点的存储空间】 
    LinkQueue::~LinkQueue(){
    	//front!=nullptr
    	while(front){//释放每一个结点的存储空间 
    		rear=front->next;
    		delete front;
    		front=rear;
    	}
    }
    
    //入队操作----链队列的插入操作只需考虑在链表的尾部进行
    void LinkQueue::EnQueue(DataType x){
    	Node *s=nullptr;
    	s=new Node;
    	s->data=x;s->next=nullptr;
    	rear->next=s;rear=s;//将结点s插入到队尾 
    	Len++;
    } 
    
    //出队操作----链队列的删除操作只需考虑在链表的头部进行 
    DataType LinkQueue::DeQueue(){
    	DataType x;
    	Node *p=nullptr;
    	//if(rear == front) throw "下溢";
    	if(rear == front) cout<< "队列已空，不能出队"<<endl;
    	else{
    		p=front->next;x=p->data;
    		front->next=p->next;
    		//if(!p->next)
    		//if(rear==p) front=rear;
    		if(p->next == nullptr) front=rear;
    		delete p;Len--;
    		return x;
    	}
    } 
    
    //取队头元素
    DataType LinkQueue::GetHead(){
    	return front->next->data;
    }
    
    //判断队列是否为空
    int LinkQueue::Empty(){
    	if(front==rear) return 1;
    	else return 0;
    }
    
    int LinkQueue::GetLen(){
    	return Len;
    }
    //渡船函数
    void ferryboat(int busSNum,int truckSNum){
    	LinkQueue bus{};//定义对象变量bus
    	LinkQueue truck{};//定义对象变量truck
    	LinkQueue ferry{};//定义对象变量ferry
    	int i,j=1,FLen;
    	for (i=0; i<busSNum; i++)                // * 代表客车 
    	{
    		bus.EnQueue('*');        
    	}
    	for (i=0; i<truckSNum; i++)                // # 代表货车 
    	{
    		truck.EnQueue('#');        
    	}
    	cout<<bus.GetLen()<<endl;
    	cout<<truck.GetLen()<<endl;
    	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;
    }

[https_blog.csdn.net_weixin_41987016_article_details_109856416]: https://blog.csdn.net/weixin_41987016/article/details/109856416
[https_blog.csdn.net_weixin_41987016_article_details_109852812]: https://blog.csdn.net/weixin_41987016/article/details/109852812