Comparing array-based queue and linked-list based queue. Requirements: Task1: im
ID: 3756587 • Letter: C
Question
Comparing array-based queue and linked-list based queue.
Requirements:
Task1: implement a concrete LLQueue class that implements the IQueue interface as we discussed in the class, along with IQueue.java, ArrayQueue.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 and a link-list based queue. You have to use the ArrayQueue class provided in the class.
The template of LLQueue class is given below:
IQueue.java is given below
public interface IQueue {
int size();
boolean isEmpty();
Object first();
void add(Object item) throws QueueFullException;
Object remove();
}
ArrayQueue.java is given below
public class ArrayQueue implements IQueue {
private Object[] data;
private int CAP;
private int head;
private int tail;
public ArrayQueue(){
this(16);
}
public ArrayQueue(int capacity){
CAP=capacity;
data=new Object[capacity];
head=0;
tail=0;
}
public int size(){
if(head==tail)
return 0;
else if (head<tail)
return tail-head;
else
return tail+CAP-head;
}
public boolean isEmpty(){
return size()==0;
}
public void add(Object e) throws QueueFullException{
if(size()==CAP-1)
throw new QueueFullException("no space left");
data[tail]=e;
tail=(++tail)%CAP;
}
public Object first(){
if(isEmpty()) return null;
return data[head];
}
public Object remove(){
if(isEmpty()) return null;
Object answer=data[head];
head= (++head)%CAP;
return answer;
}
}
QueueFullException.java is given below
public class QueueFullException extends Exception {
public QueueFullException(String str){
System.out.println("QueueFullException:" + str);
}
public QueueFullException (){
this("No space left");
}
}
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.
Explanation / Answer
Here is the completed code for this problem. Comments are included, go through it, learn how things work and let me know if you have any doubts. If you are satisfied with the solution, please rate the answer. Thanks
// LLQueue.java
public class LLQueue implements IQueue {
private SinglyLL data;
private int size;
public LLQueue() {
//initializing fields
data=null;
size=0;
}
public int size() {
//returning current size
return size;
}
public boolean isEmpty() {
//returning true if queue is empty
return size==0;
}
public void add(Object item) {
//creating a new node
SinglyLL newnode=new SinglyLL(item);
//adding as the head node if queue is empty
if(data==null){
data=newnode;
}else{
//finding the tail node
SinglyLL temp=data;
while(temp.next!=null){
temp=temp.next;
}
//appending to the tail
temp.next=newnode;
}
//incrementing the size
size++;
}
public Object first() {
if(isEmpty()){
//queue is empty
return null;
}
//returning first value
return data.data;
}
public Object remove() {
if(isEmpty()){
return null;
}
//storing first value
Object removed=data.data;
//removing first value
data=data.next;
//decrementing size
size--;
//returning removed value
return removed;
}
/**
* private inner class to represent one node in the queue
*/
private class SinglyLL {
Object data;
SinglyLL next;
public SinglyLL(Object data) {
this.data = data;
next = null;
}
}
}
// Test.java
public class Test {
public static void main(String[] args) throws QueueFullException {
/**
* creating LLQueue and ArrayQueue objects
*/
LLQueue llQueue = new LLQueue();
ArrayQueue arrayQueue = new ArrayQueue(3500);
/**
* filling with 3000 random values
*/
for (int i = 0; i < 3000; i++) {
double value = Math.random();
llQueue.add(value);
arrayQueue.add(value);
}
System.out.println("Initial ArrayQueue size: " + arrayQueue.size());
System.out.println("Initial LLQueue size: " + llQueue.size());
System.out.println("Testing ArrayQueue");
//recording start time
long start = System.currentTimeMillis();
//performing 2000 enqueue-dequeue operations
for (int i = 0; i < 2000; i++) {
//generating random value
double value = Math.random();
//performing dequeue operation
arrayQueue.remove();
//performing enqueue operation
arrayQueue.add(value);
}
//recording stop time, finding time ellapsed in seconds
long end = System.currentTimeMillis();
double time = (end - start) / 1000.0;
System.out.println("It took " + time
+ " seconds for 2000 enqueue-dequeue operations");
/**
* similarly testing LLQueue
*/
System.out.println("Testing LLQueue");
start = System.currentTimeMillis();
for (int i = 0; i < 2000; i++) {
double value = Math.random();
llQueue.remove();
llQueue.add(value);
}
end = System.currentTimeMillis();
time = (end - start) / 1000.0;
System.out.println("It took " + time
+ " seconds for 2000 enqueue-dequeue operations");
}
}
//Output
Initial ArrayQueue size: 3000
Initial LLQueue size: 3000
Testing ArrayQueue
It took 0.016 seconds for 2000 enqueue-dequeue operations
Testing LLQueue
It took 0.047 seconds for 2000 enqueue-dequeue operations
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.