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

The main advantage of using a priority queue is that we can get min/max at a constant time. So it is the first criteria that should be met. We are considering key values only. We can create a prioity queue using two Queues name them q1 and q2 if the input element is larger than top of q1 then append it to q1 else

if the input is smaller than top of q1 then repeat

remove element from q1 and insert to q2 till top is greater than that element

now add the element

now insert the remaining elements to the q2

so like input is 2 4 1 5 3
pass 1)
q1-> 2 
q2->  
pass 2)
q1-> 2 4
q2->
pass 3)
q1-> 
q2->1 2 4 // since 1 is less than top of q1 add it to q2 and then pop all the elements to q2
pass 4)
q1-> 
q2-> 1 2 4 5 //add it to q2 since it is larger than all the elements
pass 5)
q1-> 1 2 3 4 5//pop the elements smaller than q3 and then add the element and append the        remaining

q2->

Answer 2

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)