Task1: implement a concrete LLQueue class (a linked-list based queue) that implements the IQueue interface as we discussed in the class, along with IQueue.java, ArrayQueue.java, SinglyLL.java, and QueueFullException.java given in the class (any other different queue class implementation, even if it is implemented by yourself, will not receive any credit).

Task2: write a test program that compares the performance of enqueue and dequeue operations between an array based queue (ArrayQueue) and a link-list based queue (LLQueue). You have to use the ArrayQueue class provided in the class and your LLQueue class implemented above.

The template of LLQueue class is given below:

public class LLQueue implements IQueue { private SinglyLL data; public LLQueue() { // your implementation } public int size() { // your implementation } public boolean isEmpty() { // your implementation } public void add(Object item) { // your implementation // you don't need to throw QueueFullException because the linked list // is not limited to any specific space capacity } public Object first() { // your implementation } public Object remove() { // your implementation } } 

Performance Comparison Test Scenario: Performance comparison test is a common method to evaluate a certain scheme or an algorithm. The following pseudo code is an example that tests the performance of enqueue and dequeue operations. Basically, it first creates a queue and enqueues 3000 elements. Next, it interleavely perform an enqueue and a dequeue operations for 2000 times. The time consumption of the 2000 operations is printed out. The exactly same process should be repeated for a linked-list based queue. Given the two results, try to draw a conclusion and determine which queue implementation is more efficient in enqueue and dequeue. In Java, you may use System.currentTimeMillis() to obtain the timestamp.

 create an array based queue with a capacity of 5000 elements add 3000 elements to the queue before = get_the_timestamp; for (i=0;i<2000;i++) { generate_A_RANDOM_Value; dequeue(); enqueue(A_RANDOM_Value); } after = get_the_timestamp; elapsed = after - stamp; print out the elapsed time;