Eliminar repetits en una cua X90153

Implementeu una funció ITERATIVA que, donada una cua Q com a paràmetre (amb els valors ordenats, de cap a cua, potser amb repeticions), retorna una cua R que conté tots els valors que hi ha a Q en el mateix ordre i sense repeticions. La funció és aquesta:

queue<int> uniq(queue<int> q);

• PRE Q = [a₁,a₂, … ,a_n] i ∀_{i = 1}ⁿ⁻¹ a_i ≤ a_i+1.
• POST Torna una cua R = [b₁, b₂, …, b_m] tal que ∀_{i = 1}^m b_i < b_i+1 i a més ∀_{i = 1}ⁿ a_i ∈ R. És a dir, R conté tots els valors que hi ha a Q sense repeticions i en el mateix ordre.

Aquí tenim uns exemples de comportament de la funció:

uniq([1 2 2 2 3 5 5 5 5]) = [1 2 3 5]

uniq([1 2 3 4]) = [1 2 3 4]

Observació Només cal enviar el procediment demanat; el programa principal serà ignorat.

Observació

La vostra funció i subfuncions que creeu han de treballar només amb cues. Heu de trobar una solució ITERATIVA del problema.

Avaluació sobre 10 punts:

• Jocs de prova públics, semàfor verd: 6 punts.
• Jocs de prova privats, semàfor verd: 4 punts

Coses que poden restar punts a la puntuació anterior:

• Recursiu en comptes d’iteratiu (o viceversa): zero de nota final.
• Utilització d’estructures de dades auxiliars diferents del tipus que apareix a l’enunciat: des de -5 fins a zero de nota final. En cas de dubte, demaneu al professor.
• No fer immersió de paràmetres/resultats si això millora el cost assimptòtic del vostre codi: de -5 cap endavant, depenent de la gravetat.
• Manipulació excessiva d’estructures de dades: de -5 cap endavant. Exemple: agafar una pila i capgirar-la més del que cal.
• No posar PRE/POST a les funcions auxiliars que feu servir: -3. Òbviament, ja us donem la PRE/POST de la funció que us demanem, no cal que la repetiu. Ara bé, si feu una funció que implementa una generalització de la funció que us demanem, sí que cal que en feu la PRE/POST.
• No posar l’invariant si feu un bucle: -2.