使用链接列表插入优先级队列的方法

首先我觉得我应该提到这是一项任务。 我不是在寻找一个直接的代码答案，只是为了指出我正确的方向。 我们被要求在链表中实现优先级队列。

我正在努力编写insert（）函数的第一部分。 在代码中，我尝试检查head包含任何内容，如果不是，则将head设置为pqItem 。 它执行此操作，但是当再次为第二个插入调用insert时，它不会识别出head已经有PQueueItem并且只是覆盖head而不是忽略if (this.head == null) 。 我没有正确安排head吗？

PQueue类

 package ci284.ass1.pqueue; public class PQueue { private PQueueItem 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 pqItem = new PQueueItem(data, priority); PQueueItem temp; PQueueItem 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()){ 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 { private int priority; private T data; private PQueueItem 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 getNext() { return next; } public void setNext(PQueueItem next) { this.next = next; } public String toString() { return String.format("[%s,%d]", data.toString(), priority); } } 

插入JUnit测试

 @Test public void testInsertStart(){ PQueue pq = new PQueue(); 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: but was: 

并且控制台显示：

 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具有最低优先级，因此它将插入队列的末尾，对吧？ 因此，您需要遍历队列（列表）才能到达最后一个项目。