使Java PriorityQueue成为一个稳定的优先级队列

我试图在Java中实现一个稳定的（先入先出）优先级队列。 假设密钥是一个名字，值是一个年龄，我知道我可以像这样做一个不稳定的优先级队列：

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

这几乎是我所需要的一切，除了在插入（或删除它们）时不维护键值对的顺序。

我发现了一个“解决方法”，它提供了基本上所有相同功能的LinkedList，只是它不包含带有比较器选项的构造函数，而且我觉得它必须更慢，因为我维护了值排序通过在每个队列操作之后调用Collections.sort() 。

所以我觉得有两个选项是我感兴趣的。首先，如何编辑上面的PriorityQueue来维护插入和删除顺序？ 或者第二，我如何强制我的LinkedList选项立即使用比较器，而不必在每个操作上调用排序？ 谢谢！

编辑：

感谢您发布的第一条评论中的好问题。 通过FIFO，我的意思是，对于具有相同值的键值对，首先应该提取放入的对。

Answer 1

你需要这样的东西：

 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的PriorityQueue自然是稳定的。 它是用Kotlin编写的，所以它可以代替Java代码java.util.PriorityQueue 。