Queue: Sort a queue without using extra space

Problem Statement:

You are given a queue, you need to reverse the queue without using extra space.

Example:

Input: 1 2 3 4

Output: 4 3 2 1

Solution 1: Bruteforce approach

If we are able to use extra space, then copy the elements from the queue to array.

Then sort the array.

Then copy array elements to queue.

Time Complexity: O(log n)
Space Complexity: O(n)

Solution 2: Efficient approach

The solution is very simple.

In the solution, we need to find the next min index.

We do this by dequeue the element and enqueue the element till we find the next min.

Once we find the min index, then we dequeue and enqueue the element form the queue except for the min index.

Then we insert the min from the rear of the queue, proceed with the same steps till the queue is sorted.

Time Complexity: O(n*n)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <queue>
#include <climits>
using namespace std;

int getMinIndex(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 insertRear(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 solution_1(queue<int> &q)
{
    for (int i = 1; i <= q.size(); i++)
    {
        int min_index = getMinIndex(q, q.size() - i);
        insertRear(q, min_index);
    }
}

int main()
{
  queue<int> q;
  q.push(1);
  q.push(2);
  q.push(3);
  q.push(4);
  
  solution_1(q);
  
  cout<<"Solution = "<<endl;
  while (q.empty() == false)
  {
     cout << q.front() << " ";
     q.pop();
  }
  cout << endl;
  return 0;
}

Output

Solution = 
1 2 3 4