22

我认为 add() 应该忽略重复，但我的输出有重复。如何不存储重复项？

我还想知道优先级队列如何检查两个元素是否重复。我猜它使用的是比较器，但我只是想确定一下。

谢谢

4

4 回答 4

19

这是PriorityQueue Javadoc的一部分：

此队列根据构造时指定的顺序对元素进行排序，该顺序根据其自然顺序（请参阅 Comparable）或根据使用的构造函数指定的 Comparator 指定。

所以是的，PriorityQueue 使用 Comparator （如果您将其指定为构造函数参数）或使用 compareTo(...) 方法（元素必须实现 Comparable 接口）。

PriorityQueue 允许重复。因此，如果您想避免这种情况，您需要实现自己的 Queue 版本。您可以在第 85 页的“Effective Java”中找到非常优雅的方法，如何做到这一点。或者，您可以扩展 PriorityQueue 类并覆盖 add 方法（这是放置 contains(...) 检查的理想场所）。

于 2012-05-06T10:26:02.153 回答
10

Java 中的 APriorityQueue对重复元素没有任何限制。如果要确保两个相同的项目永远不会同时出现在优先级队列中，最简单的方法是Set与优先级队列并行维护一个单独的项目。每次要将元素插入优先级队列时，您可以检查集合是否已经包含它，如果没有，则将其添加到集合和优先级队列中。每当您从优先级队列中删除一个元素时，也只需从集合中删除该元素。

或者，根据您打算在优先级队列上执行的操作，以及在您的情况下如何定义相等性，将其替换为单个可能是可行的，TreeSet因为这仍然允许您执行您将拥有的所有重要操作在优先队列中访问，同时它还不允许重复。

于 2012-05-06T10:20:33.987 回答
6

以下示例实现

import java.util.PriorityQueue;

public class NoDuplicates<E> extends PriorityQueue<E> 
{
    @Override
    public boolean offer(E e) 
    {
        boolean isAdded = false;
        if(!super.contains(e))
        {
            isAdded = super.offer(e);
        }
        return isAdded;
    }
    public static void main(String args[])
    {
        PriorityQueue<Integer> p = new NoDuplicates<Integer>();
        p.add(10);
        p.add(20);
        p.add(10);
        for(int i =0;i<=2;i++)
        {
            System.out.println(p.poll());
        }
        
    }
}

结果是

10
20
null

这表明它没有添加重复元素10。

于 2012-10-21T08:53:02.323 回答
3

集合是唯一忽略重复的东西。列表和队列没有。（LinkedList 是一个队列）

如果要删除重复项，可以检查 take() 条目是否与前一个条目相同并忽略它。您可以按照自己喜欢的方式进行比较。;)

于 2012-05-06T10:56:18.393 回答