Sorting a Queue without extra space | C ++ program to implement sorting a queue data structure ; Queue elements after sortedIndex are already sorted . This function returns index of minimum element from front to sortedIndex ; This is dequeue ( ) in C ++ STL ; we add the condition i <= sortedIndex because we don 't want to traverse  on the sorted part of the queue,  which is the right part. ; This is enqueue ( ) in C ++ STL ; Moves given minimum element to rear of queue ; SortQueue Function ; driver code ; Sort queue ; Print sorted queue
#include <bits/stdc++.h> NEW_LINE 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 ( 30 ) ; q . push ( 11 ) ; q . push ( 15 ) ; q . push ( 4 ) ; sortQueue ( q ) ; while ( q . empty ( ) == false ) { cout << q . front ( ) << " ▁ " ; q . pop ( ) ; } cout << endl ; return 0 ; }