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

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

  ------------- -------------------------
  cua entrada   3 1 4 1 5 9 2 6
  set           {1, 5, 6}
  cua sortida   3 1 1 4 1 1 5 5 9 2 6 6
  ------------- -------------------------

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₁ e₂ ⋯ e_(N)]  {s₁ s₂ ⋯ s_(M)}
on e₁…e_(N) són els elements de la cua des del front al back, i s₁…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.

Informació del problema

Autoria: Bernardino Casas

Generació: 2026-06-11T20:25:46.089Z

© Jutge.org, 2006–2026.
https://jutge.org
