嘗試實施有序鏈接列表的優先級隊列

所以我想要做的是使用有序鏈接列表實現優先級隊列。我覺得我相當接近，但我似乎無法解決插入函數中的while語句中的錯誤。這是我到目前爲止：嘗試實施有序鏈接列表的優先級隊列

class OrderedLinkedListMaxPQ<Item> { 

private class PQNode { 
    Object data; 
    PQNode next; 

    public PQNode(Object value) { 
     data = value; 
     next = null; 
    } 
} 

PQNode head; 

public void PriorityQueue() { 
    this.head = null; 
} 

public boolean isEmpty() { return this.head == null; } 

public void insert(Object item) { 

    PQNode prev = null; 
    PQNode current = this.head; 
    while (current != null && current.data >= item.data) { 
     prev = current; 
     current = current.next; 
    } 

    PQNode temp = new PQNode(item); 
    if (prev == null) { 
     temp.next = this.head; 
     this.head = temp; 
    } else { 
     temp.next = current; 
     prev.next = temp; 
    } 
} 

public Object delete() { 
    Object temp = this.head.data; 
    this.head = this.head.next; 
    return temp; 
} 

public static void main(String[] args) { 
    OrderedLinkedListMaxPQ<Integer> pq = new OrderedLinkedListMaxPQ<Integer>(); 
    pq.insert(7); 
    pq.insert(6); 
    pq.insert(3); 
    pq.insert(2); 
    while (!pq.isEmpty()) 
     StdOut.println(pq.delete()); 
    } 
}

來源

2013-10-30 user2901181

第一次插入（），你不會得到一個空指針？ – iluxa

@iluxa如果你的意思是因爲一段時間的條件，它應該短路，而不是擊中current.data。 –

「使用有序鏈接列表實現優先隊列」。爲什麼？ java.util.PriorityQueue有問題嗎？它是* O（log（N））*你的是* O（N）*不要這樣做。 – EJP

current.data >= item.data是沒有意義的。 data是一個對象引用，你不能比較它們。也許，如果dat avalues是Comparable，那麼可以使用compareTo(...)方法。否則，你將需要編寫自己的機制來比較它們。此外，item作爲對象傳入，但您將其引用爲PNode ...這也是一個問題。

來源

2013-10-30 00:40:20 rolfl

感謝您的幫助。我將如何去實施compareTo到這個類中？我應該做一個單獨的幫助器方法來比較這兩個值嗎？對不起，我只是有點失落。 – user2901181

嘗試實施有序鏈接列表的優先級隊列

回答

相關問題