How to implement a priority queue using two queues

Question

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

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

Please explain to someone.

Thanks in advance.

Answer 1

Basic solution

Use two queues

• first includes all elements only

• the second includes the corresponding priority of the element in the first order.

  • Insert : for each element, the value is inserted first and its priority in the second)

  • Get top item : search for the second priority queue for the highest priority, the corresponding element in the first priority is the top element of the priority queue
    "n" and "nbsp;)

Answer 2

The main advantage of using the priority queue is that we can get min / max in constant time. Thus, this is the first criterion to be met. We consider only key values. We can create a prioity queue using two queues, their names q1 and q2; if the input element is greater than the vertex q1, then add it to q1 else

if the input is less than the vertex q1, then repeat

remove an element from q1 and insert in q2 to the top more than this element

now add item

now insert the remaining elements in 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 3

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

The difficulties are not very good, the insert will be linear, popping is constant.

Below is the python 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 used the name self.pop for the first item from the original queue. "Self.enqueue" puts the item at the end of the original queue.

How it works: The insert takes all the smaller elements from the queue and puts them at the end. When the newest item is the smallest, put it at the end. After that, just put the remaining items at the end.

Please note that I did not put the details in my code, for example, the case when the queue is empty, possibly complete ... This code will not work, but it should convey the idea.

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

Answer 4

This is some kind of question that I came across. Implementing maxQueue using two queues

Time discharge complexity - O (1) Run-time complexity - O (n)

Java code

public class _01_MaximumQueue {

 /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub } public class QueueWithMax<T extends Comparable<T>> { Queue<T> enteries = new ArrayDeque<T>(); Deque<T> candidatesForMax = new ArrayDeque<T>(); public void enqueue(T x) { enteries.add(x); if (candidatesForMax.peekLast().compareTo(x) < 0) { candidatesForMax.removeLast(); } candidatesForMax.addLast(x); } public T dequeue() { if (!enteries.isEmpty()) { T result = enteries.remove(); if (candidatesForMax.peekFirst().equals(result)) { candidatesForMax.removeFirst(); } return result; } throw new IllegalStateException("called Degueue() on empty Queue"); } public T max() { if (!candidatesForMax.isEmpty()) { return candidatesForMax.peekFirst(); } throw new NoSuchElementException("No element"); } } 

}