在 Java 中使用链表实现优先级队列

问题描述 投票:0回答:0

实现一个不可变的优先队列(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());
  }
}

尝试为优先队列做两类技术,以使代码更清晰。

java priority-queue
最新问题
© www.soinside.com 2019 - 2025. All rights reserved.