使用鏈接列表插入優先級隊列的方法

Question

首先，我覺得我應該提到這是一個任務。我不是在尋找一個直接的代碼答案，只是爲了指向正確的方向。我們被要求在一個鏈表中實現一個優先級隊列。

我在努力編寫insert（）函數的第一部分。在代碼中，我嘗試檢查head是否包含任何內容，如果沒有，則設置爲head至pqItem。它這樣做，但是當插入被再次調用第二次插入時，它不會識別head已經有PQueueItem，並且只是覆蓋head而不是忽略if (this.head == null)。我是不是正確設置head？

PQueue類

package ci284.ass1.pqueue; 

public class PQueue<T> { 

private PQueueItem<T> head; 
public static enum ORDER { 
    ASC, DESC; 
} 
public static ORDER DEFAULT_ORDER; 
private ORDER order; 

public PQueue() { 
    this.order = DEFAULT_ORDER; 
    head = null; 
} 

... 

public void insert(T data, int priority) { 
    PQueueItem<T> pqItem = new PQueueItem<T>(data, priority); 
    PQueueItem<T> temp; 
    PQueueItem<T> prev; 
    System.out.println("This is pqItem " + pqItem); 

    if (this.order == ORDER.DESC || this.order == DEFAULT_ORDER){ 
     if (this.head != null){ 
      System.out.println("Not null " + head); 
      if (priority <= head.getPriority()){ 

      } 
      else if (priority > head.getPriority()){ 
       prev = head; 
       System.out.println(prev); 
       head.setNext(head); 
       prev = pqItem; 
       System.out.println(prev); 
      } 
     } 
     if (this.head == null){ 
      System.out.println("Null " + head); 
      this.head = pqItem; 
      System.out.println("Null " + head); 
     } 
    } 
} 

PQueueItem類

package ci284.ass1.pqueue; 

public class PQueueItem<T> { 

private int priority; 
private T data; 
private PQueueItem<T> next; 

public PQueueItem(T data, int priority) { 
    this.data = data; 
    this.priority = priority; 
} 
public int getPriority() { 
    return priority; 
} 
public void setPriority(int priority) { 
    this.priority = priority; 
} 
public T getData() { 
    return data; 
} 
public void setData(T data) { 
    this.data = data; 
} 
public PQueueItem<T> getNext() { 
    return next; 
} 
public void setNext(PQueueItem<T> next) { 
    this.next = next; 
} 

public String toString() { 
    return String.format("[%s,%d]", data.toString(), priority); 
} 

} 

JUnit測試用於插入

@Test 
public void testInsertStart(){ 
    PQueue<String> pq = new PQueue<String>(); 
    pq.insert("1",2); 
    String head = pq.pop(); 
    assertEquals(head, "1"); 
    System.out.println("Worked"); 
    pq.insert("Hiya",3); 
    assertEquals(head, "Hiya"); 
} 

測試保留甕：

org.junit.ComparisonFailure: expected:<1> but was:<Hiya> 

和控制檯上寫着：

This is pqItem [1,2] 
Null null 
Null [1,2] 
Worked 
This is pqItem [Hiya,3] 
Null null 
Null [Hiya,3] 

Answer 1

下面是一些僞代碼。 （我已經通過創建一個隊列測試過）

public void insert(int priority, int data) { 
    Item item = new Item(priority, data); 

    if (head == null) { 
     head = item; 
     item.setNext(null); 
    } else { 
     Item next = head; 
     Item prev = next; 

     do { 
      if (priority > next.getPriority()) { 
       // break and insert 
       break; 
      } 
      prev = next; 
      next = next.getNext(); 
     } while (next != null); 

     item.setNext(next); 
     if (item.getPriority() > head.getPriority()) { 
      head = item; 
     } else prev.setNext(item); 
    } 
} 

你已經在你的插入方法存在以下問題：

prev = head; 
head.setNext(head); 
prev = pqItem; 

是什麼一段代碼甚至做？這裏是做什麼的：

您還沒有考慮，你必須在隊列中兩個以上項目的情況。想象一下，你有5個項目在隊列中。現在你想在隊列中插入pqItem。 pqItem的優先級最低，因此它會插入隊列的末尾，對吧？因此，您需要遍歷隊列（列表）以便到達最後一個項目。