Assignment 6 - Queues Using Inheritance (java)

Select one option from below. All (both) options are worth the same number of points. 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

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.

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.

Instead of deriving a FloatNode from the basic Node class, you will derive a CardNode from our Node. CardNode will use the Card class of Weeks 1 and 2.

Instead of signaling a pop() error by returning a special value (STACK_EMPTY = Float.MIN_VALUE), we will be more sophisticated and throw our own home-made QueueEmptyException in our remove() method. The client will catch it.

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, and it is the will be the least recent one added. The tailwill always point to the most recent one added to 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 aq.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.

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 the oldest item in the Queue. This is different from pop() which removed and returned the youngest item in the Queue.

remove() throws a QueueEmptyException exception if the queue is empty. You will define this exception.

Provide a 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.

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. Test your QueueEmptyException.

add() and remove() will be slightly more complicated than push() and pop() because you have two pointers, front and back (or headand 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. For this, you'll need to include the Card class of the first or second week.

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 from Queue, and, just like we did in the modules, write methods that let you add actual Cards onto each of 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 collections or generics 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 nextcontinues to point to the Node2's successor, prev will point to its predecessor. Since a Node2 is also a Node, these two references 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.

Once your assignment is graded and returned, you can view the instructor solution here:\

(I need code)