使用链接列表插入优先级队列的方法 [英] insert method for Priority Queue using Linked Lists

问题描述

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

Firstly I feel I should mention this is for an assignment. I'm not looking for a direct code answer just to point me in the right direction. We have been asked to implement a Priority Queue in a linked list.

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

I am struggling to write the first part of the insert() function. In the code I try to check if the head contains anything, if not it set's the head to pqItem. It does this, but when insert is called again for a second insert it doesn't recognise that head already has a PQueueItem in it and just overrides head instead of ignoring if (this.head == null). Am I not settting head correctly?

PQueue Class

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 Class

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]

推荐答案

这是一些伪代码代码。 （我已通过创建队列对其进行了测试）

Here is some pseudocode code. (I have tested it by creating a queue)

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

您的插入方法存在以下问题：

You had the following problems in your insert method:

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

这段代码甚至做了什么？以下是它的作用：

What does this piece of code even do? Here is what it does:

< img src =https://i.stack.imgur.com/On5j2.jpgalt =bad code>

你也没有考虑队列中有两个以上项目的情况。想象一下，队列中有5个项目。现在你想在队列中插入 pqItem 。 pqItem 具有最低优先级，因此它将插入队列末尾，对吧？因此，您需要遍历队列（列表）才能到达最后一个项目。

You also did not consider the case in which you have more than two items in the queue. Imagine you have 5 items in the queue. And now you want to insert pqItem in the queue. pqItem has the least priority so it will get inserted at the end of the queue, right? Therefore, you need to traverse the queue (list) in order to get to the last item.

这篇关于使用链接列表插入优先级队列的方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！