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

Question

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

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

这几乎完成了我需要它做的所有事情，除了它在我插入（或移除）键值对时不保持它们的顺序。

编辑：

感谢你在第一条评论中提出的好问题。我所说的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());
    }
  }
}