Mantenir la pila ordenada. X98875

Feu una funció recursiva tal que, donada una pila d’enters positius, no necessàriament ordenada, i que tindrà, almenys, un element. retorni la mateixa pila però eliminant-ne els elements que no estiguin ordenats de manera extrictament creixent (des del cim cap al fons de la pila). Per exemple, si tenim la pila:

                        | 3 |
                        | 5 |
                        | 4 |
                        | 5 |
                        | 7 |                          
                        | 8 |
                        | 2 |
                        -----
                

veiem que si eliminem el 4, el 2 i el segon 5, llavors la pila estarà ordenada:

                        | 3 |
                        | 5 |
                        | 7 |                                
                        | 8 |
                        -----
       

És a dir, a partir del cim, anem eliminant els element que no estiguin ordenats. La pila ha de quedar ordenada de manera creixent a partir del cim (de dalt a baix, anem a dir).

La capçalera de la funció serà:

stack<int> pilaOrdenada (stack<int> P)

La puntuació que podeu obtenir és la següent:

1. Solució correcta en els jocs de proves públics: 5 punts.
2. Solució correcta en els jocs de proves públics, especificació de la funció i H.I. : 7 punts.
3. Solució correcta en els jocs de proves públics i privats: 8 punts.
4. Solució correcta en els jocs de proves públics i privats, especificació de la funció i H.I.: 10 punts.

Només acceptarem una solució recursiva per a aquest problema.

Quan diem especificació de la funció, H.I. i funció fita volem dir que hi ha de ser tot. Dit altrament: no es donarà una fracció dels 2 punts si doneu només, per exemple, l’especificació de la funció, o només la H.I. i la fita. Se us donarà la bonificació dels 2 punts únicament si feu totes 3 coses correctament.

Entrada

Una llista d’enters positius i que representa una pila d’enters, és a dir, el primer element de la seqüència és el fons de la pila, i el darrer n’és el cim, tot i que això no té importància, ja que us donem el programa principal que s’encarrega de llegir de l’entrada estàndard i fa la crida a la funció.

Sortida

Els elements que queden a la pila d’entrada eliminant-ne els element que no estiguin ordenats.

Observació

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

tar cvf program.tar pilaOrdenada.cpp

Observeu que per compilar us donem el Makefile, la capçalera del mòdul funcional pilaOrdenada.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.