java - 优先级队列实现中比较对象的属性

Question

我尝试使用对象“队列项目”数组来实现优先级队列，其中包含一些数据(字符串)和一个作为优先级的整数。我试图使这些项目具有可比性，以便当我向队列添加新对象时，我可以迭代这些项目并将新项目添加到正确的位置，并将现在位于其后面的所有项目向后移动，但是当我添加队列中的新项目我收到空指针异常。我将包含所有代码，但 toString 方法只是从队列中复制而来，因此它不会按预期工作。

class QueueItem implements Comparable<QueueItem> {
    String data;
    int pri;

    public QueueItem(String data, int pri) {
        this.data = data;
        this.pri = pri;
    }

    @Override
    public int compareTo(QueueItem item) {
        return this.data.compareTo(item.data);
    }
}

public class PriorityQueue implements Queue<String> {
    private QueueItem[] arr;
    private int frontPos, backPos;

    public PriorityQueue() {
        arr = new QueueItem[20];
        backPos = -1;
        frontPos = 0;
    }

    public boolean isEmpty() {
        return frontPos == (backPos + 1) % arr.length;
    }

    public String front() {
        if (frontPos == (backPos + 1) % arr.length)
            throw new QueueException("Empty Queue - front");
        return arr[frontPos].data;
    }

    public int frontPri() {
        if (frontPos == (backPos + 1) % arr.length)
            throw new QueueException("Empty Queue - frontPri");
        return arr[frontPos].pri;
    }

    public void addToPQ(String str, int x) {
        if (arr.length==0) {
            arr[frontPos] = new QueueItem(str, x);
            frontPos++;
            return;
        }
        else {
            for (int i = 0; i < arr.length; i++) {
                arr[i].compareTo(new QueueItem(str, x));
            }
        }
    }

    public void deleteFront() {
        if (frontPos==(backPos+1)%arr.length) {
            throw new QueueException("Empty Queue - deleteFront");
        }
        frontPos = (frontPos+1)%arr.length;
    }

    public String toString() {
        if (frontPos == (backPos + 1) % arr.length) {
            return "<>";
        }
        StringBuffer sb = new StringBuffer();

        sb.append('<');

        int pos = frontPos;
        while (pos != backPos) {
            sb.append(arr[pos]);
            sb.append(',');
            pos = (pos + 1) % arr.length;
        }

        sb.append(arr[backPos]);
        sb.append('>');

        return (sb.toString());
    }
}

public interface Queue<String> {
    public void addToPQ(String str, int x);

    public void deleteFront();

    public String front();

    public boolean isEmpty();

    public int frontPri();
}

class QueueException extends RuntimeException {
    QueueException(String s) {
        super("Tried to apply " + s + " to empty queue");
    }
}

public class pqTest {
    public static void main(String[] args) {
        PriorityQueue pQ = new PriorityQueue();
        if (pQ.isEmpty()) {
            System.out.println("Queue is Empty - isEmpty");
        }
        pQ.addToPQ("Dog", 4);
        pQ.addToPQ("Cat", 20);
        pQ.deleteFront();
        pQ.addToPQ("Fish", 2);
    }
}

Answer 1

问题是 arr大小为 20，因此第一个元素甚至不会通过 addToPQ 中的 if 语句添加方法因为 arr.length != 0 。因此，它将转到 else 语句，该语句会迭代 arr 中的每个元素。 。但是arr有 20 个空元素，因为 QueueItems 数组中的每个点尚未初始化。因此，您应该将 if 语句中的条件更改为 frontPos == 0并将循环中的终止条件更改为 i < frontPos这样该方法就不会迭代 arr 中的 null 元素

public void addToPQ(String str, int x) {
        if (frontPos==0) {
            arr[frontPos] = new QueueItem(str, x);
            frontPos++;
            return;
        }
        else {
            QueueItem item = new QueueItem(str, x);
            for (int i = 0; i < frontPos; i++) {
                arr[i].compareTo(item);
            }
        }
    }