Reordena la Pila. X74456

Una pila quasi-ordenada és una pila (d’enters) que té tots els elements en ordre (el més petit al fons de la pila) llevat de dos elements que estan intercanviats i a més són sempre un a sobre de l’altre a la pila.

Per exemple, la pila

                   | 9 |
                   | 7 | <-
                   | 8 | <-
                   | 5 |
                   | 3 |
                   | 2 |
                   ----- 

està quasi-ordenada, ja que té els elements 7 i 8 únicament desordenats.

Feu la funció void reordenaPila (stack<int> &P) tal que, donada una pila quasi-ordenada d’enters positius, retorni la mateixa pila, però ordenada.

Cal tenir en compte que la pila es passa com a paràmentre d’entrada i sortida (per referència).

Entrada

Una pila quasi-ordenada d’enters.

Sortida

La mateixa pila ordenada.

Observació

Heu d’enviar la solució comprimida en un fitxer .tar:

tar cvf program.tar reordenaPila.cpp

Observeu que per compilar us donem el Makefile, les utilitats d’entrada/sortida de piles a utilitats.hpp, la capçalera del mòdul funcional reordenaPila.hpp i el programa principal program.cpp.

Jutge.org també us donarà un semàfor verd si envieu una solució iterativa, però no serà correcte ja que l’enunciat del problema demana que la solució enviada sigui recursiva.