有过对STL的栈练习，当然就少不了队列了
看一下题目总体要求
Background
From store-and-forward queues in network routers to the facilitation of breadth-first searches in graph algorithms, queues have many important applications in Computer Science and Information Technology. One such application can be found in a policy used by networked printers to manage print jobs. A complicated policy involves the prioritization of jobs that come from certain users. A simpler approach is a first-in-first-out policy. This policy dictates that print jobs are processed in the order they are received. A queue is used to implement this first-in-first-out policy.
Description
This assignment tests your understanding of queues and your ability to use the STL queue adapter. The program you are asked to finish the implementation of simulates a shared printer. This printer uses a first-in-first-out queue.
The simulation works by reading and processing a list of events from a data file. Each line in a valid data file contains information about a print job and a time when this job was submitted. Specifically, the information contained in each line is the time (in seconds) the job was submitted, the length in pages of the job, and the name of the computer from which the job was submitted. At the beginning of the simulation, each of these events should be read in by the program and stored in the inherited workload queue.
The program should simulate the passage of time by incrementing a counter inside a for-loop or while-loop. The program should initialize this counter to zero and increment it by one second. A print job "arrives" when the current time of the simulation equals the submitted time of the print job at the front of the workload queue. When this happens, pop this event from the workload queue and place it in another queue<event> object. This other queue<event> object stores the "arrived" print jobs. These jobs wait in this queue while the program simulates the printing of other jobs. Hence, you may want to name this object waiting or something similar.
它首先说了队列这种数据结构的重要性，然后以一个网络打印机为实例来学习队列
它给了如下文件：
- main.cpp - Includes function main
- simulator.h - Declaration of class simulator
- simulator.cpp - Definition of class simulator
- event.h - Declaration of class event
- event.cpp - Definition of class event
- job.h - Declaration of class job
- job.cpp - Definition of class job
- arbitrary.run - Data file containing arbitrary print jobs
- arbitrary.out - Output from a sample solution when run using arbitrary.run
- bigfirst.run - Data file containing larger jobs first
- bigfirst.out - Output from a sample solution when run using bigfirst.run
文件有些多，最重要的应该是simulator了，因为我们的类要继承它
先来理理头绪，对于多个文件应该从main.cpp和基类看起
再看题目要求
Following is an ordered list of steps that serves as a guide to completing this assessment. Work and test incrementally. Save often
- First, declare your class fifo in a file named fifo.h. Declare class fifo appropriately to model the following relationship: a fifo is a type of simulator.
- Next, complete the implementation of fifo::simulate. This member function should first load the data file using the inherited loadworkload. Then it should implement the simulation as described above. Use the inherited seconds_per_page data member to help determine how long a print job takes to print. Your solution's output should match the output from the sample solutions.
For clarity, latency is the number of seconds that elapse between when a print job arrives and when it begins printing. Aggregate latency is the total latency of all print jobs, and mean latency is the average latency across all print jobs.
我先列出main.cpp
#include <iostream> #include <cstdlib> #include <stdexcept> #include <string> #include "simulator.h" #include "fifo.h" //注释：白强 using namespace std; int main (int argc, char *argv[]) { //两个参数，不是的话程序异常退出 if (argc != 2) { cerr << "Usage: " << argv[0] << " data-file\n"; return EXIT_FAILURE; } try { //得到要打开的文件的名称 string file = argv[1]; //创建对象 simulator *s = new fifo (2); //调用下面这个函数处理文件，发现它在simulator.h 中已经声明virtual void simulate(string file) = 0所以我们明确是要我们在子类中实现方法 s->simulate(file); delete s; } catch(exception& e) { cerr << e.what() << endl; } catch(...) { cerr << "Unknown exception caught!" << endl; } return EXIT_FAILURE; }
再来看看simulator.h和simulator.cpp
#ifndef SIMULATOR_H #define SIMULATOR_H #include <queue> #include <string> using namespace std; #include "event.h" class simulator { protected: int seconds_per_page; queue<event> workload; //添加一个事件 virtual void addevent(event e); //实现文件读入的函数 virtual void loadworkload(string file); public: //通过设置打印的速度 simulator(int seconds_per_page); virtual void simulate(string file) = 0; //析构函数 virtual ~simulator(); }; #endif
#include <iostream> #include <fstream> using namespace std; #include "simulator.h" #include "event.h" //各个函数的实现比较好懂 simulator::simulator(int seconds_per_page) { this->seconds_per_page = seconds_per_page; } simulator::~simulator() {} void simulator::loadworkload (string file) { ifstream in; // Open workload file in.open (file.c_str()); if (!in) { cerr << "Couldn't open input file, workload empty" << endl; return; } // Load workload into simulator while (1) { event e; in >> e; if (in.eof()) break; addevent (e); } } void simulator::addevent(event e) { workload.push(e); }
这其中用到了event.h，那我们就来看看这个文件吧
#ifndef EVENT_H #define EVENT_H #include <iostream> using namespace std; #include "job.h" class event { private: //把要读入的词后两个封装成Job类 job j; //要读入的文件的第一个词 int wait_until; public: //两个构造函数 event(); event(job j, int wait_until); job getjob() const; int arrival_time() const; //友元函数重载流操作符 friend istream &operator>>(istream &stream, event &e); friend ostream &operator<<(ostream &stream, event &e); }; #endif
event.cpp
#include <iostream> using namespace std; #include "event.h" //比较好懂就不注释了，总体思想是读入和输出event对象 event::event (job j, int wait_until) { this->j = j; this->wait_until = wait_until; } event::event () { this->wait_until = -1; } job event::getjob() const { return j; } int event::arrival_time() const { return wait_until; } istream &operator>>(istream &stream, event &e) { stream >> e.wait_until; stream >> e.j; return stream; } ostream &operator<<(ostream &stream, event &e) { stream << e.wait_until << " " << e.j; return stream; }
其中有用到了Job类，它其实是把要读入的文件后两个词给封装了
#ifndef JOB_H #define JOB_H #include <iostream> #include <string> using namespace std; //没什么难的 class job { private: //最后一个词 string user; //第二个词 int number_of_pages; public: job(); job(int number_of_pages, string user); string getuser() const; int getnumpages() const; friend istream &operator>>(istream &stream, job &j); friend ostream &operator<<(ostream &stream, job &j); }; #endif
#include <iostream> using namespace std; #include "job.h" job::job (int number_of_pages, string user) { this->number_of_pages = number_of_pages; this->user = user; } job::job () { this->number_of_pages = -1; this->user = ""; } string job::getuser() const { return user; } int job::getnumpages() const { return number_of_pages; } istream &operator>>(istream &stream, job &j) { stream >> j.number_of_pages; stream >> j.user; return stream; } ostream &operator<<(ostream &stream, job &j) { int pages = j.number_of_pages; stream << pages << " page" << ((pages == 1) ? "" : "s") << " from " << j.user; return stream; }
接下来就要完成我们的作业了，自己写fifo.h和fifo.cpp文件
#ifndef FIFO_H #define FIFO_H //这是fifo.h文件 #include <queue> using namespace std; #include "simulator.h" class fifo : public simulator { private: queue <event> waiting; public: fifo(); fifo (int count); //最重要的方法 void simulate (string workload); }; #endif
fifo.cpp
#include "fifo.h" //给出了simulate (string file)的实现 //有英文注释比较详细 fifo::fifo() : simulator(1) {} fifo::fifo (int count) : simulator (count) {} /* * 注释：白强 * simulate (string file) 是最重要的方法，它先调用 void loadworkload(string file)打开文件 * 然后当得到工作台的列队不为空时： * 开始计时，时间向后推，一次循环一秒，直到这两个列队为空 * 当时间大于等于工作台的队头元素来的时间时把队头出队放入等待列队，要不然人家还没来能怎么样 * 然后 在上一个等待队列的队头在打印时，把这个时间段来的元素全加入到等待队列 * 当一个打印完毕之再看等待列队有没有要打印的，有的话打印队头，同时队头出列 * 这样在时间的这个for循环下，最后所有的元素都可以被打印 * 程序结束 * */ void fifo::simulate (string file) { int aggregate_latency = 0; int complete_jobs = 0; //调用基类的 void loadworkload(string file)方法来读入文件 loadworkload(file); //判断栈是否为空 if (workload.empty()) { cout << "\n\tThe queue is empty\n"; } else { //开始工作了 cout << "\n\nFIFO Simulaton\n\n"; //下一次可以工作的时间 next_time = time+ (seconds_per_page * e.getjob().getnumpages())可以看出它就是当前时间再加上打印工作的耗时 int next_time = 0; //开始计时了，当工作台和等待列队均不为空时执行for循环，time++其实就是把时间向后推一秒 for (int time = 0;!(workload.empty() && waiting.empty());time++) { // Look at the workload, enqueue job, if it is time //如果工作台列队不为空而且当前的时间已经大于等于工作台的第一个event来的时间 //我们就把它取出来进入等待列队，意思是当前时间比工作台列队来的时间大于或等于的时候就把它加入到等待列队 while (!workload.empty()&& time >= workload.front().arrival_time()) { //工作台队头加入到等待队列 event e = workload.front(); workload.pop(); waiting.push (e); job j = e.getjob(); //表示它已经来了，正在等待打印 cout << "\tArriving: " << j << " at "<< time << " seconds\n"; } //当当前的时间小于下一个到达的直接执行time++，把时间向后退，当time等于下个工作的时间后，向后面执行那个if语句 if (time < next_time) { continue; } //当等待列队不为空则执行打印服务，肯定要有东西才能执行打印，要不然打印谁去，没有能打印的再把时间向后退 if (!waiting.empty()) { //具体打印的应该是waiting列队的队头元素 event e = waiting.front(); job j = e.getjob(); //打印时的时间 cout << "\tServicing: " << j << " at " << time << " seconds\n"; //waiting列队的队头元素出列表示完成 waiting.pop(); //下一次循环的时间肯定是当前时间再加上打印耗时 next_time = time+ (seconds_per_page * e.getjob().getnumpages()); //这个是延迟的时间累积，它就是把当前时间减去event到达的时间，就是延迟的时间了 aggregate_latency += (time - e.arrival_time()); //完成的工作数++ complete_jobs++; } } //工作完毕，打印一些变量 //总共完成的工作数 cout << "\n\tTotal jobs: " << complete_jobs; //总共延迟的时间 cout << "\n\tAggregate latency: " << aggregate_latency << " seconds" ; cout << "\n\tMean latency: " //平均的延迟时间 << (float) aggregate_latency / (float) complete_jobs << " seconds\n"; } }
这个题到这里就完了，附上arbitrary.run文件
2 2 platypus
3 6 herring
4 1 falcon
5 1 giraffe
5 10 aardvark
5 7 dolphin
11 2 eagle
如果您有好的建议和意见请联系作者