implementation in JAVA

- private fields are not to be modified

- queue class must use a inked sequence that is node-based to represent the queue. This sequence is very similar to singly linked list but not required to provide all functionality of a linked list. Use the provided Node class to implement queue class

- constructor creates an empty queue with no front / back node, and size is zero

- enqueue : adds a new element to the back of queue, increase size of queue by one through addition of a new node to end of the sequence of nodes. Two cases to handle: (1) queue is empty before you enqueue an element, and (2) queue is not empty before you enqueue an element

- dequeue : removes and returns the element at the front of queue, decreasing the size of the queue by one through the removal of the node at the front of the sequence of nodes

- peek : returns element at the front of queue without removing it by returning the element stored in the node at the front of the sequence of nodes

- size : returns the size of the queue

- isEmpty : returns true if queue is empty & false otherwise

- toString : returns true a string representation of queue

Node class:

public class Node {

private E element;

private Node next;

/**

* Create a node holding the given data element and having the given next

* node in the sequence.

*

* @param element

* the data element to store in the node

* @param next

* the next node in the sequence

*/

public Node(E element, Node next) {

this.element = element;

this.next = next;

}

/**

* Get the next node in the sequence. Returns null if there are no more

* nodes in the sequence.

*

* @return the next node in the sequence

*/

public Node getNext() {

return this.next;

}

/**

* Set the next node in the sequence. Setting the next node to null

* indicates the end of the sequence.

*

* @param next

* the next node in the sequence

*/

public void setNext(Node next) {

this.next = next;

}

/**

* Get the data element stored in this node.

*

* @return the data element stored in this node

*/

public E getElement() {

return this.element;

}

/**

* Set the data element stored in this node.

*

* @param element

* the data element to store in this node

*/

public void setElement(E element) {

this.element = element;

}

}

Queue class to be implemented:

public class Queue {

/**

* Queue uses a node based implementation, where the nodes form a singly

* linked-list like structure. The queue must maintain a reference to the

* node holding the element at the front of the queue, and a reference to

* the node holding the element at the end of the queue.

*/

/**

* The node at the front of the queue (the first node, or head, of the

* linked list).

*/

private Node front;

/**

* The node at the back of the queue (the last node of the linked list)

*/

private Node back;

/**

* The number of elements stored in this queue (or the number of nodes)

*/

private int size;

/**

* Creates an empty queue (size is zero).

*/

public Queue() {

}

/**

* Enqueue an element. This operation adds the element to the back of the

* queue.

*

* @param element

* the element to add to the back of the queue

*/

public void enqueue(E element) {

}

/**

* Dequeue an element. This operation removes and returns the element at the

* front of the queue if the queue is not empty.

*

* @return the element at the front of the queue if the queue is not empty

* @throws NoSuchElementException

* if the queue is empty

*/

public E dequeue() {

}

/**

* Return the element at the front of the queue without dequeuing the

* element.

*

* @return the element at the front of the queue if the queue is not empty

* @throws NoSuchElementException

* if the queue is empty

*/

public E peek() {

}

/**

* Returns the number of elements in this queue.

*

* @return the number of elements in this queue

*/

public int size() {

}

/**

* Returns true if this queue is empty, and false otherwise.

*

* @return true if this queue is empty, and false otherwise

*/

public boolean isEmpty() {

}

/**

* Returns the node at the front of the queue. This method is here for

* debugging and testing purposes.

*

* @return the node at the front of the queue

*/

Node getFront() {

return this.front;

}

/**

* Returns the node at the back of the queue. This method is here for

* debugging and testing purposes.

*

* @return the node at the back of the queue

*/

Node getBack() {

return this.back;

}

/**

* Returns a hash code for this queue. The hash code is computed using the

* elements of this stack.

*

* @return a hash code for this queue

*/

@Override

public int hashCode() {

final int prime = 31;

int result = 1;

Node n = this.front;

while (n != null) {

result = prime * result + n.getElement().hashCode();

n = n.getNext();

}

return result;

}

/**

* Compares the specified object to this queue for equality. Two queues are

* equal if they contain the same number of elements in the same order.

*

* @param obj

* the object to compare to this queue for equality

* @return true if the specified object is equal to this queue

*/

@Override

public boolean equals(Object obj) {

if (this == obj) {

return true;

}

if (obj == null) {

return false;

}

if (this.getClass() != obj.getClass()) {

return false;

}

Queue other = (Queue) obj;

if (this.size == other.size()) {

Node n = this.front;

Node nOther = other.front;

for (int i = 0; i < this.size; i++) {

if (!n.getElement().equals(nOther.getElement())) {

return false;

}

n = n.getNext();

nOther = nOther.getNext();

}

}

return true;

}

/**

* Returns a string representation of this queue. The string representation

* consists of a list of the queue's elements from the front of the queue to

* the back of the queue, enclosed in square brackets ("[]"). Adjacent

* elements are separated by the characters ", " (comma and space). Elements

* are converted to strings as by String.valueOf(Object).

*

* @return a string representation of this queue

*/

@Override

public String toString() {

// to be implemented

}

}