优先队列 vs 链表 Java

Question

我正在解决一个与 BFS 相关的问题。我使用了优先队列（PriorityQueue），但是得到了错误的答案，然后我使用了 LinkedList，得到了正确的答案。我无法找到它们之间的区别。以下是两个代码。为什么两个答案不同？

Code1:    
        LinkedList q=new LinkedList();
        q.add(src);
        dist[src]=0;
        visited[src]=1;
        while(!q.isEmpty()){
            u=(int)(Integer) q.remove(0);
            for (int k = 0; k < n; k++) {
                if(a[u][k]==1 && visited[k]==0)
                {
                    dist[k]=dist[u]+1;
                    q.add(k);
                    visited[k]=1;
                }   
            }
        }

Code 2: 
    PriorityQueue<Integer> q= new PriorityQueue<>();
        q.add(src);            
        dist[src]=0;
        visited[src]=1;
        while(!q.isEmpty()){
            u=q.remove();               
            for (int k = 0; k < n; k++) {
                if(a[u][k]==1 && visited[k]==0)
                {
                    dist[k]=dist[u]+1;
                    q.add(k);
                    visited[k]=1;
                }   
            }
        }

当我使用邻接表而不是邻接矩阵时，优先队列实现给出了正确的答案。

- vikkz

---

你的代码想要做什么？当你在调试器中查看它时，在哪一行它没有按照你的期望执行？一个只有一个元素的LinkedList和一个只有一个元素的PriorityQueue做的事情是相同的。 - Peter Lawrey

这是一个简单的BFS算法，用于查找到所有节点的距离。我不知道测试用例。我在在线评测系统上练习。 - vikkz

你可能想要一个队列，而不是一个PriorityQueue。更改起来应该很简单。 - Jim Mischel

Answer 1

根据文档，PriorityQueue是一个基于优先级堆的无界优先级队列。优先级队列的元素按自然顺序排列，或者根据提供给队列构造函数的比较器进行排序，具体取决于使用哪个构造函数。

LinkedList保留插入顺序，而PriorityQueue则不保留。因此，遍历顺序会改变，这使得使用PriorityQueue的实现不再是BFS。

- uoyilmaz

---

所以我尝试的方法是让我的可比较实现每次调用compareTo时返回0。这不是类似于维护插入顺序吗？ - Shilpa

Answer 2

优先队列（PriorityQueue）和链表（LinkedList）都实现了队列接口，执行的操作与队列（FIFO）相同。 优先队列和链表之间的区别在于，在插入时，优先队列会按照自然顺序进行排序和排序，但我们也可以添加比较器来定义记录的特定排序顺序，而链表只会被排序。 因此，在您尝试向优先队列中添加元素时，它们将根据其自然顺序或比较器函数进行排序。

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

public class QueueInJava {

public static void main(String[] args) {
    Queue<String> queue = new LinkedList<>(); 
    queue.add("Ishfaq");
    queue.add("Ramzan");
    queue.add("Nagoo");
    queue.add("Bangalore");
    
    System.out.println("Linked List Queue is:" + queue);
    System.out.println("Linked List Queue Peek is :" + queue.peek());
    
    queue.poll();
    System.out.println("Linked List Queue after remove is:" + queue);
    
    
    Queue<Integer> queuenew = new PriorityQueue<>();
    
    
    queuenew.add(2);
    queuenew.add(3);
    queuenew.add(1);
    queuenew.add(0);
    queuenew.add(4);
    
    System.out.println("Priority Queue is:" + queuenew);
    System.out.println("Priority Queue Peek is :" + queuenew.peek());
    
    int ieleFirst=queuenew.remove();
    System.out.println("Priority Queue Element Removed is:" + ieleFirst);
    int ieleSecond=queuenew.remove();
    System.out.println("Priority Queue Element Removed is:" + ieleSecond);
    System.out.println("Priority Queue after remove is:" + queuenew);
  }

}

输出：

Linked List Queue is: [Ishfaq, Ramzan, Nagoo, Bangalore]

Linked List Queue Peek is: Ishfaq

Linked List Queue after remove() is: [Ramzan, Nagoo, Bangalore]

Priority Queue is: [0, 1, 2, 3, 4]

Priority Queue Peek is: 0

Priority Queue Element Removed is: 0

Priority Queue Element Removed is: 1

Priority Queue after remove() is: [2, 3, 4]

- Ishfaq Ramzan

Answer 3

你的问题基本上是：为什么你认为两个任意的类，虽然最终是不同的类..却做着相同的事情？！

换句话说：今天的教训应该是：你不应该向他人寻求解释你的实验。更好的方法是：在编写代码时，确保你理解了每一个细节。

也就是说：当你开始使用Java库中的新类时，去阅读它的javadoc！如果你没有这样做，直接开始实验，并遇到了惊喜：那就查找资料吧。

当然，让别人向你解释这些很方便，但成为一名优秀的程序员的本质是有内在动力自己找出代码的含义（或将要做的事情）！

当然，你的问题的答案是：你的两个例子使用了不同类型的列表，它们具有不同的行为；正如它们对应的Javadoc中所指定的那样（this与that）。

- GhostCat

---

好的观点，但应该以评论的形式发表。不需要点赞或踩。 - darioo