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 given Card class(Look at the bottom)

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 tail will 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 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.

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

class Card {

// type and constants

public enum Suit {

clubs, diamonds, hearts, spades

}

static char DEFAULT_VAL = 'A';

static Suit DEFAULT_SUIT = Suit.spades;

// private data

private char value;

private Suit suit;

private boolean errorFlag;

// 4 overloaded constructors

public Card(char value, Suit suit) { // because mutator sets errorFlag, we

// don't have to test

set(value, suit);

}

public Card(char value) {

this(value, DEFAULT_SUIT);

}

public Card() {

this(DEFAULT_VAL, DEFAULT_SUIT);

}

// copy constructor

public Card(Card card) {

this(card.value, card.suit);

}

// mutators

public boolean set(char value, Suit suit) {

char upVal; // for upcasing char

// convert to uppercase to simplify

upVal = Character.toUpperCase(value);

if (!isValid(upVal, suit)) {

errorFlag = true;

return false;

}

// else implied

errorFlag = false;

this.value = upVal;

this.suit = suit;

return true;

}

// accessors

public char getVal() {

return value;

}

public Suit getSuit() {

return suit;

}

public boolean getErrorFlag() {

return errorFlag;

}

// stringizer

public String toString() {

String retVal;

if (errorFlag)

return "** illegal **";

// else implied

retVal = String.valueOf(value);

retVal += " of ";

retVal += String.valueOf(suit);

return retVal;

}

// helper

private static boolean isValid(char value, Suit suit) {

// don't need to test suit (enum), but leave in for clarity

char upVal; // string to hold the 1-char value

String legalVals = "23456789TJQKA";

// convert to uppercase to simplify (need #include )

upVal = Character.toUpperCase(value);

// check for validity

if (legalVals.indexOf(upVal) >= 0)

return true;

else

return false;

}

public boolean equals(Card card) {

if (this.value != card.value)

return false;

if (this.suit != card.suit)

return false;

if (this.errorFlag != card.errorFlag)

return false;

return true;

}

}