将优先级队列实现为堆栈 Java

Question

我已经实现了我的程序，但出现异常 java.lang.ClassCastException

这是代码：

import java.util.NoSuchElementException;

public class BasePQStack<Item> implements Stack<Item> {

// TODO: implement this object.
private int N = 0;
private MaxPQ<Compare> pq = new MaxPQ<>();
private int count;

public BasePQStack() {
    count = 0;

}

/**
 * entry point for sample output..
 * 
 * @param args
 */
public static void main(String[] args) {
    Stack<Integer> S = new BasePQStack<Integer>();

    S.push(new Integer(2));
    S.push(new Integer(7));
    Integer W = S.pop();
    S.push(new Integer(8));
    S.push(new Integer(5));
    ;
    Integer X = S.pop();
    Integer Y = S.peek();
    S.push(new Integer(3));
    Integer Z = S.pop();

    System.out.println("Testing: ");
    System.out.println(W);
    System.out.println(X);
    System.out.println(Y);
    System.out.println(Z);
}

@Override
public Item push(Item item) {
    Compare x = new Compare(item, count);
    pq.insert(x);
    count++;
    N++;

    return item;
}

@Override
public Item pop() {
    if (isEmpty())
        throw new NoSuchElementException("no such element");

    else {
        Item var = (Item) pq.delMax();
        N--;
        return var;
    }
}

@Override
public Item peek() {
    if (isEmpty())
        throw new NoSuchElementException("no such element");

    else {
        Item var = (Item) pq.delMax();
        push(var);
        return var;
    }

}

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

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

public class Compare implements Comparable<Compare> {
    private Item value;
    private int a;

    public Compare(Item value, int a) {
        this.a = a;
        this.value = value;
    }

    @Override
    public int compareTo(Compare x) {
        if (this.a > x.a)
            return 1;
        if (this.a < x.a)
            return -1;
        else
            return 0;
    }

    public int getA() {
        return this.a;
    }

    public Item getValue() {
        return this.value;
    }

    @Override
    public String toString() {
        return "item {" + "value = " + value + ",a = " + a + '}';
    }
}

}

我从控制台收到的消息是 BasePQStack$Compare cannot be cast to java.lang.Integer。我试过很多转换，但无法弄清楚任何事情，因为它只会导致更多错误

代码的输出应该是：

7

5

8

3

Answer 1

来自 Java documentation：Class 转换异常是 "thrown to indicate that the code has attempted to cast an object to a subclass of which it is not an instance"。

从您发布的代码来看，当您尝试将某些内容投射到项目时，它似乎会发生：

Item var = (Item) pq.delMax();

可能是因为您的队列不包含 Item 类型的对象，它包含 Compare 类型的对象。通常，当您决定向下转换时要小心，因为编译器错误会帮助您。

Answer 2

您的 MaxPQ 密钥属于比较类型，当您推送一个整数时，它会在插入到 MaxPQ 之前被包装在一个比较中。

问题是当您弹出或查看时，您没有对 Compare 进行任何解包以返回整数。这就是为什么在任何调用 pop() 或 peek() 的行上都会出现 ClassCastException 的原因。您将比较视为整数。

您需要修改您的 pop() 和 peek() 方法，如下所示；

    @Override
    public Item pop() {
            if (isEmpty()) {
                    throw new NoSuchElementException("no such element");
            } else {
                    Item var = (Item) pq.delMax().getValue();
                    N--;
                    return var;
            }
    }

    @Override
    public Item peek() {
            if (isEmpty()) {
                    throw new NoSuchElementException("no such element");
            } else {
                    Item var = (Item) pq.delMax().getValue();
                    push(var);
                    return var;
            }
    }

注意 getValue() 的用法。这就是我上面提到的解包的作用，即它为您从比较中获取整数。

Answer 3

你或许应该替换这一行

Item var = (Item) pq.delMax()

有

Item var = (Item) pq.delMax().getValue();

因为delMax() returns一个比较对象，你需要一个Item对象。

将优先级队列实现为堆栈 Java

Implementing a Priority Queue as a Stack Java

java

queue

implementation

stack

priority-queue