对于家庭作业,我需要实现自己的 PriorityQueue 和 PriorityQueueSort。我使用泛型让它在没有排序功能的情况下工作,但现在我被困在这里..
public static void PriorityQueueSort(Iterable<?> list,
PriorityQueue<?,?> pq) {
if (!pq.isEmpty()) {
throw new IllegalArgumentException("Non-Empty PriorityQueue");
}
for (Object obj : list) {
}
}
我需要传入一个列表和一个空的 PriorityQueue,所以我对如何做到这一点的最佳猜测就在上面。我应该如何解决这个问题,以便我可以遍历具有未知类型的列表,并将该列表中具有正确类型的每个元素添加到优先级队列中?
编辑:
由于确定我没有提供足够的信息,因此这里有一些详细信息。
我有一个自定义 PriorityQueue 类和一个自定义 Entry 类,该类包含 K 类型的键和 V 类型的值。
我需要能够获取具有任何类型 T 的任何可迭代列表并遍历它,获取每个项目并将其添加到最初为空的 PriorityQueue 作为具有空值的键。然后我需要在我的 PriorityQueue 上不断调用 removeMin() 并将其按顺序添加回同一个列表对象中。
public class PriorityQueue<K extends Comparable<? super K>,V> {
private Entry<K,V> _head;
private Entry<K,V> _tail;
private int _size;
public PriorityQueue() {
this._head = null;
this._tail = null;
this._size = 0;
}
public int size() {
return _size;
}
public boolean isEmpty() {
return (size() == 0);
}
public Entry<K,V> min() {
if (_head == null) {
return null;
}
Entry<K,V> current = _head;
Entry<K,V> min = _head;;
while (current != null) {
if (current.compareTo(min) < 0) {
min = current;
}
current = current.getNext();
}
return min;
}
public Entry<K,V> insert(K k, V x) {
Entry<K,V> temp = new Entry<K,V>(k,x);
if (_tail == null) {
_tail = temp;
_head = temp;
}
else {
_tail.setNext(temp);
temp.setPrev(_tail);
_tail = temp;
}
return temp;
}
public Entry<K,V> removeMin() {
Entry<K,V> smallest = min();
smallest.getPrev().setNext(smallest.getNext());
smallest.getNext().setPrev(smallest.getPrev());
return smallest;
}
public String toString() {
return null;
}
public static <K> void PriorityQueueSort(Iterable<? extends K> list,
PriorityQueue<? super K, ?> queue) {
for (K item : list) {
queue.insert(item, null);
}
list.clear();
}
public static void main(String[] args) {
PriorityQueue<Integer, Integer> pq =
new PriorityQueue<Integer, Integer>();
pq.insert(4, 2);
pq.insert(5, 1);
System.out.println(pq.min().toString());
}
}