//I need help with implementing my Priority Queue, I can\'t pass any my the test
ID: 3823859 • Letter: #
Question
//I need help with implementing my Priority Queue, I can't pass any my the tests.
import java.util.ArrayList;
public class PQ<T> {
private ArrayList<PQEntry<T>> PQArray;
int front, rear;
private static class PQEntry<T> {
private int priority;
private T item;
public PQEntry(T x, int n) {
priority = n;
item = x;
}
public int getPriority() {
return priority;
}
public void setPriority(int priority) {
this.priority = priority;
}
public T getItem() {
return item;
}
public void setItem(T item) {
this.item = item;
}
@Override
public String toString() {
return "(" + priority + ", " + item.toString() + ")";
}
}
public PQ() {
PQArray = new ArrayList<PQEntry<T>>();
front=0; rear =0;
}
public boolean isEmpty() {
return size() == 0;
}
public int size() {
return PQArray.size();
}
public void enqueue(T item, int priority) {
PQEntry entry = new PQEntry(item, priority);
PQArray.set(rear,entry);
rear++;
insertionSort(PQArray);
}
private void insertionSort(ArrayList<PQEntry<T>> list) {
int i, j;
for (i = 1; i < list.size(); i++) {
PQEntry tmp = list.get(i);
j = i;
while ((j > 0) && (list.get(j - 1).priority > tmp.priority)) {
list.set(j, list.get(j - 1));
j--;
}
list.set(j, tmp);
}
}
public T dequeue() {
T value = PQArray.get(front).getItem();
PQArray.remove(front);
front++;
return value;
}
@Override
public String toString() {
return PQArray.toString();
}
}
Explanation / Answer
/**
*
* @author Sam
*/
public class PQ<T> {
private ArrayList<PQEntry<T>> PQArray;
private static class PQEntry<T> {
private int priority;
private T item;
public PQEntry(T x, int n) {
priority = n;
item = x;
}
public int getPriority() {
return priority;
}
public void setPriority(int priority) {
this.priority = priority;
}
public T getItem() {
return item;
}
public void setItem(T item) {
this.item = item;
}
@Override
public String toString() {
return "(" + priority + ", " + item.toString() + ")";
}
}
public PQ() {
PQArray = new ArrayList<>();
}
public boolean isEmpty() {
return size() == 0;
}
public int size() {
return PQArray.size();
}
public void enqueue(T item, int priority) {
PQEntry entry = new PQEntry(item, priority);
PQArray.add(entry);//this adds entry to rear itself
insertionSort(PQArray);
}
private void insertionSort(ArrayList<PQEntry<T>> list) {
int i, j;
for (i = 1; i < list.size(); i++) {
PQEntry tmp = list.get(i);
j = i;
while ((j > 0) && (list.get(j - 1).priority > tmp.priority)) {
list.set(j, list.get(j - 1));
j--;
}
list.set(j, tmp);
}
}
public T dequeue() {
return PQArray.remove(0).getItem(); //you always remove the first element
}
@Override
public String toString() {
return PQArray.toString();
}
}
I have changed the dequeue and enqueue function. Please Note that when we remove an element from the arraylist, the remaining elements on the right is shifted left. So next time we remove an element, we remove the first element only, not the 2nd element.
I tried to keep the code as simple as possible. If incase you face any trouble with the code, please feel free to commnet below. I shall be glad to help you with the code.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.