Algorithm Analysis of Queue Implementations

HOW TO ANSWER PART C????

Your solution to this assignment will take the form of a short report in a single document. It MUST be in PDF format.

The purpose of this assignment is to analyse two Queue implementations theoretically and experimentally.

As we have discussed in lectures, linked lists and arrays have different strengths and weaknesses in their performance. In this assignment, we will analyse how they affect the corresponding Queue implementations.

Part C (4 marks):

Draw up a table of the CPU time taken, for both the Queue Linked List implementation and the Queue Array implementation, to run your code from Part A for at least 4 different sizes of inputs, ranging from 100 strings to at least 100,000 strings. Graph the results also.

Do the results support your theoretical analysis of Part B?

Part A (8 marks):

Write a program that operates as follows:

The user is asked to specify a number of elements

In a loop, this number of Strings is added to a Queue; each String should be different (for example, you could include a different number in each one)

All of the Strings are then removed from the Queue

The program displays how long it took to enqueue the items and dequeue them. (Tip: you can use Javas System.nanoTime() to get the current time in nanoseconds; it returns a long, so if you subtract one from another, you get the number of elapsed seconds.)

ANSWER TO PART A:

package unit1Package;

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List;

public class QueueRunner {

public static void main(String[] args) throws NumberFormatException, IOException {

//The user is asked to specify a number of elements System.out.println("Please specify the desired no of elements to be entered: "); BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); int numberOfElements = reader.read();

/* * Storing the elements in a list * since to save the user entry * being done twice, this can also * be done in other ways you may like, */ List bufferList = new ArrayList(); for(int i=0; i

/* * Creating llQueue and performing * enqueue and dequeue along with * monitoring the time taken * for the actions */ LLQueue llQueue = new LLQueue(); long startTimeForLLQueueEnqueue = System.nanoTime(); for(String element : bufferList){ llQueue.enqueue(element); } long endTimeForLLQueueEnqueue = System.nanoTime();

double timeElapsedForLLQueueEnqueue = (endTimeForLLQueueEnqueue - startTimeForLLQueueEnqueue) / 1000000000; // converting from nano seconds to seconds System.out.println("Time elaped for enqueue operation in LLQueue: " + timeElapsedForLLQueueEnqueue);

long startTimeForLLQueueDequeue = System.nanoTime(); for(int i=0; i< numberOfElements; i++){ llQueue.dequeue(); } long endTimeForLLQueueDequeue = System.nanoTime();

double timeElapsedForLLQueueDequeue = (endTimeForLLQueueDequeue - startTimeForLLQueueDequeue) / 1000000000; // converting from nano seconds to seconds System.out.println("Time elaped for dequeue operation in LLQueue: " + timeElapsedForLLQueueDequeue);

/* * Creating ArrayQueue and performing * enqueue and dequeue along with * monitoring the time taken * for the actions */ ArrayQueue arrayQueue = new ArrayQueue(); long startTimeForArrayQueueEnqueue = System.nanoTime(); for(String element: bufferList){ arrayQueue.enqueue(element); } long endTimeForArrayQueueEnqueue = System.nanoTime();

double timeElapsedForArrayQueueEnqueue = (endTimeForArrayQueueEnqueue - startTimeForArrayQueueEnqueue) / 1000000000; // converting from nano seconds to seconds System.out.println("Time elaped for enqueue operation in ArrayQueue: " + timeElapsedForArrayQueueEnqueue);

long startTimeForArrayQueueDequeue = System.nanoTime(); for(int i=0; i< numberOfElements; i++){ arrayQueue.dequeue(); } long endTimeForArrayQueueDequeue = System.nanoTime();

double timeElapsedForArrayQueueDequeue = (endTimeForArrayQueueDequeue - startTimeForArrayQueueDequeue) / 1000000000; // converting from nano seconds to seconds System.out.println("Time elaped for dequeue operation in ArrayQueue: " + timeElapsedForArrayQueueDequeue);

} }

Part B (8 marks):

Calculate the theoretical complexity, using O notation, of:

Enqueue and Dequeue operations for a Queue implemented as an array

Enqueue and Dequeue operations for a Queue implemented as a linked list

Do not just write down the answers; provide full details of how you determined them.

ANSWER TO PART B:

when we implement a queue as an array

Time complexity :-

1. Enqueue :- time complexity will be O(1) . because in this operation we only insert the element at the end. so in array insertion of an element takes O(1) time.

2. Dequeue :- time complexity will be O(n) in worst case . because after deleting the first element of the array we have to resize the array so, it takes O(n) time.

when we implement a queue as a linked list

1.Enqueue :- time complexity will be O(1) . because we are only changing some pointer at the end of linked list we also have the pointer to the end of the linked list.

we are not using any loop.

2> Dequeue :- time complexity will be O(1) . for dequeue we have to delete the head node of linked list and deleting the head node of a linked list takes O(1) time .

REST OF CODE:

////////////////////////LLQueue.java///////////////////////////////

public class LLQueue implements Queue{

private SLinkedList queue;

public LLQueue() {

queue = new SLinkedList();

}

@Override

public void enqueue(Object n) {

queue.gotoTail();

queue.insertNext(n);

}

@Override

public Object dequeue() {

queue.gotoHead();

Object o = queue.getCurr();

queue.deleteHead();

return o;

}

@Override

public boolean isEmpty() {

return queue.isEmpty();

}

@Override

public boolean isFull() {

return false;

}

@Override

public Object front() {

queue.gotoHead();

return queue.getCurr();

}

}

/////////////////////Test.java//////////////////////////////

public class Test {

public static void main(String []args) {

LLQueue l = new LLQueue();

System.out.println("IsEmpty: "+l.isEmpty());

l.enqueue("one");

l.enqueue("two");

l.enqueue("three");

l.enqueue("four");

l.enqueue("five");

l.enqueue("six");

System.out.println("After Inserting elements");

System.out.println("IsEmpty: "+l.isEmpty());

while(!l.isEmpty()){

String s = (String)l.dequeue();

System.out.println(s);

}

System.out.println("After Deleting elements");

System.out.println("IsEmpty: "+l.isEmpty());

}

}

import javax.swing.JOptionPane; /** * : Array implementation of Queue ADT */ public class ArrayQueue implements Queue { protected Object Q[]; // array used to implement the queue protected int rear = -1; // index for the rear of the queue protected int capacity; // The actual capacity of the queue array public static final int CAPACITY = 1000; // default array capacity public ArrayQueue() { // default constructor: creates queue with default capacity this(CAPACITY); } public ArrayQueue(int cap) { // this constructor allows you to specify capacity capacity = (cap > 0) ? cap : CAPACITY; Q = new Object[capacity]; } public void enqueue(Object n) { if (isFull()) { JOptionPane.showMessageDialog(null, "Cannot enqueue object; queue is full."); return; } rear++; Q[rear] = n; } public Object dequeue() { // Can't do anything if it's empty if (isEmpty()) return null; Object toReturn = Q[0]; // shuffle all other objects towards 0 int i = 1; while (i <= rear) { Q[i-1] = Q[i]; i++; } rear--; return toReturn; } public boolean isEmpty() { return (rear < 0); } public boolean isFull() { return (rear == capacity-1); } public Object front() { if (isEmpty()) return null; return Q[0]; } } 

/* * THIS INTERFACE CANNOT BE CHANGED: Abstract Queue interface */ public interface Queue { // most important methods public void enqueue(Object n); // add an object at the rear of the queue public Object dequeue(); // remove an object from the front of the queue // others public boolean isEmpty(); // true if queue is empty public boolean isFull(); // true if queue is full (if it has limited storage) public Object front(); // examine front object on queue without removing it } 

public class SLinkedList { protected Node head; // head node of the list protected Node tail; // last position in the list protected Node curr; // node referencing current position in the list protected long size; // number of nodes in the list /** Default constructor that creates an empty list. */ public SLinkedList() { curr = tail = head = null; size = 0; } public long size() { return size; } public boolean isEmpty() { return (head == null); } public Object getCurr() { if (curr == null) // Verify that there is a current node return null; return curr.getElement(); } public boolean gotoHead() { if (isEmpty()) return false; curr = head; return true; } public boolean gotoNext() { if (curr == tail) return false; curr = curr.getNext(); return true; } public boolean gotoTail() { if (isEmpty()) return false; curr = tail; return true; } public void insertNext(Object el) { if (head == null) { insertHead(el); // If haven't inserted a head, do so now (for convenience) return; } Node newnode = new Node(el, curr.getNext()); // create new node with its next node equal to curr's next node curr.setNext(newnode); // update the next node of the current node to point to the new one size++; // update the tail if at the end of the list if (tail == curr) tail = newnode; // make this new node the current one curr = newnode; } public void deleteNext() { if (curr == null || curr.getNext() == null) return; // no next: list empty or already at end // update the tail if the node we are deleting is the tail if (tail == curr.getNext()) tail = curr; curr.setNext(curr.getNext().getNext()); // set curr's next equal to the next node's next // Note: Garbage collector will automatically clear up the node no longer referenced size--; } public void insertHead(Object el) { Node oldhead = head; head = new Node(el, oldhead); size++; curr = head; if (size == 1) // if this is the first node, it is both head and tail tail = head; } public void deleteHead() { if (head == null) return; // list already empty head = head.getNext(); size--; curr = head; if (size == 0) // if this was the only node, get rid of ref to tail as well as head tail = null; } }