Assignment 10 - Queues Using Inheritance (C++)

This extra credit assignment is worth 12 points. Don't worry about the fact that it may say " .1 points possible." You can get up to 12 points for it.

Select one option from below. All (both) options are worth the same number of points -- 12 for this bonus. The more advanced option(s) are provided for students who find the basic one too easy and want more of a challenge. Make sure you have read and understood

both modules A and B this week, and

module 2R - Lab Homework Requirements

before submitting this assignment.

Even though you learned to do multi-file projects, please continue to submit only one file with a full, working program and run.

OPTION A (Basic): A Queue of Cards

Understand the Problem

We hearken back to the original non-STL inheritance technique for Nodes and Stacks that we learned. You are going to parallel the development done in a past lesson on inheritance where we constructed some base classes, StackNode and Stack, and derived FloatNode and FloatStack from them. You can work best by referring to those modules all through the development of your program. These are the differences between what we did in the lesson and what you will do for your assignment.

Our basic node will be called Node rather than StackNode. You can make the data public to simplify our design. You can also make the toString() method virtual.

Instead of a Stack data structure, you will create a Queue data structure. A Stack is last-in-first-out (LIFO). A Queue is first-in-first-out (FIFO). We'll use add() and remove(), instead of push()and pop(), as the names of our primary accessors. You can change the private access specifier to protected to simplify the design.

Instead of deriving a FloatNode from the (lecture's) base StackNode class, you will derive a CardNode from our (newly named) Node. CardNode will use the Card class from the previous assignment without modification -- the instructor's Card class is fine.

Instead of deriving a FloatStack from the (lecture's) base Stack class, you will derive a CardQueue from our new Queue class. We'll do this using public, rather than private, inheritance, to allow clients to access the base class Queue toString() method.

Instead of signaling a pop() error by returning a bool, we will be more sophisticated and throw our own home-made CardQueueEmptyException in our CardQueue's remove() method. remove() will return the Card as a functional return since we no longer need the error bool in that position. The client will catch any exception.

We will replace all instances of show() with the more professional toString(), and let only the client send results to the display.

Picturing Queues

The head member of Queue will, be the first or oldest Node in the queue, i.e., it will be the "least recently" added. The tail will always point to the most recently added one in -- it is the "end of the Queue". Say we have added Nodes N1, N2, N3 and N4, in that order. The Nodes would be linked (in your Queue) as follows:

The links of the next pointers look like the StackNode organization, with head and tail sharing the role of our old top:

 head  N1  N2  N3  N4  null 

The tail pointer, not shown above, points to N4

 head  N1  N2  N3  N4  tail 

If we instantiated a new Node N5, and added it onto the Queue q, it would go in at the tail, Here is the Queue, q, after a q.Add(N5);

A couple links have to be changed to result in:

 head  N1  N2  N3  N4  N5  null 

Note: the tail has to be adjusted:

 head  N1  N2  N3  N4  N5  tail 

If we then removed an item from the Queue, using q.Remove(), the picture would be:

The links now convey the following:

 head  N2  N3  N4  N5  null 

Note, the tail may not have to be adjusted (but in one case, not shown, it will):

 head  N2  N3  N4  N5  tail 

Of course, when you do this, you will only be changing a couple pointers in each operation (either near the tail or near the head). Most of the nodes don't need to be touched in add() and remove().

Phase 1: Base Classes Node and Queue

Base Class Node

You can use the same class for a base class that was used in the modules. However, I want you to give this class a different name. Call it Node (not QueueNode or StackNode, just Node). Also, take heed to replace show() methods with toString() methods. Finally, make toString() and the destructors virtual in order to facilitate the use of base-class pointers by the client.

Base Class Queue

Next, do almost the same thing as we did with the Stack class except make sure that this class works like a Queue, not a Stack. That means

We add items to the Queue using add() not push(). push() does not appear in our Queue class.

We retrieve items from the Queue using remove() not pop(). pop() does not appear in our Queue class.

remove() removes and returns a pointer to the oldest Node (pointer) in the Queue. This is different from pop() which removed and returned the youngest item in the Queue.

Provide a virtual toString() method produces a string of all the items in the Queue from oldest to youngest.

Instead of one Node pointer member, top, you'll need two Node pointer members, and neither should be called top (since top is not meaningful in a Queue). Examples are head/tail, front/back, oldest/youngest, etc. Select two names and use them accordingly.

Make the destructor virtual.

Phase 2: Intermediate Step - Check Your Base Classes

Once you have written these two classes, write a simple test main() just like I did in the modules - show a run that displays some (generic node)s. Test the Queue's toString() method and also build a simple loop in your main() to remove and display nodes as they are removed. Compare the output of these two techniques -- they should be similar. You will not hand this in. It is just for your use in developing the full program.

add() and remove() will be slightly more complicated than push() and pop() because you have two pointers, front and back (or head and tail, or whatever you call them) to manage. This may take some time and debugging. Test it carefully. Even after you get it to work, you may find that it still needs debugging later, since your "(generic node)" screen results won't tell you if things are coming off in the correct order. You won't know that until you have real data in your Nodes. That's the next part.

Phase 3: Derived Classes CardNode and CardQueue

Deriving from Node

Now comes the fun. Derive a class from Node, CardNode. This will contain one additional member, just like the FloatNode did. However, instead of that additional member being a float it will be a Card. Use the Card class from the previous assignment without modification -- the instructor's Card class is fine.

Override the toString() method of the generic Node class to return the specific type of data. The important thing here is to not do any work - you let your Card class stringize itself through its, already defined, toString() method.

Deriving from Queue

Derive CardQueue publicly from Queue and write methods that let you add and remove actual Cards onto the CardQueue.

Card remove() takes no parameters since it returns its Card as a return value (and the base class remove() will help this method get the correct, i.e., oldest, position in the Queue). The old bool return type of pop() is no longer necessary now that we know about exceptions. So define and throw a CardQueueEmptyException in that case.

void add(Card x) takes a Card object, wraps that in CardNode, then calls upon the base class add() to place that CardNode into the correct, i.e., youngest, position in the Queue.

In your client, add() a bunch of cards, toString() the queue to the screen to see that this is working, then in a loop, remove() items displaying them as you do. Go "too far" so that you attempt to remove()from an empty queue and see that you are catching the exception.

Do not use stl templates for this assignment. You are being asked to create your own data structures exactly as I did in the lesson.

OPTION B (Intermediate): DEQueue

This is a "double ended" queue. After completing Option A, repeat the overall process with the following changes:

Create a class Node2, which is derived from Node. Node2 has a second link, besides its inherited next. This additional link is Node *prev. The idea is, every Node2 object can point both forward and backward in any linked list structure. While next continues to point to the Node2's successor, prev will point to its predecessor. Since a Node2 is also a Node, these two pointers (next and prev) can naturally point to Node2 object, which they will always do in this case.

Create a class DEQueue, which is similar to Queue, but which has four, rather than two, primary accessors:

addToBack() - similar to add() of Queue; the name says it all.

removeFromFront() - similar to remove() of Queue; the name says it all.

addToFront() - similar to push() of Stack; the name says it all.

removeFromBack() - not quite the same as any previous method, but still - the name says it all.

You do not need any additional private members beyond what you had it Queue: head and tail will be adequate for this richer class. Its power stems from the extra accessors.

As you can see, a DEQueue can behave like a Stack or a Queue, or even some unnamed combination of the two. It is both more flexible, and also more prone to confusion, due to its ambidexterity.

Write a client that shows a single DEQueue acting at times like a Stack, at other times like a Queue. Also demonstrate some random adds and removes from both sides of the DEQueue willy-nilly.