For todays lab, you need to complete the LinkedQueue implementation. Follow the guidance in the java files to complete the queue services (methods) and the driver program.

1. Complete LinkedQueue.java.

2. Complete the driver TestQueue.java.

3. Run the driver and check if operations on the queue are correctly implemented.

//*********************************************************** // LinkedQueue.java

// A linked-list implementation of the classic FIFO queue interface.

//***********************************************************

public class LinkedQueue implements QueueADT {

private Node front, back; private int numElements;

//---------------------------------------------

// Constructor; initializes the front and back pointers // and the number of elements.

//---------------------------------------------

public LinkedQueue() {

}

//---------------------------------------------

// Puts item on end of queue.

//---------------------------------------------

public void enqueue(Object item) {

}

//---------------------------------------------

// Removes and returns object from front of queue.

//---------------------------------------------

public Object dequeue() {

}

//---------------------------------------------

// Returns true if queue is empty.

//---------------------------------------------

public boolean isEmpty() {

}

//---------------------------------------------

// Returns true if queue is full, but it never is.

//---------------------------------------------

public boolean isFull() {

}

//---------------------------------------------

// Returns the number of elements in the queue.

//---------------------------------------------

public int size() {

} //---------------------------------------------

// Returns a string containing the elements of the queue

// from first to last

//---------------------------------------------

public String toString() {

String result = " ";

Node temp = front;

while (temp != null) {

result += temp.getElement() + " ";

temp = temp.getNext();

}

return result;

}

}

//************************************************************

//Node.java

//A general node for a singly linked list of objects.

//************************************************************

public class Node {

private Node next;

private Object element;

//-------------------------------------------------------

//Creates an empty node

//-------------------------------------------------------

public Node() {

next = null;

element = null;

}

//-------------------------------------------------------

//Creates a node storing a specified element

//-------------------------------------------------------

public Node(Object element) {

next = null;

this.element = element;

}

//-------------------------------------------------------

//Returns the node that follows this one

//-------------------------------------------------------

public Node getNext() {

return next;

}

//-------------------------------------------------------

//Sets the node that follows this one

//-------------------------------------------------------

public void setNext(Node node) {

next = node;

}

//-------------------------------------------------------

//Returns the element stored in this node //-------------------------------------------------------

public Object getElement() {

return element;

}

//-------------------------------------------------------

//Sets the element stored in this node

//-------------------------------------------------------

public void setElement(Object element) {

this.element = element;

}

}

//**********************************************************

// QueueADT.java

// The classic FIFO queue interface.

//**********************************************************

public interface QueueADT {

//---------------------------------------------

// Puts item on end of queue.

//---------------------------------------------

public void enqueue(Object item);

//---------------------------------------------

// Removes and returns object from front of queue.

//-------------------------------------------

public Object dequeue();

//---------------------------------------------

// Returns true if queue is empty.

//---------------------------------------------

public boolean isEmpty();

//---------------------------------------------

// Returns true if queue is full.

//---------------------------------------------

public boolean isFull();

//---------------------------------------------

//Returns the number of elements in the queue.

//---------------------------------------------

public int size();

}

//**********************************************************

// TestQueue

// A driver to test the methods of the QueueADT implementations. //**********************************************************

public class TestQueue {

public static void main(String[] args) {

QueueADT q = new LinkedQueue();

System.out.println(" Enqueuing chocolate, cake, pie, truffles:");

q.enqueue("chocolate");

q.enqueue("cake");

q.enqueue("pie");

q.enqueue("truffles");

System.out.println(" Here's the queue: " + q);

// put your code here: print the size of the queue

System.out.println(" Dequeuing two...");

//put your code here: call the dequeue method twice and print out the dequeued items

System.out.println(" Enqueuing cookies, profiteroles, mousse, cheesecake, ice cream:");

q.enqueue("cookies");

q.enqueue("profiteroles");

q.enqueue("mousse");

q.enqueue("cheesecake");

q.enqueue("ice cream");

//think about which of the above items cannot be added into the queue?

System.out.println(" Here's the queue again: " + q);

System.out.println("Now it contains " + q.size() + " items.");

System.out.println(" Dequeuing everything in queue");

//put your code here: dequeue everything in the queue now using a loop

System.out.println(" Now it contains " + q.size() + " items.");

if (q.isEmpty())

System.out.println("Queue is empty!");

else

System.out.println("Queue is not empty -- why not??!!");

}

}