Priority Queues mit verketteten Listen
In Priority Queues werden Objekte mit einer ganzzahligen Priorität eingefügt. Entnimmt man ein Element, wird immer das Element mit der höchsten Priorität ausgegeben.
Implementieren Sie Priority Queues mit doppelt verkettete Listen. Diese werden am Ende von Kapitel 5 behandelt (siehe entsprechendes Video auf AMIGO). In der Liste sollen sich die Elemente absteigend sortiert nach ihrer Priorität befinden. Durchlaufen und manipulieren Sie die Liste imperativ (wie in der ADS-Vorlesung). Verwenden Sie separate Knoten head und tail für Anfang und Ende der Liste. Implementieren Sie folgende Methoden:
void add(T obj, int priority): Fügt ein Objekt an passender Stelle in die Liste ein.T pop(): entfernt das Element mit höchster Priorität und liefert das Objekt zurück (bzw. null, falls die Queue leer ist).void removeAll(int priority): entfernt alle Elemente mit der gegebenen Priorität.
package de.hsrm.ads;
public class DLinkedPQueue<T> {
Node head;
Node tail;
public class Node {
T obj;
int priority;
Node next;
Node prev;
public Node(T obj, int priority) {
this.obj = obj;
this.priority = priority;
}
}
public DLinkedPQueue() {
// FIXME: implement
}
public void add(T obj, int priority) {
// FIXME: implement
}
public T pop() {
// FIXME: implement
}
public void removeAll(int priority) {
// FIXME: implement
}
public static void main(String[] args) {
}
}
Subato
