Sort the Queue using Recursion

Last Updated on December 14, 2022 by Prepbytes

Problem Statement:

Given a queue, we have to sort the queue using a recursive function without using any loop. We can only use the standard functions for it:-

• enqueue(element): Add an element to the rear end of the queue.
• dequeue(): Delete an element from the front end of the queue.
• empty(): Return true if the queue is empty else false.
• front(): Return the front element of the queue without deleting it.
• size(): Return the number of elements present in the queue.

What is a queue?

Queue follows the principle of FIFO (First in First out) i.e. element which is inserted first will be removed first. The operation for insertion of elements is known as enqueue operation and the operation for deletion of elements is known as dequeue operation. Like Stack, Queue is also a linear data structure.

Approach for sorting queue with the help of recursive function:

The idea is to make the queue empty by holding all the elements in the function call stack. When the queue becomes empty, add all held elements one by one in sorted order. In the time of insertion, sorted order is important.

How to manage sorted order?

Whenever you get the element from the function call stack, then first calculate the size of the queue and compare it with the elements of the queue. This will arises two cases:

1. If the element (returned by the function call stack) is greater than the front element of the queue then dequeue from element and enqueue that element into the same queue by decreasing the size of queue.
2. If the element is less than the front element from the queue then enqueue the element in the queue and dequeue the remaining element from the queue and enqueue by decreasing the size repeat the case 1 and 2 unless size becomes zero. One thing we have to care about is, if the size becomes zero and your element remains greater than all elements of the queue then push your element into the queue.

#include <bits/stdc++.h>
using namespace std;

void FrontToLast(queue<int>& q, int qsize)
{
	if (qsize <= 0)
		return;

	q.push(q.front());
	q.pop();

	FrontToLast(q, qsize - 1);
}

void pushInQueue(queue<int>& q, int temp, int qsize)
{

	if (q.empty() || qsize == 0) {
		q.push(temp);
		return;
	}

	else if (temp <= q.front()) {

		q.push(temp);

		FrontToLast(q, qsize);
	}
	else {

		q.push(q.front());
		q.pop();

		pushInQueue(q, temp, qsize - 1);
	}
}

void sortQueue(queue<int>& q)
{

	if (q.empty())
		return;

	int temp = q.front();

	q.pop();

	sortQueue(q);

	pushInQueue(q, temp, q.size());
}

int main()
{

	queue<int> qu;
	qu.push(10);
	qu.push(7);
	qu.push(16);
	qu.push(9);
	qu.push(20);
	qu.push(5);

	sortQueue(qu);

	while (!qu.empty()) {
		cout << qu.front() << " ";
		qu.pop();
	}
}

import java.util.*;

class GFG
{

static void FrontToLast(Queue<Integer> q,
						int qsize)
{
	if (qsize <= 0)
		return;

	q.add(q.peek());
	q.remove();

	FrontToLast(q, qsize - 1);
}

static void pushInQueue(Queue<Integer> q,
						int temp, int qsize)
{

	if (q.isEmpty() || qsize == 0)
	{
		q.add(temp);
		return;
	}

	else if (temp <= q.peek())
	{

		q.add(temp);

		FrontToLast(q, qsize);
	}
	else
	{

		q.add(q.peek());
		q.remove();

		pushInQueue(q, temp, qsize - 1);
	}
}

static void sortQueue(Queue<Integer> q)
{

	if (q.isEmpty())
		return;

	int temp = q.peek();

	q.remove();

	sortQueue(q);

	pushInQueue(q, temp, q.size());
}

public static void main(String[] args)
{
	
	Queue<Integer> qu = new LinkedList<>();
	qu.add(10);
	qu.add(7);
	qu.add(16);
	qu.add(9);
	qu.add(20);
	qu.add(5);

	sortQueue(qu);

	while (!qu.isEmpty())
	{
		System.out.print(qu.peek() + " ");
		qu.remove();
	}
}
}

class Queue:

	def __init__(self):
		self.queue = []

	def put(self, item):
		self.queue.append(item)

	def get(self):
		if len(self.queue) < 1:
			return None
		return self.queue.pop(0)
		
	def front(self):
		return self.queue[0]

	def size(self):
		return len(self.queue)
		
	def empty(self):
		return not(len(self.queue))

def FrontToLast(q, qsize) :

	if qsize <= 0:
		return

	q.put(q.get())

	FrontToLast(q, qsize - 1)

def pushInQueue(q, temp, qsize) :
	
	if q.empty() or qsize == 0:
		q.put(temp)
		return
	
	elif temp <= q.front() :

		q.put(temp)

		FrontToLast(q, qsize)

	else :

		q.put(q.get())

		pushInQueue(q, temp, qsize - 1)
	
def sortQueue(q):
	
	if q.empty():
		return

	temp = q.get()
	
	sortQueue(q)

	pushInQueue(q, temp, q.size())

qu = Queue()

qu.put(10)
qu.put(7)
qu.put(16)
qu.put(9)
qu.put(20)
qu.put(5)

sortQueue(qu)

while not qu.empty():
	print(qu.get(), end = ' ')

This article tried to discuss the concept of Sorting Queue using Recursion. Hope this blog helps you understand the concept. To practice problems you can check out MYCODE | Competitive Programming at Prepbytes