Sorting a Queue without extra space | Python3 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 ; Prsorted queue
from queue import Queue NEW_LINE def minIndex ( q , sortedIndex ) : NEW_LINE INDENT min_index = - 1 NEW_LINE min_val = 999999999999 NEW_LINE n = q . qsize ( ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT curr = q . queue [ 0 ] NEW_LINE q . get ( ) NEW_LINE if ( curr <= min_val and i <= sortedIndex ) : NEW_LINE INDENT min_index = i NEW_LINE min_val = curr NEW_LINE DEDENT q . put ( curr ) NEW_LINE DEDENT return min_index NEW_LINE DEDENT def insertMinToRear ( q , min_index ) : NEW_LINE INDENT min_val = None NEW_LINE n = q . qsize ( ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT curr = q . queue [ 0 ] NEW_LINE q . get ( ) NEW_LINE if ( i != min_index ) : NEW_LINE INDENT q . put ( curr ) NEW_LINE DEDENT else : NEW_LINE INDENT min_val = curr NEW_LINE DEDENT DEDENT q . put ( min_val ) NEW_LINE DEDENT def sortQueue ( q ) : NEW_LINE INDENT for i in range ( 1 , q . qsize ( ) + 1 ) : NEW_LINE INDENT min_index = minIndex ( q , q . qsize ( ) - i ) NEW_LINE insertMinToRear ( q , min_index ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT q = Queue ( ) NEW_LINE q . put ( 30 ) NEW_LINE q . put ( 11 ) NEW_LINE q . put ( 15 ) NEW_LINE q . put ( 4 ) NEW_LINE sortQueue ( q ) NEW_LINE while ( q . empty ( ) == False ) : NEW_LINE INDENT print ( q . queue [ 0 ] , end = " ▁ " ) NEW_LINE q . get ( ) NEW_LINE DEDENT DEDENT