En tancar el mòdul anterior vam deixar TaskFlow amb un tauler de tasques sobre llistes enllaçades, un repartiment de torns round-robin amb llistes circulars i un historial de navegació amb llista doblement enllaçada. I va quedar una promesa a l'aire: una estructura que s'implementa "en unes poques línies" perquè ja saps inserir i esborrar pel cap d'una llista enllaçada en O(1), i que farà possible el desfer de TaskFlow. Aquesta estructura és la pila (stack), i aquesta lliçó la presenta com a tipus abstracte de dades: què és, quin contracte ofereix, on apareix constantment en la teva vida com a programador i per què encaixa com un guant en el desfer de TaskFlow. Encara no implementarem res en detall: primer cal entendre bé el concepte.

1. De la llista enllaçada a la pila
2. El principi LIFO
3. El contracte del TAD pila
4. Com funciona una pila: diagrama
5. Piles en la vida del programador
6. La pila a TaskFlow: el desfer
7. Costos esperats del contracte

Al mòdul 2 vas aprendre que en una LlistaEnllacada hi ha dues operacions especialment barates:

• inserir_al_principi(dada): crear un Node i enganxar-lo com a nou cap → O(1).
• Esborrar el cap: moure el punter cap al node següent → O(1).

Ara fes-te aquesta pregunta: què passa si et prohibeixes totes les altres operacions? Res d'inserir_a, res d'esborrar per predicat al mig de la llista, res de recórrer per cercar. Només pots tocar un extrem: el cap.

El que obtens és una estructura més restringida... i precisament per això més potent conceptualment. En limitar les operacions, l'estructura adquireix un comportament predictible que modela situacions reals: la pila.

Aquesta idea —guanyar claredat traient llibertat— és recurrent en estructures de dades. Una pila no és "una llista a la qual li falten coses": és un contracte diferent, amb les seves pròpies garanties, que casualment es pot construir sobre una llista. Recorda la distinció TAD vs. implementació del mòdul 1: allà vam veure PilaAmbLlista i PilaAmbDiccionari com a exemple que un mateix contracte admet diverses implementacions. Ha arribat el moment d'entendre aquest contracte de debò.

Una pila és una col·lecció on els elements entren i surten sempre pel mateix extrem, anomenat cim (top). La conseqüència és la regla que defineix la pila:

LIFO: Last In, First Out — l'últim a entrar és el primer a sortir.

Imagina la pila de plats nets d'una cuina:

• Quan fregues un plat, el col·loques damunt de la pila.
• Quan necessites un plat, agafes el de dalt.
• El plat del fons pot portar setmanes allà: només sortirà quan s'hagin retirat tots els que té a sobre.

Ningú no treu un plat del mig (acabaria tot a terra). Aquesta restricció física és exactament la restricció lògica de la pila.

Quan prems Ctrl+Maj+T al navegador per reobrir una pestanya tancada, quina reapareix? L'última que vas tancar. Si ho tornes a prémer, reapareix l'anterior a aquesta. El navegador guarda les pestanyes tancades en una pila: cada tancament "apila" una pestanya, cada reobertura "desapila" la més recent.

Existeix la política contrària, FIFO (First In, First Out, com la cua del supermercat): aquesta és la cua, protagonista del mòdul 4. Aquí només ens quedem amb el contrast:

Com tot TAD, la pila es defineix per les seves operacions, no per com s'implementin. Aquest és el contracte que farem servir durant tot el mòdul (i els noms exactes que implementarem a la lliçó 03-03):

Fixa't en tres detalls del contracte:

• pop fa dues coses alhora: retira i retorna. No existeix "retirar sense saber què retires".
• peek existeix perquè pop és destructiu. Sovint vols saber què hi ha al cim (per exemple, "quina seria la propera acció a desfer?") sense desfer-la encara.
• No hi ha accés per posició. No pots preguntar "què hi ha a la posició 3?". Si necessites això, no necessites una pila; necessites una llista.

A la lliçó 03-02 veurem cada operació pas a pas, amb traces de l'estat de la pila; a la 03-03 les implementarem de dues maneres diferents. Avui n'hi ha prou d'entendre què prometen.

El diagrama següent mostra la idea central: push i pop operen sempre sobre el mateix extrem, el cim.

Lectura del diagrama:

• accio_1 va ser la primera a entrar i va quedar al fons: serà l'última a sortir.
• accio_3 és el cim actual: peek() la mostraria, pop() la retiraria.
• Si ara féssim push(accio_4), aquesta passaria a ser el nou cim, tapant accio_3.

Observa el paral·lelisme amb la llista enllaçada: el cim de la pila jugarà el paper del cap de la llista. Per això la promesa de 02-05 no era exagerada: ja tens tota la mecànica apresa.

Les piles no són una curiositat acadèmica: les estàs fent servir ara mateix, encara que no les vegis.

Cada vegada que Python executa una funció, apila un registre amb les seves variables locals i el punt de retorn. Quan la funció acaba, es desapila i l'execució torna on era. Per això, quan una funció a() crida b() i aquesta crida c(), en acabar c() tornem a b(), i en acabar b() tornem a a(): l'últim a entrar és el primer a sortir. Quan vegis un traceback d'error a Python, estàs veient una foto d'aquesta pila. Ho explorarem amb codi a la lliçó 03-04.

Tot editor de text guarda cada canvi en una pila. Ctrl+Z desapila el canvi més recent i el reverteix. És l'aplicació estrella de les piles i la que construirem per a TaskFlow.

El botó "enrere" del navegador es comporta com una pila de pàgines visitades. Al mòdul 2 ja vam muntar HistorialTasques amb una llista doblement enllaçada per moure'ns enrere i endavant; a la lliçó 03-04 veurem que "enrere i endavant" també es pot modelar amb dues piles cooperant, i compararem tots dos enfocaments.

• Comprovar que parèntesis i claudàtors estan balancejats (03-04).
• Avaluar expressions matemàtiques (03-04).
• Recórrer arbres i grafs en profunditat (DFS): ho anticiparem a 03-04 i ho desenvoluparàs als mòduls 6 i 7.

Situem-nos a TaskFlow. Un usuari treballa amb les seves tasques, representades com a diccionaris:

Al llarg del matí, l'usuari:

1. Crea la tasca 7.
2. Li canvia la prioritat de 2 a 1.
3. La marca com a "en curs".
4. L'assigna a l'Anna ("assignada_a": "anna").

Ara prem Desfer. Què espera que passi? Que es reverteixi l'assignació a l'Anna, no que s'esborri la tasca. Prem Desfer un altre cop: la tasca torna a "pendent". Un altre cop: la prioritat torna a 2.

És a dir: el desfer reverteix les accions en ordre invers al que es van fer. L'última acció realitzada és la primera a desfer-se. Això és LIFO al peu de la lletra, i per això l'estructura correcta per al desfer és una pila:

• Cada vegada que l'usuari fa alguna cosa → push(accio) a la pila d'historial.
• Cada vegada que prem Desfer → pop() recupera l'acció més recent i es reverteix.
• El botó Desfer està actiu? → esta_buida() ho decideix.
• "Desfer: canviar prioritat" com a text del botó → peek() sense tocar res.

Fixa't que les quatre necessitats reals de la interfície es corresponen una a una amb el contracte del TAD. Quan això passa, has triat bé l'estructura.

Part del contracte de la pila és el seu rendiment. Una pila ben implementada garanteix que totes les seves operacions són de temps constant:

Cap operació no depèn de quants elements hi hagi: tant se val que l'historial de TaskFlow tingui 10 accions o 10 milions, desfer l'última costarà el mateix. Compara-ho amb la llista, on cercar o inserir al mig era O(n): en restringir el contracte, hem pogut garantir que tot el que la pila ofereix és O(1). A la lliçó 03-03 verificarem aquesta taula amb timeit, i matisarem la diferència entre O(1) amortitzat i O(1) garantit segons la implementació.

• Confondre pila amb llista: si et sorprens volent accedir "al tercer element" d'una pila, atura't. O estàs fent servir l'estructura equivocada, o estàs trencant el contracte. El contracte restringit és la gràcia de la pila, no una limitació a esquivar.
• Confondre LIFO amb FIFO: un truc mnemotècnic: pila de plats (l'últim a dalt surt primer), cua del cinema (el primer a arribar entra primer). Si dubtes, dibuixa tres elements entrant i pregunta't quin surt.
• Pensar que peek modifica la pila: peek és només lectura. Si després d'un peek la pila ha canviat, la implementació està malament (ho vigilarem a 03-03).
• Creure que la pila "recorda posicions": en una pila un element no té índex estable; la seva única propietat posicional és "quants elements té a sobre", i canvia amb cada operació.
• Consell: quan analitzis un problema, pregunta't: "l'últim que arriba és el primer que necessito processar?". Si la resposta és sí, gairebé segur que hi ha una pila esperant.

Sense implementar res (pots fer-ho amb paper i llapis), parteix d'una pila buida i aplica aquesta seqüència. Què retorna cada pop() i peek(), i què queda a la pila al final?

Per a cada situació, indica si el comportament natural és LIFO (pila) o no, i justifica-ho en una frase:

1. Els missatges d'un xat, mostrats en l'ordre en què van arribar.
2. La tecla "retrocés" (backspace) esborrant caràcters del que escrius.
3. La impressora de l'oficina processant documents enviats per diverses persones.
4. Sortir de diversos menús imbricats d'una aplicació prement "tornar" repetidament.

Escriu (només en pseudocodi o frases, sense implementar) quina operació del contracte de la pila faries servir per a cada necessitat de la interfície de TaskFlow:

1. Mostrar el botó "Desfer" en gris quan no hi hagi res a desfer.
2. Mostrar com a tooltip del botó el text de la propera acció a desfer.
3. Registrar que l'usuari acaba de completar la tasca 12.
4. Executar el desfer quan l'usuari prem el botó.
5. Mostrar "Historial: 8 accions" a la barra d'estat.

Solució 1:

Al final només queda "crear tasca 1". Observa que peek no va alterar res: el pop següent va retornar el mateix element.

Solució 2:

1. No és pila (és FIFO): els missatges es mostren en ordre d'arribada. És una cua (mòdul 4).
2. Pila: el retrocés esborra l'últim caràcter escrit; el text es comporta com una pila de caràcters.
3. No és pila (és FIFO): seria injust que l'últim document enviat s'imprimís primer. Cua d'impressió, literalment.
4. Pila: cada menú obert s'apila; "tornar" desapila el més recent. És el mateix patró que la pila de crides.

Solució 3:

1. esta_buida() → si retorna True, botó en gris.
2. peek() → consulta el cim sense retirar-lo; perfecta per a un tooltip.
3. push(accio) → registra l'acció de completar la tasca 12.
4. pop() → recupera l'acció més recent per revertir-la.
5. mida() → retorna el nombre d'accions emmagatzemades.

En aquesta lliçó has conegut la pila com a tipus abstracte de dades: una col·lecció LIFO on tot passa pel cim, amb un contracte de cinc operacions (push, pop, peek, esta_buida, mida) que promet cost O(1) en totes elles. Has vist que aquesta restricció no és una feblesa sinó la clau de la seva utilitat: modela amb exactitud el desfer d'un editor, les pestanyes tancades del navegador, la pila de crides de Python i —el que ens ocupa— el desfer de TaskFlow, on cada necessitat de la interfície encaixa amb una operació del contracte. També has comprovat que la pila hereta directament el que vas aprendre al mòdul 2: el cim és el cap d'una llista enllaçada amb les operacions cares prohibides. A la propera lliçó obrirem el capó de cada operació: veurem push, pop i peek pas a pas, amb traces de l'estat de la pila, decidirem què fer quan algú fa pop sobre una pila buida i començarem a practicar amb el desfer de TaskFlow fent servir la list de Python com a pila provisional.