当前位置：首页 > news >正文

数据结构C++ 队列——队列的应用

news 来源：原创 2024/4/29 5:41:10

application.h :

1 #pragma once
2 #include "mach.h"
3 
4 //列车车厢重排
5 bool Arrange(int order[], int ordered[], int carNum, int stackNum);
6 
7 //工厂仿真
8 void machineSimulate();

mach.h :

  1 #pragma once
  2 #include "vectorQueue.h"
  3 #include "myExceptions.h"
  4 
  5 
  6 #define DEBUG_INFO 1
  7 
  8 /******************************************************
  9 *                        工序
 10 ******************************************************/
 11 struct task
 12 {
 13     int machine;    //执行该工序的机器
 14     int time;        //完成该该工序所需的时间
 15 
 16     task(int theMachine = 0, int theTime = 0)
 17     {
 18         machine = theMachine;
 19         time = theTime;
 20     }
 21 };
 22 
 23 /******************************************************
 24 *                        任务
 25 ******************************************************/
 26 struct job
 27 {
 28     vectorQueue<task> taskQ;  // 任务的工序
 29     int length;               // 被调度的工序时间之和
 30     int arrivalTime;          // 到达当前队列的时间
 31     int id;                   // 任务标志
 32 
 33     job(int theId = 0)
 34     {
 35         id = theId;
 36         length = 0;
 37         arrivalTime = 0;
 38     }
 39 
 40     void addTask(int theMachine, int theTime)
 41     {
 42         task theTask(theMachine, theTime);
 43         taskQ.push(theTask);
 44     }
 45 
 46     //删除任务的下一道工序，并返回时间
 47     int removeNextTask()
 48     {
 49         int theTime = taskQ.front().time;
 50         taskQ.pop();
 51         length += theTime;
 52         return theTime;
 53     }
 54 };
 55 
 56 /******************************************************
 57 *                        机器
 58 ******************************************************/
 59 struct machine
 60 {
 61     vectorQueue<job*> jobQ;        // 机器的等待处理任务队列
 62     int changeTime;                // 机器的转换状态所用时间
 63     int totalWait;                // 空闲时间
 64     int numTasks;                // 机器处理的工序数量
 65     job* activeJob;                // 机器当前正在处理的任务
 66 
 67     machine()
 68     {
 69         totalWait = 0;
 70         numTasks = 0;
 71         activeJob = NULL;
 72     }
 73 };
 74 
 75 
 76 /******************************************************
 77 *                        事件表
 78 ******************************************************/
 79 class eventList
 80 {
 81 public:
 82     eventList(int theNumMachines, int theLargeTime)
 83     {
 84         if (theNumMachines < 1)
 85             throw illegalParameterValue
 86             ("number of machines must be >= 1");
 87         numMachines = theNumMachines;
 88         finishTime = new int[numMachines + 1];
 89 
 90         // 初始时间，所有机器都空闲
 91         for (int i = 1; i <= numMachines; i++)
 92             finishTime[i] = theLargeTime;
 93     }
 94 
 95     //处理下一项工序的机器
 96     int nextEventMachine()
 97     {
 98         int p = 1;
 99         int t = finishTime[1];
100         //搜索最早完成的机器
101         for (int i = 2; i <= numMachines; i++)
102             if (finishTime[i] < t)
103             {
104                 p = i;
105                 t = finishTime[i];
106             }
107         return p;
108     }
109 
110     //下一项工序的完成时间
111     int nextEventTime(int theMachine)
112     {
113         return finishTime[theMachine];
114     }
115 
116     void setFinishTime(int theMachine, int theTime)
117     {
118         finishTime[theMachine] = theTime;
119     }
120 private:
121     int* finishTime;   // 完成时间数组
122     int numMachines;   // 机器的数量
123 };

application.c pp:

  1 #include <iostream>
  2 #include "vectorQueue.h"
  3 #include "application.h"
  4 
  5 
  6 /*******************************************************************************************
  7 *                                        列车车厢重排
  8 *******************************************************************************************/
  9 
 10 int minCar;                //缓冲轨道上编号最小的车厢
 11 int minCarInStack;        //缓冲轨道上编号最小的车厢所在的轨道号
 12 
 13 bool fromOrderToQueue(int car, vectorQueue<int>* &Queue, int queueNum, int carNum)
 14 {
 15     int bestStack = -1, bestTop = 0;
 16     for (int i = 0; i < queueNum; i++)        //轨道为空
 17     {
 18         if (Queue[i].empty())
 19         {
 20             if (bestStack == -1)
 21                 bestStack = i;
 22         }
 23         else                                //轨道不为空
 24         {
 25             int QueueTop = Queue[i].back();
 26             if (car > QueueTop && QueueTop > bestTop)
 27             {
 28                 bestTop = QueueTop;
 29                 bestStack = i;
 30             }
 31         }
 32     }
 33 
 34     if (-1 == bestStack)
 35         return false;
 36     std::cout << "移动" << car << "号车厢到" << bestStack << "号缓冲轨道" << std::endl;
 37     Queue[bestStack].push(car);        //车厢放入最合适的缓冲轨道内
 38     if (car < minCar)                //更新变量
 39     {
 40         minCar = car;
 41         minCarInStack = bestStack;
 42     }
 43 
 44     return true;
 45 }
 46 
 47 void fromQueueToOrdered(vectorQueue<int>* &Queue, int queueNum, int ordered[], int &nextCar, int carNum)
 48 {
 49     //    std::cout << "nextCar = " << nextCar << std::endl;
 50     int QueueTop = Queue[minCarInStack].front();
 51     Queue[minCarInStack].pop();
 52     ordered[nextCar - 1] = QueueTop;
 53     std::cout << "移动" << minCarInStack<<"缓冲轨道的"<< QueueTop <<"号车厢到出轨道"<< std::endl;
 54     //    nextCar++;
 55 
 56     minCar = carNum + 1;
 57     for (int i = 0; i < queueNum; i++)
 58     {
 59         if (!Queue[i].empty() && Queue[i].front() < minCar)
 60         {
 61             minCar = Queue[i].front();
 62             minCarInStack = i;
 63         }
 64     }
 65     //    std::cout << "minCar = " << minCar << std::endl;
 66 }
 67 
 68 bool Arrange(int order[], int ordered[], int carNum, int queueNum)
 69 {
 70     vectorQueue<int> *Queue = new vectorQueue<int>[queueNum - 1];
 71 
 72     int nextCar = 1;        //下一个该几号车厢
 73     minCar = carNum + 1;
 74     for (int i = 0; i < carNum; i++)
 75     {
 76         if (order[i] == nextCar)        //直接放到出轨道 { 9,5,7,3,2,8,4,1,6 };
 77         {
 78             ordered[nextCar - 1] = order[i];
 79             std::cout << "移动" << order[i] << "号车厢到出轨道"<<std::endl;
 80             nextCar++;
 81             while (minCar == nextCar && nextCar <= carNum)
 82             {
 83                 fromQueueToOrdered(Queue, queueNum - 1, ordered, nextCar, carNum);
 84                 nextCar++;
 85             }
 86         }
 87         else                            //将车厢放到缓冲轨道
 88         {
 89             if (!fromOrderToQueue(order[i], Queue, queueNum - 1, carNum))
 90                 return false;
 91             //            std::cout << "order[i] = " << order[i] << std::endl;
 92         }
 93         //        std::cout << "minCar = " << minCar << std::endl;
 94         /*
 95         std::cout << "Queue[0] = " << Queue[0] << std::endl;
 96         std::cout << "Queue[1] = " << Queue[1] << std::endl;
 97         std::cout << "Queue[2] = " << Queue[2] << std::endl;
 98         */
 99     }
100 
101     delete[] Queue;
102     return true;
103 }
104 
105 
106 
107 
108 /*******************************************************************************************
109 *                                        工厂仿真
110 *******************************************************************************************/
111 
112 // 全局变量
113 int timeNow;             // 当前时间
114 int numMachines;         // 机器数量
115 int numJobs;             // 任务数量
116 eventList* eList;        // 事件列表
117 machine* mArray;         // 机器数组
118 int largeTime = 10000;   // 所有任务完成截止时间
119 
120 void debug_info(std::string info)
121 {
122 #if DEBUG_INFO
123     std::cout << info << std::endl;
124 #endif
125 }
126 
127 //转换机器状态
128 job* changeState(int theMachine)
129 {
130     std::ostringstream info; 
131     info << "changeState( " << theMachine << " )";
132 
133     // 机器 theMachine 上的工序完成了就调度下一项任务
134     job* lastJob;
135     if (mArray[theMachine].activeJob == NULL)    //空闲或转换状态
136     {
137         info << "机器空闲";
138 
139         lastJob = NULL;
140         // wait over, ready for new job
141         if (mArray[theMachine].jobQ.empty())    // 没有等待被执行的任务
142         {
143             eList->setFinishTime(theMachine, largeTime);
144 
145             info << "且没有等待被执行的任务";
146         }
147         else                                    //取出队首的任务并开始执行
148         {
149             int id = mArray[theMachine].jobQ.front()->id;
150             int Mac = mArray[theMachine].jobQ.front()->taskQ.front().machine;
151             int time = mArray[theMachine].jobQ.front()->taskQ.front().time;
152 
153             mArray[theMachine].activeJob = mArray[theMachine].jobQ.front();
154             mArray[theMachine].jobQ.pop();
155             mArray[theMachine].totalWait += timeNow - mArray[theMachine].activeJob->arrivalTime;
156             mArray[theMachine].numTasks++;
157             int t = mArray[theMachine].activeJob->removeNextTask();
158             eList->setFinishTime(theMachine, timeNow + t);
159 
160             info << ",有等待被执行的" << id << "号任务在 " << Mac << "机器上执行 " << time;
161         }
162     }
163     else                    //刚完成了一项任务
164     {
165         // 设置转换时间
166         lastJob = mArray[theMachine].activeJob;
167         mArray[theMachine].activeJob = NULL;
168         eList->setFinishTime(theMachine, timeNow + mArray[theMachine].changeTime);
169 
170         info << "刚执行完第" << lastJob->id << "号任务";
171     }
172 
173     debug_info(info.str());
174     // 返回 theMachine 刚完成的任务
175     return lastJob;
176 }
177 
178 //将任务移动到下一项任务所需的机器上
179 bool moveToNextMachine(job* theJob)
180 {
181     if (theJob->taskQ.empty())        //任务已完成，返回false
182     {
183         std::cout << "第" << theJob->id << "号任务在 "
184             << timeNow << " 时间完成，等待 " << (timeNow - theJob->length) 
185             <<std::endl;
186         return false;
187     }
188     else                            //任务还有下一道工序
189     {
190         std::ostringstream info;
191         info << "将" << theJob->id << " 号任务调度到" << theJob->taskQ.front().machine
192             <<"号机器";
193         debug_info(info.str());
194 
195         // 执行下一项任务的机器
196         int p = theJob->taskQ.front().machine;
197         // 将任务添加到该机器的等待队列中
198         mArray[p].jobQ.push(theJob);
199         theJob->arrivalTime = timeNow;
200         // 如果该机器空闲，则改变其状态为 活动
201         if (eList->nextEventTime(p) == largeTime)
202             changeState(p);
203 
204         return true;
205     }
206 }
207 
208 //获取机器和任务数据
209 void getMachineAndJob()
210 {
211     std::cout << "输入机器数量和任务数量：" << std::endl;
212     std::cin >> numMachines >> numJobs;
213     if (numMachines < 1 || numJobs < 1)
214         throw illegalInputData("机器数量和任务数量必须 >= 1");
215 
216     // 生成任务和机器队列
217     eList = new eventList(numMachines, largeTime);
218     mArray = new machine[numMachines + 1];
219 
220     // 输入状态转换时间
221     int ct;
222     for (int j = 1; j <= numMachines; j++)
223     {
224         std::cout << "输入"<<j<<"号机器状态转换时间：" << std::endl;
225         std::cin >> ct;
226         if (ct < 0)
227             throw illegalInputData("状态转换时间必须 >= 0");
228         mArray[j].changeTime = ct;
229     }
230 
231     // 输入任务
232     job* theJob;
233     int numTasks, firstMachine, theMachine, theTaskTime;
234     for (int i = 1; i <= numJobs; i++)
235     {
236         std::cout << "输入"<< i<<"号任务的工序数量：" << i << std::endl;
237         std::cin >> numTasks;
238         firstMachine = 0;   // machine for first task
239         if (numTasks < 1)
240             throw illegalInputData("任务的工序数量必须 > 1");
241 
242         // 创建任务
243         theJob = new job(i);
244         for (int j = 1; j <= numTasks; j++)
245         {
246             std::cout << "输入" << i << "号任务"<<j<<"号工序（机器编号，执行时间）：" << std::endl;
247             // 读取任务i的工序
248             std::cin >> theMachine >> theTaskTime;
249             if (theMachine < 1 || theMachine > numMachines
250                 || theTaskTime < 1)
251                 throw illegalInputData("机器编号 或 执行时间 错误");
252             if (j == 1)
253                 firstMachine = theMachine;                // 第一道工序所需要的机器
254             theJob->addTask(theMachine, theTaskTime);    // 添加到工序队列
255         }
256         mArray[firstMachine].jobQ.push(theJob);
257     }
258 }
259 
260 //初始化，填装任务
261 void initMachine()
262 {
263     for (int p = 1; p <= numMachines; p++)
264         changeState(p);
265 }
266 
267 //执行任务，开始仿真
268 void simulate()
269 {
270     while (numJobs > 0)            //存在未处理的任务
271     {
272         int nextToFinish = eList->nextEventMachine();
273         timeNow = eList->nextEventTime(nextToFinish);
274         // 改变机器 nextToFinish 上的任务
275         job* theJob = changeState(nextToFinish);
276         // 移动任务到下一台机器，若任务完成，则减少未完成任务数
277         if (theJob != NULL && !moveToNextMachine(theJob))
278         {
279             std::ostringstream info;
280             info << "A job over at the " << timeNow << "time";
281             debug_info(info.str());
282             numJobs--;
283         }
284     }
285 }
286 
287 //输出任务在每台机器上的等待时间
288 void outputTime()
289 {
290     std::cout << "完成时间 = " << timeNow << std::endl;
291     for (int p = 1; p <= numMachines; p++)
292     {
293         std::cout << "第 " << p << " 号机器完成了 "
294             << mArray[p].numTasks << " 道工序，" << std::endl;
295         std::cout << "等待时间是 " << mArray[p].totalWait << std::endl;
296         std::cout << std::endl;
297     }
298 }
299 
300 //仿真主程
301 void machineSimulate()
302 {
303     getMachineAndJob();
304     initMachine();
305     simulate();
306     outputTime();
307 }