Intercalació recursiva de dues cues de manera alterna V18561

Implementa una funció RECURSIVA que, donades dues cues d’enters, retorna una altra cua que conté la cua resultat d’intercalar els elements de la primera cua amb els elements de la segona. Si una de les cues s’acaba abans que l’altra, els elements sobrants s’afegeixen tal qual a la cua resultant.

La capçalera de la funció és la següent:

Per exemple, donades les cues

 
q1 = [1, 3, 5] (1 seria el primer element de la cua) 
q2 = [2, 4, 6, 8, 10] (2 seria el primer element de la cua)
 
intercala_cues(q1, q2) = [1, 2, 3, 4, 5, 6, 8, 10] 

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

Observació

La funció i les subfuncions que creïs han de treballar només amb cues (la classe queue de la biblioteca STL). Has de trobar una solució RECURSIVA i eficient del problema. En particular, no hi hauria d’haver cap bucle en cap de les funcions que implementis. Si crees funcions auxiliars, afegeix-hi les corresponents Pre i Post. En les crides recursives, inclou tant la Hipòtesi d’inducció com la funció de fita/decreixement de cada crida recursiva.