使用堆栈实现优先级队列

debugcn 发表于 Dev

乌兹别拉

我的想法是将数据添加到ArrayList中，对其进行排序，然后将数据返回到堆栈中。听起来circuit回曲折，但你们有更好的实施方法吗？

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();
  }
}

扎普尔

您可以使用2个堆栈而不是列表和一个堆栈来实现一个非常简单的实现。

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

每当添加元素时，都可以弹出堆栈，直到找到正确的位置来推送新元素为止。每个弹出的元素都进入临时堆栈。推送新添加的元素后，您便开始从临时堆栈中弹出，然后将这些元素推送回真实堆栈中。

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

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。