A la lliçó anterior vas conèixer el contracte del TAD pila: push, pop, peek, esta_buida i mida, totes amb cost O(1). Ara obrirem cada operació i la veurem funcionar pas a pas, amb traces de l'estat de la pila després de cada moviment, exactament com faries en depurar. A més prendrem una decisió de disseny que tot autor d'estructures ha d'afrontar (què fer quan algú fa pop sobre una pila buida?), formularem els invariants que tota pila ha de complir, i aplicarem tot això al desfer de TaskFlow. Per practicar sense esperar la implementació completa (lliçó 03-03), farem servir la list de Python com a pila provisional. Dominar la mecànica fina d'aquestes operacions és el que et permetrà després implementar-les i, sobretot, raonar amb seguretat sobre qualsevol algorisme que faci servir piles.

1. push: apilar pas a pas
2. pop: desapilar pas a pas
3. peek: mirar sense tocar
4. esta_buida i mida: les consultes d'estat
5. El cas de la pila buida: excepció vs None
6. Invariants del TAD pila
7. Seqüències d'operacions: el desfer de TaskFlow
8. Minipràctica guiada: list com a pila provisional

push(element) col·loca element al cim. És l'única manera d'entrar en una pila. Vegem una traça partint d'una pila buida, apilant accions de l'historial de TaskFlow (dibuixem la pila en vertical, amb el cim a dalt, tal com creix de debò):

Punts clau:

• Cada push tapa l'element anterior: crear tasca 7 continua allà, però ja no és accessible fins que es retirin els de sobre.
• push mai no falla per estat de la pila: una pila (conceptual) no té límit de capacitat. (Existeixen piles acotades —ho veurem en un exercici de 03-05 amb el límit d'historial— però no formen part del contracte base.)
• push no retorna res: el seu efecte és el canvi d'estat.

En diagrama, els dos primers passos:

pop() fa dues coses en una: retira l'element del cim i el retorna. Continuem la traça anterior (la pila tenia 3 elements):

Observa dues coses:

• Els elements surten en ordre invers al d'entrada: van entrar 7→prioritat→en curs i van sortir en curs→prioritat→7. Aquesta és l'essència LIFO, i és exactament l'ordre que necessita un desfer.
• El quart pop() és un problema: la pila és buida i no hi ha res a retornar. Aquest "?" mereix la seva pròpia secció (la número 5).

Un patró habitual és buidar una pila processant cada element:

Aquest bucle processa els elements en ordre invers al d'inserció. Memoritza el patró: el farem servir una vegada i una altra (desfer-ho tot, invertir seqüències, avaluar expressions...).

peek() retorna l'element del cim sense retirar-lo. La pila queda exactament igual:

Per a què serveix si pop ja retorna el cim? Per decidir abans d'actuar. Dos usos típics a TaskFlow:

• La interfície vol mostrar "Desfer: canviar prioritat" al botó. Necessita llegir la propera acció sense desfer-la: peek.
• Un algorisme vol desapilar només si el cim compleix una condició (ho veuràs a la conversió d'expressions de 03-04): primer peek, es comprova la condició, i només llavors pop.

Regla d'or: si després de cridar una operació de consulta la pila ha canviat, aquesta operació està mal implementada. peek, esta_buida i mida són observadores; push i pop són modificadores.

• esta_buida() retorna True si mida() == 0. És la guarda natural abans de qualsevol pop o peek, i la condició d'aturada del bucle de buidatge.
• mida() retorna el nombre d'elements. Perquè sigui O(1), la implementació mantindrà un comptador que s'incrementa a cada push i es decrementa a cada pop — la mateixa tècnica de l'atribut mida de LlistaEnllacada al mòdul 2, on comptar recorrent hauria costat O(n).

Encara que semblin trivials, aquestes dues operacions són les que fan segur l'ús de la pila: gairebé tot bug amb piles és un pop sense comprovar esta_buida abans.

Què ha de fer pop() (o peek()) sobre una pila buida? És una decisió de disseny, i les dues opcions raonables tenen conseqüències diferents:

En aquest curs adoptem l'excepció, per dos motius:

1. Coherència amb Python: [].pop() llança IndexError. La nostra pila es comportarà com la resta del llenguatge.
2. Fallar aviat i fort: un None inesperat pot viatjar per mig programa abans de trencar alguna cosa, i llavors el traceback no apunta a la causa. Una excepció al pop culpable apunta exactament a l'error.

El cridador té llavors dos estils correctes, tots dos vàlids:

L'important no és quin estil triïs, sinó que la decisió "excepció, no None" quedi escrita al contracte i tots els usuaris de la pila puguin confiar-hi.

Un invariant és una propietat que es compleix sempre, abans i després de cada operació (ja vam raonar així al mòdul 2, quan manteníem cap, cua i mida coherents després de cada inserció). Els invariants de la pila són el "control de qualitat" de qualsevol implementació:

1. mida() >= 0 en tot moment; i esta_buida() equival a mida() == 0.
2. Després de push(x): peek() retorna x, i mida() ha crescut exactament en 1.
3. pop() després de push(x) (sense operacions intermèdies) retorna x i deixa la pila exactament com estava abans del push. És a dir: pop desfà push.
4. peek() no modifica res: mida() i el contingut són idèntics abans i després.
5. Ordre LIFO global: si s'apilen n elements i després es desapilen n, surten en ordre exactament invers.

Aquests invariants són directament traduïbles a tests. Quan implementem les dues piles de la lliçó 03-03, qualsevol d'elles ha de passar exactament les mateixes comprovacions: aquesta és la prova pràctica que el TAD és independent de la implementació.

Juguem una sessió realista de TaskFlow, encara amb pseudocodi del contracte. Cada acció de l'usuari es registra amb push; cada pulsació de Desfer executa pop i reverteix. Seguim la tasca {"id": 7, "titol": "Revisar el pressupost", "prioritat": 2, "estat": "pendent"}:

Dues observacions importants:

• Al pas 4 es va desfer l'estat i al 5 l'usuari va fer una cosa nova. L'acció desfeta no "torna": la pila només registra el que és vigent. (I si la volgués refer? Necessitaríem una segona pila; aquesta és exactament la construcció desfer/refer de la lliçó 03-04.)
• Cada acció apilada porta la informació necessària per revertir-la (el valor previ: 2→1, pendent→en curs). A 03-03 formalitzarem això amb diccionaris {"tipus": ..., "tasca": ..., "dades_previes": ...}.

Encara no tenim la nostra classe Pila (arriba a 03-03), però la list de Python pot exercir de pila provisional, perquè les seves operacions pel final són les adequades:

• llista.append(x) → fa de push → O(1) amortitzat.
• llista.pop() (sense argument) → fa de pop → O(1).
• llista[-1] → fa de peek → O(1).
• len(llista) == 0 → fa d'esta_buida → O(1).

Per què pel FINAL i no pel principi? Recorda la trampa del mòdul 1: insert(0, x) i pop(0) són O(n), perquè una list és un array dinàmic i tocar el principi obliga a desplaçar tots els elements. El cim de la nostra pila provisional ha de ser el final de la llista, on l'array treballa en O(1). Una pila feta amb insert(0)/pop(0) "funciona" però degrada totes les operacions a O(n): trencaria la taula de costos del contracte.

Obre un intèrpret i reprodueix la sessió de TaskFlow de la secció anterior:

Explicació línia a línia:

• historial = [] crea la pila buida. La llista buida és la nostra pila buida.
• Els tres append apilen en ordre; després d'ells, el cim (final de la llista) és l'acció més recent.
• historial[-1] llegeix el cim sense retirar-lo: és el nostre peek. Compte: sobre una llista buida, [-1] també llança IndexError, coherent amb la nostra decisió de disseny.
• historial.pop() sense argument retira del final: LIFO garantit i O(1).
• El bucle while és el patró de buidatge: imprimeix les accions en ordre invers al que van passar, que és justament l'ordre correcte d'un "desfer-ho tot".
• L'últim pop() sobre la llista buida llança IndexError: Python ja implementa l'estratègia d'excepció que hem triat.

Aquesta pila provisional és totalment funcional, però té un defecte: no protegeix el contracte. Res no impedeix que un altre programador faci historial.insert(0, x) o historial[3] i trenqui la disciplina LIFO. Encapsular la llista dins d'una classe que només exposi les cinc operacions és precisament la feina de la propera lliçó.

• Fer pop sense comprovar abans (o sense try/except): el clàssic IndexError en producció. Tota crida a pop/peek ha d'estar protegida per esta_buida() o per un except IndexError.
• Fer servir pop(0) o insert(0, x) sobre la list-pila: funciona, però converteix O(1) en O(n). El cim viu al final de la llista. Si dubtes, torna a la taula de costos de list del mòdul 1.
• Fer servir pop quan només volies consultar: si després de "mirar" el cim el necessites de nou, has destruït informació. Consulta = peek (llista[-1]); extracció = pop.
• Retornar None en pila buida "per simplificar": acabes amb if resultat is not None escampats per tot el codi i bugs quan None és un valor vàlid. Excepció i punt.
• Oblidar que pop retorna l'element: escriure pila.pop() i després intentar llegir el cim amb peek per saber "què s'ha desapilat" — ja és tard, era el valor de retorn del mateix pop.
• Consell: quan escriguis o depuris seqüències d'operacions, dibuixa la traça en una taula com les d'aquesta lliçó (operació → retorna → estat). Dos minuts de taula estalvien vint de depurador.

Partint d'una pila buida, construeix la taula de traça (operació, valor retornat, estat de la pila, mida) d'aquesta seqüència:

Indica en quin pas (si n'hi ha) es llança IndexError segons la nostra decisió de disseny.

Fent servir una list com a pila provisional, escriu una funció desfer_tot(historial) que rebi la pila d'accions (llista de cadenes) i retorni una llista amb els missatges "Desfent: <accio>" en l'ordre correcte de desfer, deixant la pila buida. La funció no ha de fallar mai, ni tan sols si rep la pila ja buida. Escriu-ne dues versions: una amb estil LBYL (comprovar abans) i una altra amb estil EAFP (try/except).

Un company ha escrit aquestes "operacions de pila" sobre list. Assenyala tots els errors respecte al contracte i als invariants d'aquesta lliçó, i corregeix-los:

Solució 1:

El pas 11 llança IndexError: la pila és buida i hem triat excepció, no None.

Solució 2:

Totes dues retornen els missatges en ordre invers a la inserció (l'ordre correcte de desfer) i deixen historial buida. Amb una pila ja buida, el while de la primera no arriba a executar-se i el try de la segona trenca el bucle a la primera volta: cap de les dues no falla.

Solució 3: hi ha quatre errors.

1. push fa servir insert(0, ...): apila pel principi de la llista → O(n) per desplaçament de l'array. Trenca el cost del contracte.
2. pop fa servir pop(0): mateix problema, O(n). (Curiosament el conjunt "inserir i esborrar pel principi" manté l'ordre LIFO, així que funciona... lentíssim. El bug de rendiment és el més traïdor perquè els tests de correcció no l'atrapen.)
3. pop retorna None en pila buida: contradiu la decisió de disseny; ha de deixar que l'excepció salti (o llançar-la explícitament).
4. peek fa pop(0): retira l'element! Viola l'invariant 4 (peek no modifica). Ha de ser només lectura.

Versió corregida:

Ja domines la mecànica completa del TAD pila: push tapa el cim anterior, pop retira i retorna en un sol gest, peek observa sense modificar, i esta_buida/mida fan segura tota la resta. Has pres una decisió de disseny raonada (excepció IndexError en pila buida, com fa la mateixa list de Python), has formulat els invariants que qualsevol implementació haurà de complir, i has traçat sessions reals del desfer de TaskFlow operació a operació. A més ja tens una pila provisional funcionant amb list —sempre pel final, mai pel principi— encara que li falta l'essencial: una frontera que impedeixi saltar-se el contracte. A la propera lliçó construirem aquesta frontera dues vegades: una classe Pila sobre list i una PilaEnllacada sobre els nodes del mòdul 2, mesurarem totes dues amb timeit i muntarem l'HistorialAccions real de TaskFlow.