Please read the following program CAREFULLY and IMPLEMENT it while fullfilling the RUNTIME requirements. Comments are highly apprciated. THANKS A BUNCH!! #ifndef _SERVICE_QUEUE_H #define _SERVICE_QUEUE_H #include #include #include class ServiceQueue { private: /** Your private data members here! * (you should have NO PUBLIC data members! * * Nested private types also go here. * For example, if your design needs some kind of * structure, you would specify it here. */ public: /** * Constructor * Description: intializes an empty service queue. * * RUNTIME REQUIREMENT: O(1) * * TODO */ ServiceQueue() { } /** * Destructor * Description: deallocates all memory assciated * with service queue * * RUNTIME REQUIREMENT: O(N_b) where N_b is the number of buzzer * IDs that have been used during the lifetime of the * service queue; in general, at any particular instant * the actual queue length may be less than N_b. * * [See discussion of "re-using buzzers" below] * * TODO */ ~ServiceQueue() { } /** * Function: snapshot() * param: buzzers is an integer vector passed by ref * Description: populates buzzers vector with a "snapshot" * of the queue as a sequence of buzzer IDs * * * RUNTIME REQUIREMENT: O(N) (where N is the current queue * length). */ void snapshot(std::vector &buzzers) { buzzers.clear(); // you don't know the history of the // buzzers vector, so we had better // clear it first. } /** * Function: length() * Description: returns the current number of * entries in the queue. * * RUNTIME REQUIREMENT: O(1) */ int length() { return 0; // placeholder } /** * Function: give_buzzer() * Return: buzzer-ID (integer) assigned to the new customer. * Description: This is the "enqueue" operation. For us * a "buzzer" is represented by an integer (starting * from zero). The function selects an available buzzer * and places a new entry at the end of the service queue * with the selected buzer-ID. * This buzzer ID is returned. * The assigned buzzer-ID is a non-negative integer * with the following properties: * * (1) the buzzer (really it's ID) is not currently * taken -- i.e., not in the queue. (It * may have been in the queue at some previous * time -- i.e., buzzer can be re-used). * This makes sense: you can't give the same * buzzer to two people! * * (2) Reusable Buzzers: A re-usable buzzer is * a buzzer that _was_ in the queue at some previous * time, but currently is not. * * REQUIREMENT: If there is one or more reusable * buzzer, you MUST return one of them; furthermore, * it must be the buzzer that became reusable most * MOST RECENTLY. * * (3) if there are no previously-used / reusable buzzers, * the SMALLEST possible buzzer-ID is used (retrieved from * inventory). * Properties in this situation (where N is the current * queue length): * * - The largest buzzer-ID used so far is N-1 * * - All buzzer-IDs in {0..N-1} are in the queue * (in some order). * * - The next buzzer-ID (from the basement) is N. * * In other words, you can always get more buzzers (from * the basement or something), but you don't fetch an * additional buzzer unless you have to (i.e., no reusable buzzers). * * Comments/Reminders: * * Rule (3) implies that when we start from an empty queue, * the first buzzer-ID will be 0 (zero). * * Rule (2) does NOT require that the _minimum_ reuseable * buzzer-ID be used. If there are multiple reuseable buzzers, * any one of them will do. * * Note the following property: if there are no re-useable * buzzers, the queue contains all buzzers in {0..N-1} where * N is the current queue length (of course, the buzzer IDs * may be in any order.) * * RUNTIME REQUIREMENT: O(1) ON AVERAGE or "AMORTIZED" * In other words, if there have been M calls to * give_buzzer, the total time taken for those * M calls is O(M). * * An individual call may therefore not be O(1) so long * as when taken as a whole they average constant time. * */ int give_buzzer() { return 0; // placeholder } /** * function: seat() * description: if the queue is non-empty, it removes the first * entry from (front of queue) and returns the * buzzer ID. * Note that the returned buzzer can now be re-used. * * If the queue is empty (nobody to seat), -1 is returned to * indicate this fact. * * Returns: buzzer ID of dequeued customer, or -1 if queue is empty. * * RUNTIME REQUIREMENT: O(1) */ int seat() { return -1; // placeholder } /** * function: kick_out() * * description: Some times buzzer holders cause trouble and * a bouncer needs to take back their buzzer and * tell them to get lost. * * Specifially: * * If the buzzer given by the 2nd parameter is * in the queue, the buzzer is removed (and the * buzzer can now be re-used) and 1 (one) is * returned (indicating success). * * Return: If the buzzer isn't actually currently in the * queue, the queue is unchanged and false is returned * (indicating failure). Otherwise, true is returned. * * RUNTIME REQUIREMENT: O(1) */ bool kick_out(int buzzer) { return false; // placeholder } /** * function: take_bribe() * description: some people just don't think the rules of everyday * life apply to them! They always want to be at * the front of the line and don't mind bribing * a bouncer to get there. * * In terms of the function: * * - if the given buzzer is in the queue, it is * moved from its current position to the front * of the queue. 1 is returned indicating success * of the operation. * - if the buzzer is not in the queue, the queue * is unchanged and 0 is returned (operation failed). * * Return: If the buzzer isn't actually currently in the * queue, the queue is unchanged and false is returned * (indicating failure). Otherwise, true is returned. * * RUNTIME REQUIREMENT: O(1) */ bool take_bribe(int buzzer) { return false; // placeholder } }; // end ServiceQueue class #endif 

You go to a popular restaurant that doesn't take reservations. When you get there, you just have to wait in line for a table. These days, most restaurants will give you some kind of buzzer and will signal you when your table is ready The restaurant essentially has to manage a queue of buzzers. Implementation of an ADT supporting this management is what you will be doing in this assignment. Overview of ServiceQueue behavior (greater detail can be found in the banner comments in ServiceQueue.h) . "Buzzers": for our purposes, a "buzzer" is represented by a unique integer ID. In principle, there is an infinite number of buzzers starting from Operation give, buzzer(): this is the enqueue operation (a new customer is getting in line). The following happens: o An unused buzzer ID is determined (see Buzzer Policy below) and o an entry for that buzzer is added to the end of the queue and o the selected buzzer ID is returned Operation seat): this is the "dequeue" operation if the queue is not-empty, the first entry is removed from the front; the removed buzzer ID can now be "re-used" (again, see Buzzer Policy below). If the queue is empty, false is returned and no changes are made (on success, true is returned). . Operation take_bribe(): A person holding a particular buzzer may offer the system a bribe to move to the front of the queue. This function takesa buzzer ID and does the following: o If the buzzer is indeed somewhere in the queue, it is plucked out and moved to the front of the queue and true is returned o Otherwise (the buzzer isn't even in the queue), the function simply returns false . Operation kick out(): (for sending trouble causers home). This operation takes a buzzer ID and does the following: o If the buzzer is indeed somewhere in the queue, it is removed and true is returned. The buzzer now becomes reusable (again, see Buzzer Policy) o Otherwise (the buzzer isn't even in the queue), the function simply returns false Operation snapshot(): This function takes an integer vector as a reference parameter and populates it with the current queue contents (i.e., sequence of buzzer IDs) in sequence Operation length) reports the current length of the queue Buzzer Policy: The buzzer ID assigned by a call to give buzzer is determined by the following policy: 1. If there are no reusable buzzers (i.e., from a previous seat or kick_out operation), the smalLest unused buzzer ID must be used. (As a consequence, the first call to give_buzzer will always use ID zero) 2. If there are reusable buzzers, the buzzer that became reusable most recently must be used (i.e., from the most recent seat or kick_out operation) Understanding Behavior: You have been given two complete implementations of the ADT described above However, these implementations, while behaviorally correct, do NOT meet the runtime requirements that you must meet The "slow" implementations are given in two files (they both use the class name ServiceQueue): . serviceQueueSlow.h: this makes extensive use of C++ vectors ncluding some arcane stuff with removal, iterators, etc ServiceQueueSlow2.h: this also uses C+ vectors and the same overall structure as ServiceQueueSlow.h However, some operations are done "by hand" on the underlying vectors instead of using the functions provided by the vector class. Reason: you may find some of the vector functions called in ServiceQueueSlow.h to be a bit strange (depending on your level of C experience This version may have fewer distractions for you (otherwise, in terms of behavior and runtime, the two "slow" versions are effectively the same You have also been given a simple interactive driver program in Driver.cpp. It can be compiled to use any of the three ServiceQueue implementations (one of the two slow ones or yours) To compile using ServiceQueue.h, you do nothing fancy (produces executable Driver) gt+-std-ct+il Driver.app-Driver To compile using ServiceQueueSlow.h: gt+ -std-ct+il Driver.cpp -D SLON-DriverSlow To compile using ServiceQueueSlow2.h: gtt-std-ct+ll Driver.cpp -D SLON2 -DriverSlow2 Or... simply type "make" and the provided makefile will compile all three Play with the driver program: To make sure you understand the correct behavior, compile and run DriverSlow and/or DriverSlow2 and follow the interactive menu A sample session has been included in an appendix Runtime Requirements: Now the fun part! Your implementation of the ServiceQueue class must meet the following runtime requirements: give_buzzer(): 0(1) runtime (technically 0(1) "amortized runtime") seat) take_bribe) 0(1) runtime kick_out) 0(1) runtime 0(1) runtime 0(n) runtime (where n is the queue length) 0(1) runtime length): Deliverables 1. (via gradescope) Analysis of a Slow implementation You will study the "Slow" implementations and do a (tight) worst-case runtime analysis for each of the size functions above Note that both ServiceQueueSlow.h and ServiceQueueSlow2.h have the same runtime behavior, so study the one you feel most comfortable with. This will be submitted via gradescope as a separate item. Details: a. You must include an analysis of each of the six operations above clearly labeled b. Each analysis must give a rationale for each of your conclusions (i.e., why your claimed worst-case runtime bound is correct) 2. Your implementation of ServiceQueue.h meeting the requirements above Brainstorming The week e6 lab will be dedicated to group brainstorming on ideas for how the runtime requirements can be met! In the meantime, think, think, think! Remember, you have lots of freedom here as to how you might organize your data structures. After you have completed your brainstorming lab sessions, we will discuss in lecture a sketch of a strategy which meets the runtime requirements. So, even if you weren't able to converge on a design that meets all requirements, you still can submit a final implementation that does! Restrictions: You may use vectors from the standard template library, but that is about the limit everything else must be done by you Hints: You may find doubly-linked list nodes handy It's cliche, but try to think outside the box. Think about your toolbox- you have structs, vectors, pointers, etc.. Be creative about how to use them! You go to a popular restaurant that doesn't take reservations. When you get there, you just have to wait in line for a table. These days, most restaurants will give you some kind of buzzer and will signal you when your table is ready The restaurant essentially has to manage a queue of buzzers. Implementation of an ADT supporting this management is what you will be doing in this assignment. Overview of ServiceQueue behavior (greater detail can be found in the banner comments in ServiceQueue.h) . "Buzzers": for our purposes, a "buzzer" is represented by a unique integer ID. In principle, there is an infinite number of buzzers starting from Operation give, buzzer(): this is the enqueue operation (a new customer is getting in line). The following happens: o An unused buzzer ID is determined (see Buzzer Policy below) and o an entry for that buzzer is added to the end of the queue and o the selected buzzer ID is returned Operation seat): this is the "dequeue" operation if the queue is not-empty, the first entry is removed from the front; the removed buzzer ID can now be "re-used" (again, see Buzzer Policy below). If the queue is empty, false is returned and no changes are made (on success, true is returned). . Operation take_bribe(): A person holding a particular buzzer may offer the system a bribe to move to the front of the queue. This function takesa buzzer ID and does the following: o If the buzzer is indeed somewhere in the queue, it is plucked out and moved to the front of the queue and true is returned o Otherwise (the buzzer isn't even in the queue), the function simply returns false . Operation kick out(): (for sending trouble causers home). This operation takes a buzzer ID and does the following: o If the buzzer is indeed somewhere in the queue, it is removed and true is returned. The buzzer now becomes reusable (again, see Buzzer Policy) o Otherwise (the buzzer isn't even in the queue), the function simply returns false Operation snapshot(): This function takes an integer vector as a reference parameter and populates it with the current queue contents (i.e., sequence of buzzer IDs) in sequence Operation length) reports the current length of the queue Buzzer Policy: The buzzer ID assigned by a call to give buzzer is determined by the following policy: 1. If there are no reusable buzzers (i.e., from a previous seat or kick_out operation), the smalLest unused buzzer ID must be used. (As a consequence, the first call to give_buzzer will always use ID zero) 2. If there are reusable buzzers, the buzzer that became reusable most recently must be used (i.e., from the most recent seat or kick_out operation) Understanding Behavior: You have been given two complete implementations of the ADT described above However, these implementations, while behaviorally correct, do NOT meet the runtime requirements that you must meet The "slow" implementations are given in two files (they both use the class name ServiceQueue): . serviceQueueSlow.h: this makes extensive use of C++ vectors ncluding some arcane stuff with removal, iterators, etc ServiceQueueSlow2.h: this also uses C+ vectors and the same overall structure as ServiceQueueSlow.h However, some operations are done "by hand" on the underlying vectors instead of using the functions provided by the vector class. Reason: you may find some of the vector functions called in ServiceQueueSlow.h to be a bit strange (depending on your level of C experience This version may have fewer distractions for you (otherwise, in terms of behavior and runtime, the two "slow" versions are effectively the same You have also been given a simple interactive driver program in Driver.cpp. It can be compiled to use any of the three ServiceQueue implementations (one of the two slow ones or yours) To compile using ServiceQueue.h, you do nothing fancy (produces executable Driver) gt+-std-ct+il Driver.app-Driver To compile using ServiceQueueSlow.h: gt+ -std-ct+il Driver.cpp -D SLON-DriverSlow To compile using ServiceQueueSlow2.h: gtt-std-ct+ll Driver.cpp -D SLON2 -DriverSlow2 Or... simply type "make" and the provided makefile will compile all three Play with the driver program: To make sure you understand the correct behavior, compile and run DriverSlow and/or DriverSlow2 and follow the interactive menu A sample session has been included in an appendix Runtime Requirements: Now the fun part! Your implementation of the ServiceQueue class must meet the following runtime requirements: give_buzzer(): 0(1) runtime (technically 0(1) "amortized runtime") seat) take_bribe) 0(1) runtime kick_out) 0(1) runtime 0(1) runtime 0(n) runtime (where n is the queue length) 0(1) runtime length): Deliverables 1. (via gradescope) Analysis of a Slow implementation You will study the "Slow" implementations and do a (tight) worst-case runtime analysis for each of the size functions above Note that both ServiceQueueSlow.h and ServiceQueueSlow2.h have the same runtime behavior, so study the one you feel most comfortable with. This will be submitted via gradescope as a separate item. Details: a. You must include an analysis of each of the six operations above clearly labeled b. Each analysis must give a rationale for each of your conclusions (i.e., why your claimed worst-case runtime bound is correct) 2. Your implementation of ServiceQueue.h meeting the requirements above Brainstorming The week e6 lab will be dedicated to group brainstorming on ideas for how the runtime requirements can be met! In the meantime, think, think, think! Remember, you have lots of freedom here as to how you might organize your data structures. After you have completed your brainstorming lab sessions, we will discuss in lecture a sketch of a strategy which meets the runtime requirements. So, even if you weren't able to converge on a design that meets all requirements, you still can submit a final implementation that does! Restrictions: You may use vectors from the standard template library, but that is about the limit everything else must be done by you Hints: You may find doubly-linked list nodes handy It's cliche, but try to think outside the box. Think about your toolbox- you have structs, vectors, pointers, etc.. Be creative about how to use them