Question

CODE MUST NOT REFERENCE java.util.PriorityQueue

CODE MUST NOT REFERENCE java.util.PriorityQueue

CODE MUST BE COPY PASTE FRIENDLY AND SCREENSHOTS MUST BE INCLUDED SHOWING THAT IT WORKS.

6. Implement a priority queue using java.util.Stack as the base data type. Your code must not reference java.util.PriorityQueue! You may need several Java classes for this one to define Entry, one for the priority queue, and one for the main program. It's acceptable use inner class if you'd rather have everyone contained in one.java file. Your priority queue must implement the following methods: insert(Entry E); removeMin(); -returns the entry with the lowest key value Where Entry is: int k; String v; The core data storage should be: Stack<Entry> sl; Stack<Entry> s2; Hint: you may need more than one stack to fully implement the queue! The following test cases should be hard-coded into your program: Input (in order) Output (in order) (3, "test") (3,"test") (4,"every") (4,"every") (5, "edge") (5, "edge") (10,"smoked") (1, "good") (5,"quality") (5, "quality") (12, "beef) (10,"smoked") (1, "good") (12, "beef") (9,"or") (3, "to") (3, "to") (5, "be") (5, "be") (9,"or") (10,"not") (10,"not") The program must work for any correct sequence of entries, not just the test cases. Rubric: Works for other values, not just test cases: (-5 if fails) Program operation is correct: (-10 if fails) Code must not reference java.util.PriorityQueue:(-10 if fails) Priority queue as stack (or two stacks): 5 points Test cases included in program: 5 points

Answer 1

CODE:

Entry.java

package testpriorityqueue;

public class Entry
{
int k;
String v;
  
//constructor for Entry.
public Entry(int k, String v)
{
this.k = k;
this.v = v;
}
  
//toString() - to print the values in the desired format.
@Override
public String toString()
{
return "("+k+", \""+v+"\")";
}
}

Screenshots:

1 package testpriorityqueue; 2 3 public class Entry 4 5 int ki String vi 6 7 8 9 //constructor for Entry. public Entry (int k, String v) 10 I- { 11 this.k = k; this.v = Vi 12 13 14 ] 15 16 //toString() to print the values in the desired format. @Override public String toString() o 18 19 20 return "("+k+", ""+v+"|")"; 21 22

PriorityQueue.java

package testpriorityqueue;

import java.util.Stack;

public class PriorityQueue {
//s1 - holds the priority queue.
private Stack<Entry> s1;
//s2 - supports s1 for achieving priority queue using stack.
private Stack<Entry> s2;
  
//constructor for PriorityQueue.
public PriorityQueue()
{
s1 = new Stack();
s2 = new Stack();
}
  
//while s1 is not empty,
//top of s1(stack)'s key is compared with the E's key.
//if the top value is smaller than E,
//top of the stack s1 is popped and added to stock s2.
//this repeats till either top of s1's key
//is greater than E's key or till s1 becomes empty.
//the E is added to s1.
//then all the entries in the stack s2 is popped and added to the stack s1.
public void insert(Entry E)
{
//while s1 is not empty,
while(!s1.empty())
{
//top of s1(stack)'s key is compared with the E's key.
if(s1.peek().k < E.k)
{
//if the top value is smaller than E,
//top of the stack s1 is popped and added to stock s2.
s2.add(s1.pop());
}
else
{
break;
}
}
//then E is added to s1.
s1.add(E);
//then all the entries in the stack s2 is popped and added to the stack s1.
while(!s2.empty())
{
s1.add(s2.pop());
}
}
  
public Entry removeMin()
{
//returns null is stack is empty, else returns s1's top entry.
return s1.empty()?null:s1.pop();
}

}
Screenshots:

1 package testpriorityqueue; 2 3 import java.util.Stack; 4 5 public class PriorityQueue { //31 - holds the priority queue. private Stack<Entry> sl; 1/32 - supports sl for achieving priority queue using stack. private Stack<Entry> 32; 8 //constructor for PriorityQueue. public PriorityQueue () o LO 11 12 13 14 15 16 17 18 19 sl = new Stack(); 32 = new Stack(); 20 21 22 / /while sl is not empty, //top of 31 (stack) 's key is compared with the E's key. //if the top value is smaller than E, //top of the stack sl is popped and added to stock 32. //this repeats till either top of sl's key //is greater than E's key or till sl becomes empty. //the E is added to sl. //then all the entries in the stack s2 is popped and added to the stack sl. public void insert (Entry E) 23 24 25 27 - // while sl is not empty while (!sl.empty()) 30 31 32 //top of 31 (stack) 's key is compared with the E's key. if (31.peek(). < E.k) 33 35 36 //if the top value is smaller than E, //top of the stack sl is popped and added to stock s2. 32.add(s1.pop()); 37 38 else {

while (!s1.empty()) 29 30 31 32 33 34 35 //top of 31 (stack) 's key is compared with the E's key. if(31.peek().k < E.k) //if the top value is smaller than E, //top of the stack sl is popped and added to stock s2. 32.add(sl.pop()); 36 37 else 38 39 40 break; 41 } 42 43 44 45 46 47 //then E is added to sl. sl.add(E); //then all the entries in the stack s2 is popped and added to the stack 31. while (!s2.empty()) { 48 sl.add(32.pop()); } 50 51 52 53 public Entry removeMin() 보 54 //returns null is stack is empty, else returns sl's top entry. return sl.empty()?null:31.pop(); 55 56 57 58 59

TestPriorityQueue.java

package testpriorityqueue;
public class TestPriorityQueue {
public static void main(String[] args) {
//creating object for PriorityQueue.
PriorityQueue pq = new PriorityQueue();
//inserting entries.
pq.insert(new Entry(3, "test"));
pq.insert(new Entry(4, "every"));
pq.insert(new Entry(5, "edge"));
//removing entries.
System.out.println(pq.removeMin());
System.out.println(pq.removeMin());
System.out.println(pq.removeMin());
System.out.println("");
//inserting entries.
pq.insert(new Entry(10, "smoked"));
pq.insert(new Entry(5, "quality"));
pq.insert(new Entry(12, "beef"));
pq.insert(new Entry(1, "good"));
//removing entries.
System.out.println(pq.removeMin());
System.out.println(pq.removeMin());
System.out.println(pq.removeMin());
System.out.println(pq.removeMin());   
System.out.println("");
//inserting entries.
pq.insert(new Entry(9, "or"));
pq.insert(new Entry(3, "to"));
pq.insert(new Entry(5, "be"));
pq.insert(new Entry(10, "not"));
//removing entries.
System.out.println(pq.removeMin());
System.out.println(pq.removeMin());
System.out.println(pq.removeMin());
System.out.println(pq.removeMin());
}
}
Screenshots:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 package testpriorityqueue; public class TestPriorityQueue { public static void main(String[] args) { //creating object for PriorityQueue. PriorityQueue pq = new PriorityQueue (); //inserting entries. pq.insert(new Entry(3, "test")); pq.insert (new Entry(4,"every")); pq.insert(new Entry(5, "edge")); //removing entries. System.out.println(pq.removeMin()); System.out.println(pq.removeMin()); System.out.println(pq.removeMin()); System.out.println(""); //inserting entries. pq.insert (new Entry(10, "smoked")); pq.insert (new Entry(5, "quality")); pq.insert (new Entry(12, "beef")); pq.insert (new Entry(1, "good")); //removing entries. System.out.println(pq.removeMin()); System.out.println(pq.removeMin()); System.out.println(pq.removeMin()); System.out.println(pq.removeMin()); System.out.println(""); //inserting entries. pq.insert (new Entry(9,"or")); pq.insert (new Entry(3, "to")); pq.insert(new Entry(5, "be")); pq.insert (new Entry(10, "not")) ;|| //removing entries. System.out.println(pq.removeMin()); System.out.println(pq.removeMin()); System.out.println(pq.removeMin()); System.out.println(pq.removeMin()); 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 WWW WWW 37

Sample I/O:

run: (3, "test") (4, "every") (5, "edge") (1, "good") (5, "quality") (10, "smoked") (12, "beef") (3, "to") (5, "be") (9,"or") (10, "not") BUILD SUCCESSFUL (total time: 1 second) 1

//Hope this Helps!

//Please consider giving this answer a thumbs up.

//If this answer didn't satisfies your requirements or needs modifications, please let me know in the comment section before giving a thumbs down.

//Thank you! Stay Safe!!!