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.

Solution 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)

Solution 2

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->

Solution 3

There are of course several options. The first one I can think of uses only 1 queue, but assumes you do know the size of the queue.

Complexities are not very well, insertion would be linear, popping is constant.

Below is the pseudo python 3 code.

class PriorityQueue(Queue):

    def insert(self, item):
        for i in range(self.size):
            next = self.pop()
            if next < item:
                self.enqueue(next)
            else:
                self.enqueue(item)
                self.enqueue(next)
                break
        for i in range(i, self.size):
            self.enqueue(self.pop())

    def pop(self):
        return self.pop()

I've used the name 'self.pop' for taking the first item from the original queue. The 'self.enqueue' puts an item on the end of the original queue.

How it works: The insertion takes all the smaller items from the queue, and puts them at the end. When the new item is the smallest, put that one at the end. After that, just put the remainder of the items at the end.

Note that I did not put the details in my code, like the case wherein the queue is empty, possibly full, ... This code will not work, but it should convey the idea.

A working solution in python 3:

from queue import Queue

class PriorityQueue(Queue):

    def insert(self, item):
        if self.empty():
            self.put(item)
            return
        i = 0
        size = self.qsize()
        n = self.get()
        while item > n and i < size:
            self.put(n)
            n = self.get()
            i += 1
        if i == size:
            self.put(item)
            self.put(n)
            for i in range(size): self.put(self.get())
        else:
            self.put(item)
            self.put(n)
            for j in range(i + 1, size): self.put(self.get())

Comments

[Nagendra Yadav]

any solution using two queues??

[Noctua]

Can't think of any faster than linear implementation using 2 queues.

[VINOTH ENERGETIC]

why can't I use the single queue and insert both value and priority as structure in queue. So that I can fetch data using single queue instead of two queue

[Bogdan Gavril MSFT]

This not only takes O(n) time to get the top element, it also uses an extra O(n) space.

[Mika Feiler]

Queue means FIFO. This here is both a stack and a queue, both FIFO and FILO, with both *First and *Last methods.

[Ankur S]

There is no point to this solution. Why is it accepted??