mport java.util.Scanner; import class17.HeapPriorityQueue; import class17.Priori
ID: 3825953 • Letter: M
Question
mport java.util.Scanner; import class17.HeapPriorityQueue; import class17.PriorityQueue; /*************** * Homework D * * Edit the following file and save it as Dxxxxxxxx.java where xxxxxxxx is * replaced by your 8 digit ID number. Change the class name to reflect this * file name. Include a comment with your name at the top of the program in case * there is a problem with automatic recognition of your ID number. Submit this * one file as an email attachment to alexander.ryba@qc.cuny.edu * * 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
Answer:
Note: User hasn’t provided the PriorityQueue class. So I am unable to run the code.
Modified Code:
import java.util.Scanner;
import class17.HeapPriorityQueue;
import class17.PriorityQueue;
/***************
* Homework D
*
* Edit the following file and save it as Dxxxxxxxx.java where xxxxxxxx is
* replaced by your 8 digit ID number. Change the class name to reflect this
* file name. Include a comment with your name at the top of the program in case
* there is a problem with automatic recognition of your ID number. Submit this
* one file as an email attachment to alexander.ryba@qc.cuny.edu
*
* 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 {
if (size <= 0) throw new Exception("Queue EMPTY");
K tmp=data[0];
int indx=0;
for(int kk=1;kk<size;kk++)
{
if(data[kk]<tmp)
{
tmp=data[kk];
indx=kk;
}
}
for(int kk=indx;kk<size-1;kk++)
{
data[kk]=data[kk+1];
}
size--;
return tmp;
}
}
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==0)
{
data[size]=x;
size++;
return;
}
else
{
for(int kk=size-1;kk>=0;kk--)
{
if(data[kk]<x)
continue;
}
for(int aa=size-1;aa>kk;aa--)
{
data[aa+1]=data[aa];
}
data[kk]=x;
size++;
}
}
// 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();
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.