使用堆栈实现优先级队列

Question

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

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栈只是暂时的。另一个堆栈是队列，弹出的元素表示队列中的下一个元素。

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

由于添加新项目的正确位置并不总是堆栈的最终位置，所以此方法对于优先级队列比对于简单队列更好。尽管如此，可能有更高效的实现。

Answer 2

仅使用栈对象实现队列的经典方法是双栈队列。

基本上这个想法是，如果你有一个堆栈中的项目，并且你逐个弹出它们，它们将以相反的顺序（这是队列顺序）出来。因此，对于两个堆栈，您有一个临时存储传入项目的堆栈，并在适当时将它们全部弹出到第二个堆栈中，该堆栈充当队列的“出口”。当您想要从整个队列对象中弹出时，您会从第二个堆栈中弹出，因为这是项目已被反转的地方。

延伸阅读：

1. Explanation on stackoverflow
2. Written tutorial
3. Video tutorial