Design and Implementation of a Service Queue ADT

1. Your class implementation (file: ServiceQueue.h)

(details below).

You go to a popular restaurant that doesnt 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 0.

• Operation give_buzzer(): this is the enqueue operation (a new customer is getting in line). The following happens:

  • An unused buzzer ID is determined (see Buzzer Policy below) and

  • an entry for that buzzer is added to the end of the queue and

  • 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 takes a buzzer ID and does the following:

  • 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.

  • 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:

  • 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).

  • 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 including some arcane stuff with removal, iterators, etc.

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):

g++ -std=c++11 Driver.cpp -Driver

To compile using ServiceQueueSlow.h:

g++ -std=c++11 Driver.cpp -D_SLOW -DriverSlow

To compile using ServiceQueueSlow2.h:

g++ -std=c++11 Driver.cpp -D_SLOW2 -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(): O(1) runtime (technically O(1) "amortized runtime")

seat(): O(1) runtime.

take_bribe(): O(1) runtime

kick_out(): O(1) runtime

snapshot(): O(n) runtime (where n is the queue length).

length(): O(1) runtime

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:

   1. You must include an analysis of each of the six operations above clearly labeled.

   2. 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.

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!

#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