I know this is long, but I have no idea, and I need this to pass. I need it to b
ID: 3556419 • Letter: I
Question
I know this is long, but I have no idea, and I need this to pass. I need it to be in Java, and works with the code given below. Please help.
Using the MyLinkedList class that we developed in assignment #6 as a starting point, you may modify the class code OR extend the class to create a generic priority queue.
For this exercise, a priority queue is defined as a queue of nodes that contain both generic data AND and an integer value representing priority. Within the LinkedList used to form the queue, nodes are inserted in sorted order BY PRIORITY. The enqueue method should insert every new node BEHIND every other node of lower priority, but IN FRONT of evey other node in the list that has the same or higher priority. This retains the first-in-first-out property for any given priority level.
Your solution should create a new PriorityQueue for String data with:
PriorityQueue pq = new PriorityQueue
If I wanted to enqueue the String
Explanation / Answer
DO RATE if satisfied.
Look for "Change#" for all the changes i made.
//Change#1 classname
public class PriorityQueue<E> implements Comparable<E> {
private class Node {
E data;
int priority;
Node next;
public Node(E s) {
data = s;
priority = 0;
next = null;
}
public Node(E s, int pr){
data = s;
priority = pr;
next = null;
}
}
private Node head;
private Node tail;
private int count;
public E front() {
return head.data;
}
public E back() {
return tail.data;
}
public int length() {
return count;
}
public boolean isEmptyList() {
return count == 0;
}
public void initializeList() {
head = null;
tail = null;
count = 0;
}
public void print() {
Node temp = head;
for (int i = 0; i < count; i++) {
System.out.print(temp.data + " ");
if (i < count - 1)
temp = temp.next;
}
System.out.println();
}
public int search(E s) {
Node temp = head;
for (int i = 0; i < count; i++) {
if (((Comparable) temp.data).compareTo(s) == 0) {
return i;
}
if (i < count - 1)
temp = temp.next;
}
return -1;
}
//Change#2
public PriorityQueue clone() {
PriorityQueue newList = new PriorityQueue();
Node n = head;
for (int i = 0; i < count; i++) {
newList.insertBack(n.data);
if (n.next != null)
n = n.next;
}
return newList;
}
//Change#3
public void insertFront(E s) {
insertFront(s, 0);
}
//Change#4
public void insertFront(E s, int pr) {
Node n = new Node(s, pr);
if (count == 0) {
head = n;
tail = n;
} else {
n.next = head;
head = n;
}
count++;
}
//Change#4
public void insertBack(E s) {
insertBack(s, 0);
}
//Change#5
public void insertBack(E s, int pr) {
Node n = new Node(s, pr);
if (count == 0) {
head = n;
tail = n;
} else {
tail.next = n;
tail = n;
}
count++;
}
public E deleteFront() {
if (count > 0) {
E s = head.data;
head = head.next;
count--;
if (count == 0)
tail = null;
return s;
}
return null;
}
public E deleteBack() {
if (count > 0) {
if (count == 1)
return deleteFront();
else {
Node temp = head;
for (int i = 0; i < count - 1; i++)
temp = temp.next;
E s = tail.data;
tail = temp;
count--;
return s;
}
}
return null;
}
public int delete(E s) {
int index = search(s);
if (index < 0)
return -1;
else {
if (index == 0)
deleteFront();
else if (index == count - 1)
deleteBack();
else {
Node n = head;
for (int i = 0; i < index - 1; i++)
n = n.next;
n.next = n.next.next;
count--;
}
return index;
}
}
public void insertSorted(E s) {
if (count == 0 || ((Comparable) s).compareTo(head.data) <= 0)
insertFront(s);
else if (((Comparable) s).compareTo(tail.data) >= 0)
insertBack(s);
else {
Node n = new Node(s);
Node temp = head;
while (((Comparable) s).compareTo(temp.next.data) > 0)
temp = temp.next;
n.next = temp.next;
temp.next = n;
count++;
}
}
public int compareTo(E obj) {
if (((Comparable) this).compareTo(obj) < 0)
return -1;
else if (((Comparable) this).compareTo(obj) > 0)
return 1;
else
return 0;
}
//Change#6 all below this
public void enqueue(E s, int pr){
if (count == 0 || pr <= head.priority)
insertFront(s, pr);
else if ( pr > tail.priority )
insertBack(s, pr);
else {
Node n = new Node(s, pr);
Node temp = head;
while (temp.next!= null && n.priority > temp.next.priority)
temp = temp.next;
n.next = temp.next;
temp.next = n;
count++;
}
}
public E dequeue(){
if( count==0 )
return null;
else {
E temp = tail.data;
Node n = head;
while( n.next!=null && n.next != tail)
n = n.next;
n.next = null;
tail = n;
count--;
return temp;
}
}
public void printReverse(){
int cnt = this.count;
for(int i=0; i<cnt; i++){
int pr = tail.priority;
E obj = this.dequeue();
System.out.print(obj + " ");
this.insertFront(obj, pr);
}
System.out.println("");
}
}