This will also serve as a quick tutorial on how to use Java generic types. A generic type is basically like having a variable Object type for your class. This may sound a bit confusing, but they are fairly simple to use. The code for this class will illustrate this. Namely, you will see this:
public class Queue
This says, "this is a Queue which stores items T which extends (or implements) Comparable." To create an instance of this class, you would do as was done in the Category class.
Queue
This ensures that every Object in "questions" is a Question Object. To see how to build the rest of the class using the variable T, see the code below.
Since this class is going to be used as a queue, we will build it as a FIFO structure (first item in is the first item out). It will have a enqueue(x) method which adds new items to the back of the queue and a dequeue() method which returns the item from the front of the queue (think of it as, "next please!"). We will also add some other methods for retrieving data from the queue such as a get() method which will return the item from the front of the queue without removing it, a getLast() method which will do the same for the last, a getByIndex(i) method, and a getByString(s) method. Finally, a getLength() method will tell how many items are in the queue. The class also contains a private class called TNode which will simply store an Object of type T and a link to the next item in the queue (think of it as holding hands and looking backwards (can't see whats in front)).
@SuppressWarnings("rawtypes")
public class Queue <T extends Comparable>
{
/*** Description ***
* FIFO list of items of type T.
* Held together by private class TNode
* Items are added to the back of the list and pulled from the front
*
*** Variables ***
* #root - The first item in the list
* #end - The last item in the list
* #length - The number of items in the list
*
*** Methods ***
*
* #Constructor - No argument. Initializes all variables to default values.
* #push - add item of type T to the end of the list.
* #pop - remove item of type T from the front of the list.
* #get - get item of type T from the front of the list (without removing)
* #getFromIndex - get the nth item from the list
* #getByValue - find a node which matches the passed argument of type T.
*
*** Classes ***
*
* TNode
*/
protected TNode root;
protected TNode end;
int length;
public Queue()
{
this.root = null;
this.end = null;
this.length = 0;
}
public void enqueue(T item)
{
TNode newNode = new TNode(item);
if (root == null)
{
root = newNode;
}
else
{
end.next = newNode;
}
end = newNode;
length++;
}
public T dequeue()
{
T returnVal;
if (root == null)
return null;
returnVal = root.get();
root = root.next;
length --;
return returnVal;
}
public T get()
{
if (root == null)
return null;
return root.get();
}
public T getByIndex(int i)
{
TNode currNode = root;
if (root == null)
return null;
for (int j = 0; j < i; j++)
{
currNode = currNode.next;
if (currNode == null)
return null;
}
return currNode.get();
}
public T getByString (String str)
{
TNode currNode = root;
while (currNode != null)
{
if (currNode.get().toString().equalsIgnoreCase(str))
{
return currNode.get();
}
currNode = currNode.next;
}
return null;
}
public T getLast()
{
if (end == null)
return null;
return end.item;
}
public int getLength()
{
return length;
}
public void join(Queue<T> queue)
{
end.next = queue.root;
}
public void remove(int i)
{
if (i == 0)
root = root.next;
else
{
TNode t = getNodeByIndex(i-1);
if (i == length)
{
end = t;
t.next = null;
}
else // just skip the next node to remove it
{
t.next = t.next.next;
}
}
length --;
}
protected TNode getNodeByIndex(int i)
{
TNode currNode = root;
if (root == null)
return null;
if (i < 0)
return root;
for (int j = 0; j < i; j++)
{
currNode = currNode.next;
if (currNode == null)
return null;
}
return currNode;
}
protected class TNode
/*** Description ***
* This class represents a single node in a one directional list of type T.
*
*** Methods ***
* #Constructor: expects an item of type T
* #get: returns item of type T from the node
*
*** Variables ***
* #item: item of type T held by the node
* #next: next node in the list
****
*/
{
protected T item;
protected TNode next;
public TNode (T item)
{
this.item = item;
this.next = null;
}
public T get()
{
return item;
}
}
}
