Turning a Queue into a Priority Queue
Given a queue. The task is to change a queue in a priority queue.
Example :
Input : Q = [ 3, 4, 2, 8, 1, 7 ]
Output : Q =[ 8, 7, 4, 3, 2, 1 ]
Approach :
The idea is to sort the queue elements either in ascending / descending order. We know that queue can be sorted using recursion that takes extra space due to function call stack.
After sorting the queue either in ascending or descending order we can change a queue into a priority queue. whenever we push any value inside the queue, just after that we have to sort the queue then all elements will be arranged according to their priority.
- Create a queue q and push random elements in it.
- Create sortqueue function to sort the array.
- If the queue is empty then return back.
- Initialize a variable item and store the topmost element of the queue in it and pop it out from the queue.
- Again, make a recursive call inside sortqueue function.
- Now, again insert elements in the queue by checking if q is empty or not.
- If the queue is empty then push the front value inside the queue.
- Check if the current element is greater than the element at the front.
- If yes, then push the value inside the queue and make a recursive call for inserting the front element of the queue to the last.
- If q is not empty then return back.
- Pop the front element and push in the last of the queue.
- Make recursive calls for further elements.
- Otherwise, push the front element into the last of the queue and make a recursive call for pushing elements inside the queue.
- If yes, then push the value inside the queue and make a recursive call for inserting the front element of the queue to the last.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function to push element in last // by popping from front until size becomes 0 void frontelement(queue< int >& q, int qsize) { // Base condition if (qsize <= 0) return ; // Pop front element and push // this last in a queue q.push(q.front()); q.pop(); // Recursive call for pushing element frontelement(q, qsize - 1); } // Function for inserting element in the queue void insertelement(queue< int >& q, int val, int qsize) { if (qsize == 0 || q.empty()) { q.push(val); return ; } // If current element is greater than // the element at the front else if (val >= q.front()) { // Call stack with front of queue q.push(val); // Recursive call for inserting // a front element of the queue // to the last frontelement(q, qsize); } else { // Push front element into last in a queue q.push(q.front()); q.pop(); // Recursive call for pushing elements in a queue insertelement(q, val, qsize - 1); } } // Function to sort queue void sortqueue(queue< int >& q) { if (q.empty()) { return ; } int item = q.front(); q.pop(); sortqueue(q); insertelement(q, item, q.size()); } // Driver Code int main() { queue< int > q; q.push(3); q.push(4); q.push(2); q.push(8); q.push(1); q.push(7); // Initially queue is 3 4 2 8 1 7 sortqueue(q); while (!q.empty()) { cout << q.front() << " " ; q.pop(); } return 0; } |
Java
// Java code to implement the approach import java.io.*; import java.util.*; class GFG { // Function to push element in last // by popping from front until size becomes 0 static void frontelement(Queue<Integer> q, int qsize) { // Base condition if (qsize <= 0 ) { return ; } // Pop front element and push // this last in a queue q.add(q.peek()); q.poll(); // Recursive call for pushing element frontelement(q, qsize - 1 ); } // Function for inserting element in the queue static void insertelement(Queue<Integer> q, int val, int qsize) { if (qsize == 0 || q.isEmpty()) { q.add(val); return ; } // If current element is greater than // the element at the front else if (val >= q.peek()) { // Call stack with front of queue q.add(val); // Recursive call for inserting // a front element of the queue // to the last frontelement(q, qsize); } else { // Push front element into last in a queue q.add(q.peek()); q.poll(); // Recursive call for pushing elements in a // queue insertelement(q, val, qsize - 1 ); } } // Function to sort queue static void sortqueue(Queue<Integer> q) { if (q.isEmpty()) { return ; } int item = q.peek(); q.poll(); sortqueue(q); insertelement(q, item, q.size()); } public static void main(String[] args) { Queue<Integer> q = new LinkedList<>(); q.add( 3 ); q.add( 4 ); q.add( 2 ); q.add( 8 ); q.add( 1 ); q.add( 7 ); // Initially queue is 3 4 2 8 1 7 sortqueue(q); while (!q.isEmpty()) { System.out.print(q.peek() + " " ); q.poll(); } } } // This code is contributed by lokeshmvs21. |
Python3
# Python code to implement the approach # Function to push element in last # by popping from front until size becomes 0 def frontelement(q, qsize): # Base condition if qsize < = 0 : return # Pop front element and push # this last in a queue q.append(q[ 0 ]) q.pop( 0 ) # Recursive call for pushing element frontelement(q, qsize - 1 ) # function for inserting element in the queue def insertelement(q, val, qsize): if qsize = = 0 or len (q) = = 0 : q.append(val) return # If current element is greater than # the element at the front elif val > = q[ 0 ]: # Call stack with front of queue q.append(val) # Recursive call for inserting # a front element of the queue # to the last frontelement(q, qsize) else : # Push front element into last in a queue q.append(q[ 0 ]) q.pop( 0 ) # Recursive call for pushing elements in a queue insertelement(q, val, qsize - 1 ) # Function to sort queue def sortqueue(q): if len (q) = = 0 : return item = q[ 0 ] q.pop( 0 ) sortqueue(q) insertelement(q, item, len (q)) # Driver Code q = [ 3 , 4 , 2 , 8 , 1 , 7 ] # Initially queue is 3 4 2 8 1 7 sortqueue(q) print (q) # This code is contributed by Tapesh(tapeshdua420) |
C#
// C# code to implement the approach using System; using System.Collections.Generic; class Program { // Function to push element in last // by popping from front until size becomes 0 static void frontelement(Queue< int > q, int qsize) { // Base condition if (qsize <= 0) return ; // Pop front element and push // this last in a queue q.Enqueue(q.Peek()); q.Dequeue(); // Recursive call for pushing element frontelement(q, qsize - 1); } // Function for inserting element in the queue static void insertelement(Queue< int > q, int val, int qsize) { if (qsize == 0 || q.Count == 0) { q.Enqueue(val); return ; } // If current element is greater than // the element at the front else if (val >= q.Peek()) { // Call stack with front of queue q.Enqueue(val); // Recursive call for inserting // a front element of the queue // to the last frontelement(q, qsize); } else { // Push front element into last in a queue q.Enqueue(q.Peek()); q.Dequeue(); // Recursive call for pushing elements in a // queue insertelement(q, val, qsize - 1); } } // Function to sort queue static void sortqueue(Queue< int > q) { if (q.Count == 0) { return ; } int item = q.Peek(); q.Dequeue(); sortqueue(q); insertelement(q, item, q.Count); } // Driver Code static void Main( string [] args) { Queue< int > q = new Queue< int >(); q.Enqueue(3); q.Enqueue(4); q.Enqueue(2); q.Enqueue(8); q.Enqueue(1); q.Enqueue(7); // Initially queue is 3 4 2 8 1 7 sortqueue(q); while (q.Count != 0) { Console.Write(q.Peek() + " " ); q.Dequeue(); } } } // This code is contributed by Tapesh(tapeshdua420) |
Javascript
// Javascript code to implement the approach // Function to push element in last // by popping from front until size becomes 0 function frontelement(q, qsize) { // Base condition if (qsize <= 0) { return ; } // Pop front element and push // this last in a queue q.push(q[0]); q.shift(); // Recursive call for pushing element frontelement(q, qsize - 1); } // function for inserting element in the queue function insertelement(q, val, qsize) { if (qsize == 0 || q.length == 0) { q.push(val); return ; } // If current element is greater than // the element at the front else if (val >= q[0]) { // Call stack with front of queue q.push(val); // Recursive call for inserting // a front element of the queue // to the last frontelement(q, qsize); } else { // Push front element into last in a queue q.push(q[0]); q.shift(); // Recursive call for pushing elements in a queue insertelement(q, val, qsize - 1); } } // Function to sort queue function sortqueue(q) { if (q.length == 0) { return ; } var item = q[0]; q.shift(); sortqueue(q); insertelement(q, item, q.length); } // Driver Code var q = [3, 4, 2, 8, 1, 7]; // Initially queue is 3 4 2 8 1 7 sortqueue(q); console.log(q); // This code is contributed by Tapesh(tapeshdua420) |
8 7 4 3 2 1
Time complexity: O(N2)
Auxiliary Space: O(N)
Related Articles: