Remove any initial package declaration that might be added to your file in * cas
ID: 3807855 • Letter: R
Question
Remove any initial package declaration that might be added to your file in * case you edit it in eclipse. * * The goal of the homework is to create two ArrayList based implementations of * a Priority Queue as explained in Section 9.2 (in 9.2.4 and 9.2.5) of the * textbook. * * These are to be made by completing the classes PQunsorted and PQsorted as * given below. In completing these classes you should only use the instance * members array, capacity and size, but you should add implementations for the * required Priority Queue methods. Only change their methods as indicated by * TODO instructions * * Finally, you should make the main program display your name and 8 digit ID * number. * * Your implementations should work interchangeably with the heap based version. * The main program runs both your implementations and the (correct) heap based * one from class at once. When your code is correct, it should produce any * output three times over. ********************************************************************/ class PQunsorted<K extends Comparable<K>> implements PriorityQueue<K> { K[] data; int size; int capacity; public PQunsorted() { capacity = 100; size = 0; data = (K[]) new Comparable[capacity]; } // easy insertion public void insert(K x) throws Exception { if (size >= capacity) throw new Exception("Queue full"); data[size++] = x; } public K removeMin() throws Exception { // TODO complete code to remove min here return null; } } class PQsorted<K extends Comparable<K>> implements PriorityQueue<K> { K[] data; int size; int capacity; public PQsorted() { capacity = 100; size = 0; data = (K[]) new Comparable[capacity]; } public void insert(K x) throws Exception { // TODO complete code to insert x, keeping the array sorted so the min is at the end } // easy removal in this implementation public K removeMin() throws Exception { if (size == 0) throw new Exception("Queue Empty"); return data[--size]; } } // ---------------------- main program to test implementations --- class D00000000 { public static void main(String args[]) { PriorityQueue<String> pq = new HeapPriorityQueue<>(); PriorityQueue<String> pqU = new PQunsorted<>(); PriorityQueue<String> pqS = new PQsorted<>(); boolean done = false; Scanner sc = new Scanner(System.in); while (!done) { try { // add your name into the following print statement System.out.println( " Program by: xxxx ---- cmds are + - Q: >>"); String cmd = sc.next(); String entry = null; char command = cmd.charAt(0); if (command == '+') entry = sc.next(); switch (cmd.charAt(0)) { case 'Q': done = true; break; case '+': pq.insert(entry); pqU.insert(entry); pqS.insert(entry); break; case '-': System.out.print(pq.removeMin() + " "); System.out.print(pqU.removeMin() + " "); System.out.print(pqS.removeMin() + " "); break; } } catch (Exception e) { System.out.println("Error " + e.toString()); } } sc.close(); } }
Explanation / Answer
class PQunsorted<K extends Comparable<K>> implements PriorityQueue<K> {
K[] data;
int size;
int capacity;
public PQunsorted() {
capacity = 100;
size = 0;
data = (K[]) new Comparable[capacity];
}
// easy insertion
public void insert(K x) throws Exception {
if (size >= capacity) throw new Exception("Queue full");
data[size++] = x;
}
public K removeMin() throws Exception {
// TODO complete code to remove min here
//here array is not sorted..
//so we have to search each and every element
int i=0;
int min = 0;
if(size == 0)return null;//if size is zero then
while(i<size)//finding min
{
if(data[min]>data[i])
min=i;//updating min
i++;
}
i=min;
K swap;
while(i<size-1)//removing min
{
swap = data[i];
data[i]=data[i+1];
data[i+1]=swap;
i++;
}
size--;//removing min element
K Min = data[i];
return Min;
}
}
class PQsorted<K extends Comparable<K>> implements PriorityQueue<K> {
K[] data;
int size;
int capacity;
public PQsorted() {
capacity = 100;
size = 0;
data = (K[]) new Comparable[capacity];
}
public void insert(K x) throws Exception {
// TODO complete code to insert x, keeping the array sorted so the min is at the end
if (size >= capacity) throw new Exception("Queue full");
data[size++]=x;//placing at the end
int i,j;
K l;
for(i=size-1;i>=1;i++)
{
if(data[i]<=data[i-1])
break;//breaking cause found the right position
else
{
l=data[i];
data[i]=data[i-1];
data[i-1]=l;
}
}
}
// easy removal in this implementation
public K removeMin() throws Exception {
if (size == 0) throw new Exception("Queue Empty");
return data[--size];
}
}
// ---------------------- main program to test implementations ---
class D00000000 {
public static void main(String args[]) {
PriorityQueue<String> pq = new HeapPriorityQueue<>();
PriorityQueue<String> pqU = new PQunsorted<>();
PriorityQueue<String> pqS = new PQsorted<>();
boolean done = false;
Scanner sc = new Scanner(System.in);
while (!done) {
try {
// add your name into the following print statement
System.out.println(
" Program by: xxxx ---- cmds are + - Q: >>");
String cmd = sc.next();
String entry = null;
char command = cmd.charAt(0);
if (command == '+')
entry = sc.next();
switch (cmd.charAt(0)) {
case 'Q':
done = true;
break;
case '+':
pq.insert(entry);
pqU.insert(entry);
pqS.insert(entry);
break;
case '-':
System.out.print(pq.removeMin() + " ");
System.out.print(pqU.removeMin() + " ");
System.out.print(pqS.removeMin() + " ");
break;
}
} catch (Exception e) {
System.out.println("Error " + e.toString());
}
}
sc.close();
}
}