Eine Java PriorityQueue zu einer stabilen Prioritätswarteschlange machen

Question

Ich versuche eine stabile (first in first out) Prioritätswarteschlange in Java zu implementieren. Angenommen, dass der Schlüssel ein Name ist und der Wert ist ein Alter, ich weiß, ich eine instabile Prioritätswarteschlange wie diese machen kann:

Queue<Map.Entry<String, Integer>> pq = new PriorityQueue<Map.Entry<String, Integer>>(100, ageComparator); 

Das tut so ziemlich alles, was ich brauche es zu, mit der Ausnahme, dass es nicht der Fall ist Die Reihenfolge der Schlüssel/Wert-Paare beibehalten, während ich sie einfüge (oder sie entferne).

Ich habe eine "umgehung" gefunden, indem ich eine LinkedList gemacht habe, die im Wesentlichen alle die gleiche Funktionalität bietet, außer dass es keinen Konstruktor mit einer Komparatoroption enthält, und ich denke, dass es seitdem langsamer sein muss Ich bestelle Wertbestellung durch Aufruf von Collections.sort() nach jeder Warteschlangenoperation.

Also denke ich, dass es wirklich zwei Optionen gibt, die mich interessieren. Erstens, wie könnte ich die PriorityQueue oben bearbeiten, um die Einfüge- und Entfernungsreihenfolge beizubehalten? Oder zweitens, wie kann ich meine LinkedList-Option zwingen, sofort einen Komparator zu verwenden, anstatt bei jeder Operation eine Sortierung aufrufen zu müssen? Vielen Dank!

EDIT:

Vielen Dank für die gute Frage in dem ersten Kommentar, geschrieben wurde. Mit FIFO meine ich, dass für Schlüssel/Wert-Paare mit gleichen Werten zuerst das zuerst eingegebene Paar extrahiert werden soll.

Answer 1

Sie brauchen etwas wie folgt aus:

import java.util.AbstractMap; 
import java.util.Comparator; 
import java.util.PriorityQueue; 
import java.util.concurrent.atomic.AtomicInteger; 

public class PriorityTest { 
    @SuppressWarnings("serial") 
    private static class Entry extends AbstractMap.SimpleEntry<String, Integer> { 
    private final static AtomicInteger seq = new AtomicInteger(0); 
    final int order; 
    public Entry(final String _key, final Integer _value) { 
     super(_key, _value); 
     order = seq.incrementAndGet(); 
    } 
    } 

    private static class OrderedComparator implements Comparator<Entry> { 
    @Override 
    public int compare(final Entry _e1, final Entry _e2) { 
     int r = _e1.getValue().compareTo(_e2.getValue()); 
     if (r == 0) 
     return Integer.compare(_e1.order, _e2.order); 
     return r; 
    } 
    } 

    public static void main(String[] args) { 
    final PriorityQueue<Entry> pq = new PriorityQueue<Entry>(10, new OrderedComparator()); 
    pq.add(new Entry("Jane", 22)); 
    pq.add(new Entry("John", 15)); 
    pq.add(new Entry("Bill", 45)); 
    pq.add(new Entry("Bob", 22)); 
    while(!pq.isEmpty()) { 
     System.out.println(pq.remove()); 
    } 
    } 
} 

Answer 2

Keap-based PriorityQueue ist natürlich stabil. Es ist in Kotlin geschrieben, so kann es java.util.PriorityQueue in Java-Code ersetzen.