リンクされたリストを使用するプライオリティキューの挿入方法

Question

最初に、これは割り当てのために言及する必要があると感じる。私はちょうど正しい方向に私を指すために直接コードの答えを探しているわけではありません。リンクリストに優先度キューを実装するように求められました。

私はinsert（）関数の最初の部分を書くのに苦労しています。コードでは、headに何かが含まれているかどうかを確認します。そうでない場合は、headからpqItemに設定されています。これは行いますが、2番目の挿入のためにinsertが再度呼び出された場合、headはすでにPQueueItemを持っていると認識せず、if (this.head == null)を無視する代わりにheadをオーバーライドします。 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"); 
} 

試験RET壷：

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); 
    } 
} 

あなたのinsertメソッドで、次のような問題いた ：

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

コードのこの作品でも何をしますか？ここではそれが何をするかです：

また、あなたがキュー内に二つ以上のアイテムを持っている場合を考慮していませんでした。キューに5つのアイテムがあるとします。そして、pqItemをキューに挿入します。 pqItemは優先度が最も低いので、キューの最後に挿入されます。したがって、最後の項目に到達するには、キュー（リスト）をトラバースする必要があります。