通用优先级队列java实现

dphi5xsq 于 2023-02-07 发布在 Java

关注(0)|答案(1)|浏览(164)

我需要在JAVA中实现一个泛型优先级队列。注意键和值都是泛型的。所有的数据结构必须是用户实现的。严格禁止使用Java集合或任何其他数据结构库。我使用了数组来存储队列中的数据。但显然泛型数组声明是不可能的。我不能使用数组列表，因为那样我就必须导入库。并且代码必须在一个文件中。该类必须实现一个接口。接口：

public interface PQK<P extends Comparable<P>, T> {

    // Return the length of the queue
    int length();

    // Enqueue a new element. The queue keeps the k elements with the highest priority. In case of a tie apply FIFO.
    void enqueue(P pr, T e);

    // Serve the element with the highest priority. In case of a tie apply FIFO.
    Pair<P, T> serve();
}

类I为实现给定接口的优先级队列编写：

public class PQKImp<P extends Comparable<P>, T> implements PQK<P, T> {

    private int size;
    private int capacity;
    private Pair<P , T>[] heap;

    public PQKImp(int k) {
        heap = new Pair<P,T>[k];
        this.capacity = k;
        this.size = 0;
    }

    public int length(){
        return size;
    }

    public void enqueue(P pr, T e){
        Pair<P ,T> pair = new Pair<P,T>(pr , e);
        heap[++size] = pair;
        int pos = size;
        while(pos!=1 && pair.first.compareTo(heap[pos/2].first)<0){
            heap[pos] = heap[pos/2];
            pos /= 2;
        }
        heap[pos] = pair;
    }

    public Pair<P,T> serve(){
        return heap[0];
    }
}

这是我得到的错误：

.\PQKImp.java:8: error: generic array creation
                heap = new Pair<P,T>[k];
                       ^
1 error

你能给我一个在类中存储数据的方法吗？谢谢

Java

来源：https://stackoverflow.com/questions/59235229/generic-priority-queue-java-implementation

1条答案

按热度按时间

u3r8eeie1#

class Employee implements Comparable<Employee>{
    String name;
    int rollNumber;

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getRollNumber() {
        return rollNumber;
    }

    public void setRollNumber(int rollNumber) {
        this.rollNumber = rollNumber;
    }

    @Override
    public String toString() {
        return "Employee [name=" + name + ", rollNumber=" + rollNumber + "]";
    }

    public Employee(String name, int rollNumber) {
        super();
        this.name = name;
        this.rollNumber = rollNumber;
    }

    @Override
    public int compareTo(Employee o) {
        return rollNumber - o.getRollNumber();
    }

}

public class PriorityQueueImplementation {
    public static void main(String[] args) {
        PriorityQueue<Employee> employees = new PriorityQueue<>();

        Employee e1 = new Employee("A", 1);
        Employee e2 = new Employee("B", 3);
        Employee e3 = new Employee("C", 2);
        Employee e4 = new Employee("D", 5);
        Employee e5 = new Employee("E", 6);
        Employee e6 = new Employee("F", 8);
        Employee e7 = new Employee("G", 10);
        Employee e8 = new Employee("H", 4);
        Employee e9 = new Employee("I", 7);
        Employee e10 = new Employee("J", 9);

        employees.add(e1);
        employees.add(e2);
        employees.add(e3);
        employees.add(e4);
        employees.add(e5);
        employees.add(e6);
        employees.add(e7);
        employees.add(e8);
        employees.add(e9);
        employees.add(e10);
        
        for (Employee employee : employees) {
            System.out.println(employee);
        }
        
        System.out.println();
        System.out.println("Print By Priority Queue");
        while(!employees.isEmpty()) {
            System.out.println(employees.remove());
        }

    }
}

赞(0）回复(0）举报 2023-02-07

我来回答

通用优先级队列java实现

1条答案

相关问题

热门标签

最新问答