Java 扩展优先级队列可比？

Question

我正在做一项 class 作业，我不太明白如何按照作业要求的方式使用比较器。

作业如下：

"完成优先队列class

您的优先级队列必须使用匿名函数来决定优先级
必须将Function接口作为构造函数的参数
您应该仍然有默认构造函数——如果没有提供函数，请使用 class

这是我正在研究的 class...

public class PriorityQueue <Item extends Comparable<Item>> {

    public PriorityQueue()
    {

    }
    public PriorityQueue(Comparator<Item> compare )
    {

    }  

    private int size = 0;
    private Node<Item> head = null;
    private Comparator<Item> compare ;

    private static class Node<Item>
    {
       private Item data;
       private Node<Item> next;


    public Node(Item data, Node<Item> next)
       {
          this.data = data;
          this.next = next;
       }       
       public Node(Item data)
       {
          this.data = data;
          this.next = null;
       }       
       public Node()
       {
          this.data = null;
          this.next = null;
       }
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public Item dequeue() {
        // TODO Auto-generated method stub
        return null;
    }

    @Override
    public void enqueue(Item item) {
        Node<Item> curr = head;
        Node<Item> prev = curr;

        if (isEmpty())
        {
            head = new Node<Item>(item,null);
        }
        else
        {
            while (curr != null)
            {
                prev = curr;
                curr = curr.next;
            }

            prev.next = new Node<Item>(item, curr);
        }
        size++;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public void printQueue() {
        Node<Item> curr = head;

        while (curr != null)
        {
            System.out.println(curr.data);
            curr = curr.next;
        }

    }
}

这是队列将包含的进程class...

public class Process implements Comparable<Process> {

    private ProcessPriorty priority;
        private String name;

    public Process(ProcessPriorty priority, String name) {
        super();
        this.priority = priority;
        this.name = name;
    }

    public void setPriority(ProcessPriorty priority) {
        this.priority = priority;
    }

    @Override
    public String toString() {
        return name + "... Priority = " + priority + ".";
    }

    public String getName() {
        return name;
    }

    public ProcessPriorty getPriority() {
        return priority;
    }

    @Override
    public int compareTo(Process other) {

        if(other == null)
        {
            return  1;
        }
        return this.priority.compareTo(other.priority) ;
    }
}

我理解队列的概念，甚至将入队方法编码为一个简单的队列，在项目进入时将其插入。我遇到的问题是比较该方法中的节点以对按插入时的优先级列出。我认为这与作业的这三个方向有关。那么，我应该如何处理构造函数、Comparator 变量，以及如何使其默认为 compareTo？

Answer 1

既然您有对队列头部的引用，那么从那里开始就很简单了。您有 2 个案例 -

compare != null
compare == null
- 第一种情况，您对Comparator::compareTo感兴趣。从优先队列的定义来看，只需要从头开始遍历队列，只要enqueue(Item item)中的item大于当前的element就遍历，您在 element 之前插入 item。您将使用 compare.compareTo(item, element) 来确定它们的顺序。
- 第二种情况你只要用item.compareTo(element)做上面的比较，遍历和插入是一样的

Java 扩展优先级队列可比？

Java priority queue that extends comparable?

java

linked-list

priority-queue

comparable

enqueue