UNC-CH COMP 410

Queue as Linked List

Write Java classes to implement a Queue as a Linked List.
Use a double linked list (next and prev links) so we can have efficient insert and delete operations.

Write these 3 classes (and others if you wish):

class Node (contains value and links)
class Que (double linked list of Node)
class QueDemo (test driver)

Node

You may use generics if you wish, or you may write your Node class to contain a value of type double.
An object of type Node will contain a value field, and two Node fields (the links, or pointers for you C programmers). The Node fields will point to the Node ahead in the list, and the Node behind.

Write these methods:

one or more constructors
void setVal(double v), double getVal() (or generic instead of double)
void setNext(Node n), Node getNext()
void setPrev(Node n), Node getPrev()

Que

Implement your Que as a list with no special header nodes. This means if the list is empty, then the head pointer and the tail pointer with both be null. If the list has one Node, then head will be the same as tail.

Write these methods:

one or more constructors
void enq(double v), void deq()
double head(), double tail() (or generics)
boolean empty()
int size()
boolean equals(Que q) (explained below in QueDemo)

QueDemo

This will contain the main method.
In it you will create objects of type Que and test for correct behavior out of your implementation.

You may test it as you wish, but at least show that it exhibits the behavior given by the axioms we wrote for ADT Que.

This means you need to create the situations described on each side of an axiom and show that the two sides are "equal". Then do this for each axiom.

For example, consider

   size(enq(i,Q)) = size(Q)+1

To test using this, create some instance Q of Que; do an enq(i,Q) on it for some value i; then do a size on it and keep that result; then take the original instance of Q and do a size on it, subtract 1, and see if it is equal to the value you saved.

Note: Some of the axioms compare one Que to another for equality; this is abstract equality. You cannot do this by simply asking

  if (Q1 == Q2)

since this will compare the addresses of the objects and not the contents of the lists. You will need to write a method called "equals" in your class Que to deal with this. It will allow an object of type Que to compare itself to another object of type Que and return true if they are abstractly the same. We will define abstractly equal as

both queues have the same number of nodes
both contain the same values in the same order

Careful... don't destroy the contents of either Que during the execution of equals.

Submission

You will submit the completed assignment using blackboard. You will upload your Java source files; the instructions will be there to follow.