Sorting Queue Without Extra Space

Queue:

The queue is a linear data structure that works on the principle of First in First out (FIFO). In the queue, the element which is added at least recently is removed first from it. For example, a queue of consumers for a resource or service where the consumer who comes first will be served first.

Given below are the operations of the queue:

• Enqueue: This function is used to add an element to the rear end of the queue. If the queue is completely filled, then it will be in an overflow condition. The time complexity of the enqueue is O(1).
• Dequeue: This function is used to remove an element from the front end of the queue. If the queue is empty, then it will be in an underflow condition. The time complexity of the dequeue is O(1).
• Front: This function returns the front element of the queue. The time complexity of this function is O(1).
• Rear: This function returns the last element of the queue. The time complexity of this function is O(1).

And we have C++ STL operations also such as isEmpty(): This operation is used to check whether the queue is empty or not.

Let’s take an example:
Input queue 1 = 100 50 40 200
MODIFIED QUEUE
Output queue = 40 50 100 200

Input queue 2 = 4 5 1 3 2
MODIFIED QUEUE
Output queue 2 = 1 2 3 4 5

What if we are allowed to use extra space?

If we are allowed to use an extra space we’ll use an array and move all the elements from the queue to array and then sort the array and finally move all the elements back to the queue.

How to do it without using an extra space?

So, on every iteration on the queue, we’ll be looking for the next minimum index. To do this we dequeue the element then we enqueue the element until we will find the next minimum. Basically in this operation the queue is not changed at all and after we have found the minimum index then we dequeue and enqueue the elements from the queue except for the minimum index. After the traversal of the queue we’ll insert the minimum from the rear of the queue. We keep on this until all minimums are pushed to the front and finally the queue will become sorted.
We repeat this method for n times.
And also first we need to find the maximum, because on every iteration we need to find the next minimum so that we can compare it with the maximum element from the queue.

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

int minIndex(queue<int> &q, int sortedIndex)
{
	int min_index = -1;
	int min_val = INT_MAX;
	int n = q.size();
	for (int i=0; i<n; i++)
	{
		int curr = q.front();
		q.pop(); 

		
		if (curr <= min_val && i <= sortedIndex)
		{
			min_index = i;
			min_val = curr;
		}
		q.push(curr); 
	}
	return min_index;
}

void insertMinToRear(queue<int> &q, int min_index)
{
	int min_val;
	int n = q.size();
	for (int i = 0; i < n; i++)
	{
		int curr = q.front();
		q.pop();
		if (i != min_index)
			q.push(curr);
		else
			min_val = curr;
	}
	q.push(min_val);
}

void sortQueue(queue<int> &q)
{
	for (int i = 1; i <= q.size(); i++)
	{
		int min_index = minIndex(q, q.size() - i);
		insertMinToRear(q, min_index);
	}
}

int main()
{
queue<int> q;
q.push(300);
q.push(110);
q.push(150);
q.push(40);

sortQueue(q);

while (q.empty() == false)
{
	cout << q.front() << " ";
	q.pop();
}
cout << endl;
return 0;
}

import java.util.LinkedList;
import java.util.Queue;
class GFG
{

	public static int minIndex(Queue<Integer> list,
									int sortIndex)
	{
	int min_index = -1;
	int min_value = Integer.MAX_VALUE;
	int s = list.size();
	for (int i = 0; i < s; i++)
	{
		int current = list.peek();
		
	
		list.poll();

		if (current <= min_value && i <= sortIndex)
		{
			min_index = i;
			min_value = current;
		}
		list.add(current);
	}
	return min_index;
}

	public static void insertMinToRear(Queue<Integer> list,
											int min_index)
	{
		int min_value = 0;
		int s = list.size();
		for (int i = 0; i < s; i++)
		{
		int current = list.peek();
		list.poll();
		if (i != min_index)
			list.add(current);
		else
			min_value = current;
		}
		list.add(min_value);
	}
	
	public static void sortQueue(Queue<Integer> list)
	{
		for(int i = 1; i <= list.size(); i++)
		{
			int min_index = minIndex(list,list.size() - i);
			insertMinToRear(list, min_index);
		}
	}

	public static void main (String[] args)
	{
		Queue<Integer> list = new LinkedList<Integer>();
		list.add(300);
		list.add(110);
		list.add(150);
		list.add(40);
		
		sortQueue(list);
		
		while(list.isEmpty()== false)
		{
			System.out.print(list.peek() + " ");
			list.poll();
		}
	}
}

from queue import Queue

def minIndex(q, sortedIndex):
	min_index = -1
	min_val = 999999999999
	n = q.qsize()
	for i in range(n):
		curr = q.queue[0]
		q.get() 
		if (curr <= min_val and i <= sortedIndex):
			min_index = i
			min_val = curr
		q.put(curr) 
	return min_index

def insertMinToRear(q, min_index):
	min_val = None
	n = q.qsize()
	for i in range(n):
		curr = q.queue[0]
		q.get()
		if (i != min_index):
			q.put(curr)
		else:
			min_val = curr
	q.put(min_val)

def sortQueue(q):
	for i in range(1, q.qsize() + 1):
		min_index = minIndex(q, q.qsize() - i)
		insertMinToRear(q, min_index)

if __name__ == '__main__':
	q = Queue()
	q.put(300)
	q.put(110)
	q.put(150)
	q.put(40)
	
	sortQueue(q)
	
	while (q.empty() == False):
		print(q.queue[0], end = " ")
		q.get()

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