приоритетная очередь 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; 
       } 
      } 
     } 

Кроме того, когда я использовал смежность List вместо матрицы смежности, реализация очереди Приоритета дала правильный анс.

Answer 1

Как documentation говорит:

Неограниченная приоритетная очередь на основе приоритета кучи. Элементы очереди приоритетов упорядочены в соответствии с их естественным порядком или Компаратором, предусмотренным во время построения очереди, в зависимости от , который используется конструктором.

LinkedList сохраняет порядок вставки, PriorityQueue этого не делает. Таким образом, ваш порядок итераций изменяется, что делает вашу реализацию, которая использует PriorityQueue, отличную от BFS.

Answer 2

Ваша проблема в основном: почему вы считаете, что два произвольных класса, которые хорошо, есть, в конце концов, разные классы .. сделать то же самое ?!

Другими словами: ваш урок сегодня должен быть: вы не должны обращаться к другим людям, чтобы объяснить свои эксперименты. Лучший подход: в этот момент, когда вы напишите ваш код, вы должны убедиться, что вы понимаете каждый деталь вашего кода.

Смысл: когда вы начинаете использовать новый класс из библиотек Java, go и прочитайте его javadoc! И когда вы этого не делаете, но вы начинаете свои эксперименты; и вы сталкиваетесь с сюрпризами: посмотрите на вещи.

Конечно, это удобно, чтобы другие люди объясняют, что для вас, но суть быть хорошим программистом является внутренней мотивации, чтобы узнать себя, что ваш код (или будет) делать!

И, конечно же, ответ на ваш вопрос: ваши два примера использовать различного рода списки, которые имеют различные поведения; как указано в их соответствующем Javadoc (this против that).

Answer 3

PriortiyQueue, а также Linkedlist реализуют интерфейс Queue Interface и выполняют те же операции, что и Queue Operated (FIFO). Разница между PriorityQueue и Linkedlist во время установки PriorityQueue будет сортироваться, а также упорядочена в соответствии с естественным ордером, но мы также можем добавить Commparator, чтобы определить конкретный порядок сортировки для записи, тогда как LinkedList будет быть просто заказанным. Итак, пока вы пытаетесь добавить элементы в PriorityQueue, они будут отсортированы по их естественному порядку или по функции компаратора.

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<String>(); 
    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<Integer>(); 


    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]