Question: Task: Implementating the following Java interface and classes: Interface: PQueue Abstract class: AbstractPQueue Concrete classes: UnsortedPQueue and SortedPQueue Requirements: The implementation of PQueue, AbstractPQueue and
Task: Implementating the following Java interface and classes:
Interface: PQueue
Abstract class: AbstractPQueue
Concrete classes: UnsortedPQueue and SortedPQueue
Requirements:
The implementation of PQueue, AbstractPQueue and UnsortedPQueue must follow what I discussed in the class. Any other implementation will NOT receive any credit.
Implement the SortedPQueue classes by using either ArrayList or LinkedList.
List, ArrayList and LinkedList should be based on your earlier implementation in HW5. For those who didn't have a working version of the List, ArrayList and LinkedList implementation, please contact the TA for the assistance.
Test: write a performance comparison program to compare the performance of the insert() and removeMin() operation of the two PQueues in running time. To do that, you need to construct one UnsortedPQueue and one SortedPQueue, respectively, by using the same data source, 1,000 data elements. In the performance comparison test, try to time the operation of inserting 1,000 elements and time the operation of removing the same 1,000 elements. Note, try to obtain the time stamps in milliseconds. You should provide a report similar to the following format:
UnsortedPQueue Insertion: xxx milliseconds SortedPQueue Insertion: xxx milliseconds UnsortedPQueue RemoveMin: xxx milliseconds SortedPQueue RemoveMin: xxx milliseconds
Please see implementation of classes below. Let me know if you need anyhting else.
LinkedList Implementation public class LinkedList implements List {
private Link head;
private int size;
/**
* constructor to initialize the list
*/
public LinkedList() {
head = null;
size = 0;
}
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public Object get(int index) throws OutRangeException {
if (index < 0 || index >= size) {
throw new OutRangeException("Invalid index " + index);
}
// getting a reference
Link reference = head;
int i = 0;
/**
* looping until the required index is found
*/
while (i < index) {
reference = reference.getNext();
i++;
}
// returning element at given index
return reference.getData();
}
@Override
public void set(int index, Object o) throws OutRangeException {
if (index < 0 || index >= size) {
throw new OutRangeException("Invalid index " + index);
}
Link reference = head;
int i = 0;
while (i < index) {
reference = reference.getNext();
i++;
}
reference.setData(o);
}
@Override
public void add(int index, Object o) throws OutRangeException {
if (index < 0 || index > size) {
throw new OutRangeException("Invalid index " + index);
}
if (index == 0) {
/**
* Adding head element
*/
Link link = new Link(o);
link.setNext(head);
head = link;
size++;
} else {
Link reference = head;
int i = 0;
while (i < index - 1) {
reference = reference.getNext();
i++;
}
/**
* adding new element in the middle of current reference and next
* node (if exists)
*/
Link link = new Link(o);
link.setNext(reference.getNext());
reference.setNext(link);
size++;
}
}
@Override
public Object remove(int index) throws OutRangeException {
if (index < 0 || index >= size) {
throw new OutRangeException("Invalid index " + index);
}
if (index == 0) {
Object data = head.getData();
head = head.getNext();
size--;
return data;
}
Link reference = head;
int i = 0;
while (i < index - 1) {
reference = reference.getNext();
i++;
}
Object data = reference.getNext().getData();
/**
* making current reference point to the next of next element (if
* exists), hereby dropping the middle element
*/
reference.setNext(reference.getNext().getNext());
size--;
return data;
}
@Override
public String toString() {
String data = "[";
Link reference = head;
for (int i = 0; i < size; i++) {
data += reference.getData();
if (i != size - 1) {
data += ",";
}
reference = reference.getNext();
}
data += "]";
return data;
}
}
ArrayList Implementation
public class ArrayList implements List {
// attributes
private Object items[];
private int size;
/**
* constructor with argument to set the capacity of array
*/
public ArrayList(int capacity) {
items = new Object[capacity];
size = 0;
}
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public Object get(int index) throws OutRangeException {
if (index < 0 || index >= size) {
throw new OutRangeException("Invalid index " + index);
}
// returning element at given index
return items[index];
}
@Override
public void set(int index, Object o) throws OutRangeException {
if (index < 0 || index >= size) {
throw new OutRangeException("Invalid index " + index);
}
// setting new element at given index
items[index] = o;
}
@Override
public void add(int index, Object o) throws OutRangeException {
if (index < 0 || index > size) {
throw new OutRangeException("Invalid index " + index);
}
if (size < items.length) {
/**
* shifting following elements to the right
*/
for (int i = size - 1; i >= index; i--) {
items[i + 1] = items[i];
}
/**
* Adding element at index
*/
items[index] = o;
size++;
}
}
@Override
public Object remove(int index) throws OutRangeException {
if (index < 0 || index >= size) {
throw new OutRangeException("Invalid index " + index);
}
Object item = items[index];
/**
* Shifting remaining elements to the left to occupy the vacant space
*/
for (int i = index; i < size - 1; i++) {
items[i] = items[i + 1];
}
size--;
return item;
}
@Override
public String toString() {
/**
* returns a String representation of list
*/
String data = "[";
for (int i = 0; i < size; i++) {
data += items[i];
if (i != size - 1) {
data += ",";
}
}
data += "]";
return data;
} }
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help