java - 使用栈实现优先级队列

Question

我的想法是将数据添加到ArrayList中，对其进行排序，然后将数据返回到Stack。听起来很迂回，但是你们有更好的实现吗？

class MyPriorityQueue {
  private Stack<Integer> st;
  private ArrayList<Integer> list;

  public MyPriorityQueue() { // The constructor
    st = new Stack<Integer>();
    list = new ArrayList<Integer>();
  }

  public void add(int e) { // To add one more item
    list.add(e);

  }

  public int poll() { // To remove one item
    if(!list.isEmpty())
      sortListAndTransferToStack();
    System.out.println("st.peek(): " + st.peek());
    return st.pop();

  }

  private void sortListAndTransferToStack() {
    Collections.sort(list, Collections.reverseOrder());
    st.clear();
    for(int i=0; i<list.size(); i++) {
      st.push(list.get(i));
    }
    list.clear();
  }

  public boolean isEmpty() { // To check whether the priority queue is empty.  Don't modify this method
    return st.isEmpty();
  }
}

Answer 1

您可以使用 2 个堆栈来代替列表和堆栈来实现非常简单的实现。

1 堆栈只是暂时的。另一个堆栈是队列，您弹出的元素代表队列中的下一个元素。

每当添加一个元素时，您都可以弹出堆栈，直到找到推送新元素的正确位置。每个弹出的元素都会进入临时堆栈。一旦你推送了新添加的元素，你就开始从临时堆栈中弹出并将元素推回真实堆栈。

此方法对于优先级队列比对于简单队列更有效，因为添加新项目的正确位置并不总是堆栈的最末尾。不过，可能还有更有效的实现。