Implement a priority queue using stack

Question

My idea is to add data into an ArrayList, sort it and then return the data to the Stack. It sounds circuitous but do you guys have better implementation?

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

You could use 2 stacks instead of a list and a stack for a very simple implementation.

1 Stack is just temporary. The other stack is the queue and the element you pop represents the next element in the queue.

Whenever you add an element you could pop the stack until you've found the correct place to push the new element. Every popped element goes onto the temporary stack. Once you've pushed the newly added element you start to pop from the temporary stack and push the elements back onto the real stack.

This approach works better for a priority queue than for a simple queue since the correct place to add the new item is not always the very end of the stack. There are probably far more efficient implementations though.

Answer 2

The classic way to implement a queue using only a stack object is the Two-Stack Queue.

Basically the idea is that if you have items in a stack and you pop them off one by one, they come out in reverse order (which is queue order). So, with two stacks, you have one stack that temporarily stores the incoming items, and when appropriate you pop them all off into the second stack which acts as the 'exit' to the queue. When you want to pop from the overall queue object, you pop from the second stack as that is where the items have been reversed.

Further reading:

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