2023年6月22日发(作者：)

数据结构之队列—轮渡模拟⼀、简单介绍　　　　这是在博客园潜⽔⼏个⽉第⼀次开始想要写点东西，⼀是记录⾃⼰的学习过程，⼆是和⼤家分享同时接受⼤家的指正，再者可以多交⼀些朋友，我微博地址在公告栏⾥。。。。这是最近上数据结构时的练习题，⾸先是队列的实现，再⽤队列去模拟解决⼀个实际问题——轮渡模拟。⼆、问题分析　　　2.1 问题描述：轮渡模拟：有⼀个渡⼝，每条渡船能⼀次性装载10辆汽车过河，车辆分为客车和货车两类。上渡轮有如下规定：同类汽车先到先上船，客车先于货车上船，轮渡每10分钟⼀班。模拟⼀⼩时内汽车上渡轮的过程。汽车：包含⼀个汽车类型属性，⼀个到达时间属性，到达时间随机产⽣。轮渡：包含⼀个装车情况的属性，⼀个出发时间的属性。输出：1⼩时内六班轮渡的装车情况。2.2 实现说明：轮渡不管是否装满10秒钟⼀班，⼀共进⾏6班共⼀分钟；期间的汽车到来时间及类型是随机的;初始当前已有⼀班渡轮停靠在渡⼝；　　　　当拿到这个问题时，分析问题后觉得要⽐较好的使各个事件不相互影响地模拟轮渡情况，需要⽤到多线程，但因为以前都是在Linux环境下编程，没有在Windows上实现过多线程编程，所以也不知道在具体实现中是否会存在什么问题。实现时在主函数中创建了三个线程：其中两个线程分别是客车和货车随机产⽣(到达)，并携带时间信息进⼊到相应的队列；还有⼀个是⽤于做计时器⽤。

三、实现代码3.1测试#include #include #include #include #include #include "sqQueue.h" //包含⾃定义队列类using namespace std;#define MAX_NUM 10 //渡轮最⼤装载数量typedef enum{PassengerCar, FreightCar}CarType; //汽车类型typedef struct

{ CarType type; //汽车类型 time_t arriveTime; //汽车到达时间}Car;typedef struct

{ int size; //渡轮当前装载汽车数量 time_t startTime; //渡轮出发时间}Ferry;SqQueue pCarQueue(61); //定义队列，⽤于存放客车的队列,模拟⼀分钟最多60辆汽车SqQueue fCarQueue(61); //定义队列，⽤于存放货车的队列int startTimeFlag = 0; //定义渡轮出发标志int countLength = 6; //计数长度unsigned _stdcall threadCountFun(void* pArguments){ while (countLength > 0) { Sleep(10000); //计数10秒 startTimeFlag = 1; countLength--; } return 0;}

bool ferryFun() //函数：处理渡轮到达，装载，出发等{ int count = 1; //渡轮计数 while (count<7) { Ferry ferry; = 0; //初始轮渡装载汽车数量 while(1) { if ( < 10 ) //轮渡未满 { if (!y_SqQueue() && !y_SqQueue() && _SqQueue().arriveTime == _SqQueue().arriveTime) { //当两队列对头汽车到达时间相同时，客车先上船 cout<<"⼀辆客车上船...其到达渡⼝时间："; cout<

} return true;}unsigned _stdcall threadPCarFun(void* pArguments) //客车处理函数{ srand(time(0));

while (!_SqQueue()) { Car car; if (1 == rand()%14) //1(客车) { = PassengerCar; time(&Time); //记录到达时间 _SqQueue(car); // cout<<"P: "<

} return 0;}unsigned _stdcall threadFCarFun(void* pArguments) //货车处理函数{ srand(time(0));

while (!_SqQueue()) { Car car; if(2 == rand()%14) //2(货车) { = FreightCar; time(&Time); //记录到达时间 _SqQueue(car); // cout<<"H: "<

} //测试这个频率能看到装满和没装满的情况 return 0;}int main(int argc, char** argv){

HANDLE hThread_P, hThread_F, hThread_Count; unsigned int threadID_P, threadID_F, threadID_Count; hThread_P = (HANDLE) _beginthreadex(NULL, 0, &threadPCarFun, NULL, 0, &threadID_P); hThread_F = (HANDLE) _beginthreadex(NULL, 0, &threadFCarFun, NULL, 0, &threadID_F); hThread_Count = (HANDLE) _beginthreadex(NULL, 0, &threadCountFun, NULL, 0, &threadID_Count);

ferryFun(); cout<<"n汽车排队中....直⾄队满..."<

return 0;}运⾏结果：

3.2以下是⾃⼰⽤模板类实现的循环队列:⾃定义队列类(sqQueue.h)#ifndef SQQUEUE_H#define SQQUEUE_H#define Q_MAX_LENGTH 100template class SqQueue{public: SqQueue(int length_SqQueue = Q_MAX_LENGTH); virtual ~SqQueue(); bool push_SqQueue(const T& e); bool pop_SqQueue(); bool isEmpty_SqQueue(); bool isFull_SqQueue(); T& top_SqQueue(); const T& top_SqQueue()const; int size_SqQueue(); void display_SqQueue();private: T* data; int front; int rear; int length;};/*构造函数，初始化队列*/template SqQueue::SqQueue(int length_SqQueue){ data = new T[length_SqQueue]; front = rear = 0; length = length_SqQueue;}/*析构函数*/template SqQueue::~SqQueue(){ delete []data;}/*判空操作 */template bool SqQueue::isEmpty_SqQueue(){ if (front == rear) return true; else return false;}/*判满操作*/template bool SqQueue::isFull_SqQueue(){ if ((rear+1)%length == front) return true; else return false;}/*⼊队操作*/template bool SqQueue::push_SqQueue(const T& e){ if (!isFull_SqQueue()) { data[rear] = e; rear = (rear+1)%length; return true; } return false;}/*出队操作*/template bool SqQueue::pop_SqQueue(){ if (!isEmpty_SqQueue()) { front = (front+1)%length; } return false;}/*得到对头元素*/template T& SqQueue::top_SqQueue(){ if (!isEmpty_SqQueue()) { return data[front]; }// cout<<"队列空"<const T& SqQueue::top_SqQueue()const{ if (!isEmpty_SqQueue()) { return data[front]; }// cout<<"队列空"<int SqQueue::size_SqQueue(){ return (rear-front+length)%length;}/*遍历打印操作*/template void SqQueue::display_SqQueue(){ int i = front; while (i != rear) { std::cout<