How to implement a priority queue using two queues

Question

In a interview question I was asked to implement a priority queue using queues,

After the interview I googled it and found that it can be implemented using two queues, but I did not find how..

Please can anybody explain me.

Thanks in advance.

Answer 1

A basic solution

Use two queues

1. first one includes all the elements only

2. second one includes the respective priority of the element in the first queue.

   • Insertion : for every element insert the value in first queue, and its priority in second
                                                   Time Complexity O(1)

   • Get the top element : search the second queue for highest priority, the respective element in the first queue is the top element of the priority queue
                                                   Time Complexity O(n)