Trenat de cues X22646

Considerem la representació habitual amb nodes de la classe Cua per manegar cues genèriques d’elements de tipus T que podeu trobar als fitxers públics. Els nodes són simplement encadenats amb punters al següent (seguent). Una cua té tres atributs: la longitud i dos punters a nodes, un pel pimer element (primer_node) i un per l’últim (ultim_node).

Diem que el resultat de trenar dues cues $q_1$ i $q_2$ és una cua $q_3$ on els elements de $q_1$ apareixen a les posicions senars (primera, tercera, cinquena, etc) i els elements de $q_2$ apareixen a les posicions parelles (segona, quarta, sisena, etc). Després de l’últim element de la més curta apareixen la resta dels elements de la més llarga.

Volem implementar dins de la classe Cua una operació nova amb la següent especificació:

void trenat(Cua &c)
/* Pre: p.i. = C1, c = C2 */
/* Post: el p.i. passa a ser el resultat de trenar C1 i C2; c passa a ser buida */

Exemples:

1. Si el p.i. és originalment

   1   5   14   25   8

   i $c$ és

   99   3

   llavors el p.i. ha de quedar.

   1   99   5   3   14   25   8

2. Si el p.i. és originalment

   67   89

   i $c$ és

   19   24   5   17   6

   llavors el p.i. ha de quedar.

   67   19   89   24   5   17   6

Dissenyeu aquesta operació sense utilitzar cap de les operacions primitives de les cues, accedint directament als atributs de la classe Cua.

Entrada

L’entrada son dues cues.

Sortida

La sortida és una cua el resultat de la qual és el trenat de les dues cues d’entrada.

Observació

Només s’ha d’enviar un fitxer que contengui la funció amb la capçalera de l’enunciat i qualsevol altra funció auxiliar que cregueu convenient, sense la funció main i sense posar-hi cap “include”.