Mètode de Queue que duplica només els elements que pertanyen a un set S59319

Donada la classe Queue<T> implementada amb una llista simplement encadenada, fes el mètode RECURSIU:

void duplicate(const set<T>& s);

Aquest mètode duplica cada element de la cua que pertanyi a s, és a dir, ha d’aparèixer dues vegades consecutives (original i la còpia, adjacents). Els elements que no pertanyen a s no es toquen. Si un element apareix diverses vegades a la cua i pertany a s, totes les seves ocurrències es dupliquen.

Exemple

Què has de lliurar

D’entre els fitxers que s’adjunten en aquest exercici, trobaràs queue.old.hpp, a on hi ha una implementació de la classe genèrica Queue. En primer lloc, hauràs de fer:

cp queue.old.hpp queue.hpp

A continuació si obres el fitxer queue.hpp al final del mateix trobaràs el mètode que has d’implementar:

void duplicate(const set<T>& s);

IMPORTANT: No toquis la resta de la implementació de la classe, excepte si per algun motiu, consideres que necessites afegir algun mètode auxiliar o atribut a la part privada.

D’entre els fitxers que s’adjunten a l’exercici també hi ha program.cpp (programa principal) i Makefile per a compilar i generar l’executable. El programa principal que t’oferim ja s’encarrega de llegir les cues i els sets i fer les crides al mètode indicat. Només cal que implementis el mètode duplicate.

Per a pujar la teva solució, has de crear el fitxer solution.tar així:

tar cf solution.tar queue.hpp

Observacions

• No es pot usar cap contenidor auxiliar de la STL (vector, stack, queue, …) llevat de set.

• Has de trobar una solució RECURSIVA i eficient del problema. En particular, no hi hauria d’haver cap bucle en cap dels mètodes que implementis.

• Hauries d’aconseguir implementar el mètode demanat a base de crear nous nodes. De fet, una solució a base d’usar push i pop potser et permetrà passar els jocs de proves, però atès que la solució ha de ser eficient en temps i espai, aquest tipus de solució serà fortament penalitzat.

• Recorda que tots els mètodes que implementis han de tenir les corresponents Precondició (Pre) i Postcondició (Post).

• En les crides recursives inclou la hipòtesi d’inducció (HI) i la funció de fita (FF).

Entrada

L’entrada del programa és una seqüència de cues i sets.

Cada línia descriu un cas de prova amb el format: $$[e_1 \; e_2 \; \cdots \; e_N] \quad \{s_1 \; s_2 \; \cdots \; s_M\}$$ on $e_1\ldots e_N$ són els elements de la cua des del front al back, i $s_1 \ldots s_M$ són els elements del set (tots diferents).

Sortida

Per cada cas de prova s’escriurà la cua resultant d’aplicar el mètode duplicate. Per escriure les cues, s’ha utilitzat l’operador << que es troba definit en el fitxer queue.hpp.