En tancar el mòdul de piles vam deixar tres fils pendents: un HistorialAmbLimit que necessitava treballar pels dos extrems, un min-stack que podia consultar l'element més prioritari però no extreure'l, i una promesa: processar les tasques de TaskFlow "per ordre just d'arribada". Els tres fils es lliguen en aquest mòdul, i tots tres apunten a la mateixa família d'estructures: les cues. En aquesta lliçó presentem el TAD cua, el seu principi FIFO, el seu contracte d'operacions i els llocs (ben reals) on les cues sostenen sistemes sencers. Encara no implementarem res en detall: primer cal entendre bé què és una cua i per a què serveix; el com arriba a la lliçó següent.

1. De la pila a la cua: els tres ponts pendents
2. El principi FIFO
3. LIFO vs FIFO: dues polítiques oposades
4. El contracte del TAD cua
5. Analogies: el supermercat i la impressora
6. Cues en sistemes reals
7. La cua de notificacions de TaskFlow
8. El mapa del mòdul 4

Recordem exactament on ens vam quedar al final del mòdul 3:

• L'historial amb límit: el nostre HistorialAmbLimit apilava per dalt però, en omplir-se, descartava pel fons amb un pop(0) de cost O(n). Necessitàvem una estructura eficient pels dos extrems. Aquesta estructura existeix, es diu deque (cua doble), i la veurem a la lliçó 04-05.
• El "més prioritari": la PilaAmbMinim responia en O(1) "quin és l'element mínim?", però no permetia extreure'l si no era al cim. Extreure sempre el més prioritari és just el que fa una cua de prioritat (lliçó 04-04).
• L'ordre just: una pila atén primer l'últim que ha arribat. En moltes situacions això és exactament el contrari del que volem: les notificacions de TaskFlow s'han d'enviar en l'ordre en què es van generar. Aquesta política és el FIFO, i és el cor d'aquest mòdul.

Fixa't en el patró: no canviem d'estructura per caprici, sinó perquè el problema ens hi empeny. Igual que la pila era l'estructura natural del "desfer", la cua és l'estructura natural de l'"atendre per ordre d'arribada".

FIFO són les sigles de First In, First Out: el primer que entra és el primer que surt. Una cua és un TAD (tipus abstracte de dades, com vam veure al mòdul 1) amb dues regles d'accés molt estrictes:

• Els elements entren sempre per un extrem, anomenat el final (o cua, en el sentit de "final de la fila").
• Els elements surten sempre per l'altre extrem, anomenat el front.

Aquesta separació d'extrems és la diferència essencial amb la pila, on tot passava pel mateix costat (el cim). En usar extrems oposats, l'ordre de sortida reprodueix exactament l'ordre d'arribada:

Si encuem les notificacions 1, 2 i 3 (en aquest ordre) i després desencuem tres vegades, obtenim 1, 2 i 3, en aquest mateix ordre. Amb una pila hauríem obtingut 3, 2 i 1.

Convé tenir les dues polítiques cara a cara, perquè triar malament entre elles produeix errors silenciosos (el programa funciona, però atén les coses en l'ordre equivocat):

Una manera útil de decidir quina necessites: pregunta't quin element s'ha d'atendre a continuació. Si la resposta és "el més recent" (desfer, tornar enrere, tancar l'últim parèntesi obert), és una pila. Si és "el que fa més temps que espera" (atendre peticions, enviar missatges, repartir feina amb justícia), és una cua.

Com vam fer amb la pila, definim la cua pel seu contracte: quines operacions ofereix i què promet cadascuna, sense dir encara res de com s'implementa per dins. Aquest és l'esperit del TAD del mòdul 1: primer la interfície, després la implementació.

Dues observacions que ja coneixes del mòdul 3 i que continuen vigents:

• Error en cua buida: mantindrem la decisió que vam prendre amb la pila: desencuar() i front() sobre una cua buida llancen una excepció (estil EAFP), en lloc de retornar None. Un None silenciós es confon amb un element vàlid i amaga errors.
• Contracte estable, implementació intercanviable: igual que Pila i PilaEnllacada compartien contracte (i ho verificàvem amb provar_contracte), en aquest mòdul veurem diverses implementacions de cua amb aquest mateix contracte. El codi client no hauria de notar el canvi.

Encara que no hem implementat res, ja podem escriure codi contra el contracte, que és com pensa un bon dissenyador de programari:

Observa que la tasca amb prioritat: 1 (la màxima a TaskFlow) no surt la primera: en una cua FIFO mana l'ordre d'arribada, no la urgència. Quan vulguem que mani la urgència necessitarem una altra estructura —la cua de prioritat de la lliçó 04-04—. Distingir totes dues necessitats és mitja batalla guanyada.

La cua del supermercat. Les persones s'incorporen pel final i la caixera atén pel front. Ningú (en un món civilitzat) no es cola: qui fa més temps que espera és atès primer. Les dues operacions del contracte són a la vista: arribar a la fila és encuar, ser atès és desencuar, i mirar qui és el següent sense atendre'l encara és front.

La cua d'impressió. Diverses persones envien documents a una impressora compartida. La impressora només pot imprimir un document alhora, així que les feines esperen en una cua: s'imprimeixen en l'ordre exacte en què es van enviar. Aquesta analogia afegeix un matís important que el supermercat no té: la cua actua d'amortidor entre un productor ràpid i un consumidor lent. Deu persones poden enviar documents en un segon; la impressora trigarà minuts a processar-los, però cap no es perd i cap no avança un altre. Guarda't aquesta idea: és la clau de gairebé tots els usos professionals de les cues.

Les cues no són un exercici acadèmic; són una de les estructures més usades en sistemes en producció:

• Cues de missatges (RabbitMQ, Amazon SQS, Kafka en la seva versió més simple): un servei deixa missatges en una cua i un altre servei els consumeix al seu ritme. És la impressora a escala industrial: desacobla productors de consumidors i absorbeix pics de càrrega sense perdre feina.
• Buffers d'entrada/sortida: quan escrius al teclat més de pressa del que el programa llegeix, les pulsacions esperen en un buffer FIFO. El mateix passa amb paquets de xarxa en un router o amb àudio en streaming. Molts d'aquests buffers tenen mida fixa i "fan la volta": són les cues circulars de la lliçó 04-03.
• Planificadors de processos: el sistema operatiu manté cues de processos a punt per executar-se. La variant més famosa, el round-robin, reparteix torns de CPU per ordre d'arribada; connecta directament amb el RepartidorTasques que vam construir sobre la LlistaCircular al mòdul 2, i el reprendrem als exercicis (04-06).
• Recorreguts de grafs: l'algorisme BFS (cerca en amplada) explora un graf "per capes" usant una cua. Només ho deixem anotat com a avançament: es desenvolupa al mòdul 7.

Situem tot això a la nostra aplicació. Cada cop que a TaskFlow passa alguna cosa rellevant —s'assigna una tasca, canvia un estat, s'acosta una data límit— cal notificar-ho a l'usuari afectat. Enviar una notificació (correu, avís al mòbil) és lent comparat amb generar l'esdeveniment, així que no podem enviar-les "al moment": les acumularíem i bloquejaríem l'aplicació.

La solució professional és la de la impressora: un productor (l'aplicació) encua notificacions a l'instant, i un consumidor (el procés d'enviament) les va desencuant i enviant al seu ritme. Requisits:

1. Cap notificació no es perd.
2. S'envien en l'ordre en què es van generar (seria absurd rebre "tasca completada" abans que "tasca creada").
3. Encuar ha de ser instantani, perquè passa enmig de l'acció de l'usuari.

Els requisits 1 i 2 els garanteix el contracte FIFO. El requisit 3 és una exigència de cost: encuar i desencuar han de ser O(1). I aquí ve l'avís per a la propera lliçó: la implementació "òbvia" amb una list de Python incompleix aquest requisit, per la mateixa trampa del pop(0) que vam mesurar amb timeit al mòdul 1. Resoldre-ho amb elegància —reutilitzant la LlistaEnllacada del mòdul 2— és l'objectiu de la lliçó 04-02.

Perquè sàpigues què t'espera, aquest és el pla del mòdul, i no és casual: cada lliçó respon a un dels ponts del mòdul 3.

• Confondre la política amb l'estructura: FIFO és una política (un contracte); la cua es pot implementar de moltes maneres (llista enllaçada, dues piles, array circular). No diguis "una cua és una llista": una cua és un contracte que una llista pot (bé o malament) implementar.
• Usar una pila on toca una cua (o viceversa): el codi no fallarà, però l'ordre d'atenció serà l'invers de l'esperat. Si processes notificacions amb una pila, l'usuari rebrà primer l'última generada. Pregunta't sempre: ha de sortir "el més recent" o "el més antic"?
• Esperar que la cua FIFO respecti prioritats: no ho fa, i no ho ha de fer. Si una tasca de prioritat 1 ha d'avançar les altres, necessites una cua de prioritat (04-04), no un FIFO amb pedaços.
• Consell: quan llegeixis documentació de sistemes (missatgeria, sistemes operatius, xarxes), busca les paraules queue, enqueue, dequeue, front/head i rear/tail. Reconèixer el contracte sota noms diferents és senyal que has interioritzat el TAD.

Sense executar res, indica què imprimeix aquest codi (assumint una Cua que compleix el contracte):

Per a cada escenari de TaskFlow, decideix si l'estructura adequada és una pila (LIFO) o una cua (FIFO), i justifica-ho en una frase:

1. Reproduir els canvis d'una tasca en ordre cronològic per a auditoria.
2. Desfer les últimes modificacions de la descripció d'una tasca.
3. Repartir les peticions d'exportació d'informes entre els usuaris, atenent-les amb justícia.
4. Comprovar que els parèntesis d'una fórmula de filtre estan balancejats.

La impressora de l'oficina necessita, a més del contracte bàsic de cua, una operació perquè un administrador cancel·li totes les feines pendents. Escriu la taula de contracte completa (operació, què fa, què promet) d'aquesta CuaImpressio, sense implementar-la. Pista: cancel·lar-ho tot no ha d'obligar a desencuar en bucle des de fora.

Solució 1:

La clau és a la tercera línia: front() no extreu, per això després desencuar() continua retornant "B".

Solució 2:

1. Cua: l'auditoria exigeix ordre cronològic d'arribada (FIFO).
2. Pila: desfer atén sempre el més recent (LIFO), com el GestorDesferRefer del mòdul 3.
3. Cua: "amb justícia" = per ordre d'arribada, ningú no es cola.
4. Pila: cada tancament casa amb l'obertura més recent, exactament el filtre_balancejat del mòdul 3.

Solució 3:

Fixa't que ampliar un contracte és legítim; l'important és prometre amb precisió què fa la nova operació, casos frontera inclosos.

Hem definit la cua com a TAD: un contracte FIFO amb encuar, desencuar, front, esta_buida i mida, on els elements entren pel final i surten pel front, garantint l'ordre d'arribada. L'hem contrastada punt per punt amb la pila, hem vist que sosté sistemes reals (cues de missatges, buffers, planificadors) i hem identificat el seu paper a TaskFlow: la cua de notificacions pendents d'enviar, que exigeix a més costos O(1) a tots dos extrems. Just aquí hi ha el repte: la implementació ingènua sobre list cau a la trampa del pop(0) que ja coneixem. A la propera lliçó executarem les operacions pas a pas, mesurarem aquesta trampa i construirem la classe Cua correcta reutilitzant la LlistaEnllacada del mòdul 2 — amb una sorpresa final: una cua feta amb dues piles.