将Java PriorityQueue转换为稳定的优先级队列

本文介绍了将Java PriorityQueue转换为稳定的优先级队列的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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

I'm trying to implement a stable (first in first out) priority queue in Java. Supposing that the key is a name and the value is an age, I know I can make an unstable priority queue like this:

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

这几乎可以满足我所需要的一切，除了它不维护密钥的顺序-value对，因为我插入它们（或删除它们）。

This does pretty much everything that I need it to, except that it doesn't maintain order of key-value pairs as I insert them (or remove them).

我通过制作LinkedList找到了解决方法，它提供了基本上所有相同的功能，除了它不包含带比较器选项的构造函数，我觉得它必须慢，因为我通过在每个之后调用 Collections.sort（）来维护值排序排队操作。

I've found a "work around" by making a LinkedList, which offers essentially all of the same functionality, except that it doesn't include a constructor with a comparator option, and I feel that it must be slower since I maintain value ordering by calling Collections.sort() after each queue operation.

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

So I guess that really there are two options that I'm interested in. First, how could I edit the PriorityQueue above to maintain insertion and removal order? Or second, how could I force my LinkedList option to use a comparator immediately rather than having to call a sort on each operation? Thanks!

编辑：

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

Thanks for the good question in the first comment that was posted. By FIFO, I mean that for key-value pairs with equal values, the pair which is put in first should be extracted first.

推荐答案

<你需要这样的东西：

You need something like this:

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()pareTo(_e2.getValue()); if (r == 0) return Integerpare(_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()); } } }