实现一个不可变的优先队列(PQ)。优先级是整数,值是字符串。我正在使用创建 emptyNode 类和 elementNode 类以及 ListPriorityQueue 类进行包装的技术。我想我在 ElementNode 类中遇到了 pop 和 peek 的问题,但无法找出哪一部分是错误的。此外,在包装类(ListPriorityQueue 类)中,我还需要获取一个私有变量,如 head 来创建对吗?
public interface PriorityQueue {
/**
* Checks if the priority queue is empty
* @return true if the PQ is empty, false otherwise.
*/
Boolean isEmpty();
/**
* Adds an element to the PQ.
* @param priority The element's (non-negative) priority.
* @param value The element's value.
* @return A copy of the priority queue containing the new element.
*/
PriorityQueue add(Integer priority, String value) throws IllegalArgumentException;
/**
* Gets the value of the highest priority element. If there are multiple elements that have the same priority, gets
* the value of the earliest added element.
* @return The value of the highest priority element.
* @throws EmptyPriorityQueueException if the PQ is empty.
*/
String peek() throws EmptyPriorityQueueException;
/**
* Removes the highest priority element.
* @return A copy of the priority queue without the highest priority element.
* @throws EmptyPriorityQueueException if the PQ is empty.
*/
PriorityQueue pop() throws EmptyPriorityQueueException;
}
public class EmptyPriorityQueueException extends Exception {
public EmptyPriorityQueueException() {
super("The queue is empty");
}
public EmptyPriorityQueueException(String mes) { // provide custom message of exception.
super(mes);
}
}
public class EmptyNode implements PriorityQueue {
@Override
public Boolean isEmpty() {
return true;
}
@Override
public PriorityQueue add(Integer priority, String value) throws IllegalArgumentException {
if (priority < 1 || priority > 10) {
throw new IllegalArgumentException("Priority should be in the range of 1-10.");
}
return new ElementNode(priority, value, this);
}
@Override
public String peek() throws EmptyPriorityQueueException {
throw new EmptyPriorityQueueException("Cannot peak an empty PQ");
}
@Override
public PriorityQueue pop() throws EmptyPriorityQueueException {
throw new EmptyPriorityQueueException("Cannot pop an empty PQ");
}
}
public class ElementNode implements PriorityQueue {
private final Integer priority;
private final String value;
private final PriorityQueue next;
public ElementNode(Integer priority, String value, PriorityQueue next) {
if (priority == null) throw new IllegalArgumentException("Data cannot be null");
if (value == null) throw new IllegalArgumentException("Value cannot be null");
this.priority = priority;
this.value = value;
this.next = next;
}
@Override
public Boolean isEmpty() {
return false;
}
@Override
public PriorityQueue add(Integer priority, String value) throws IllegalArgumentException {
if (priority < 1 || priority > 10) {
throw new IllegalArgumentException("Priority should be in the range of 1-10.");
}
if (priority > this.priority) {
return new ElementNode(priority, value, this);
} else if (priority < this.priority) {
return new ElementNode(this.priority, this.value, this.next.add(priority, value));
} else {
return new ElementNode(this.priority, this.value, new ElementNode(priority, value,
this.next));
}
}
@Override
public String peek() throws EmptyPriorityQueueException {
if (this.next.isEmpty()) {
return this.value;
} else {
Integer nextP = ((ElementNode) next).priority;
if (this.priority >= nextP) {
return this.value;
} else {
return this.next.peek();
}
}
}
@Override
public PriorityQueue pop() throws EmptyPriorityQueueException {
if (this.next.isEmpty()) {
return new EmptyNode();
} else {
String nextV = this.next.peek();
if (this.priority >= ((ElementNode) this.next).priority) {
return new ElementNode(this.priority, this.value, this.next.pop());
} else {
return new ElementNode(((ElementNode) this.next).priority, nextV, this.next.pop().pop());
}
}
}
}
public class ListPriorityQueue implements PriorityQueue {
private final PriorityQueue node;
private ListPriorityQueue(PriorityQueue node) {
this.node = node;
}
public static ListPriorityQueue createEmpty() {
return new ListPriorityQueue(new EmptyNode());
}
@Override
public Boolean isEmpty() {
return node.isEmpty();
}
@Override
public PriorityQueue add(Integer priority, String value) throws IllegalArgumentException {
return new ListPriorityQueue(node.add(priority, value));
}
@Override
public String peek() throws EmptyPriorityQueueException {
return node.peek();
}
@Override
public PriorityQueue pop() throws EmptyPriorityQueueException {
return new ListPriorityQueue(node.pop());
}
}
尝试为优先队列做两类技术,以使代码更清晰。