El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
HOME Els meus cursos Finalitzats
◄ Anterior
◄

Implementació de Piles

Següent ►
►

Ha arribat el moment de complir la promesa: implementar la pila. I ho farem dues vegades. Al mòdul 1 vam distingir el TAD (el contracte: quines operacions i amb quin cost) de la implementació (el com), amb PilaAmbLlista i PilaAmbDiccionari com a exemple que un contracte admet diversos "coms". Avui aquesta idea deixa de ser teòrica: escriurem una classe Pila sobre la list de Python i una PilaEnllacada sobre els nodes del mòdul 2, comprovarem que totes dues compleixen exactament el mateix contracte i els mateixos invariants, les mesurarem amb timeit, i discutirem quina convé en cada situació. Com a cloenda, TaskFlow estrena el seu HistorialAccions: la pila que registra cada acció de l'usuari amb les dades necessàries per revertir-la. Aquesta lliçó és el cor del mòdul: en acabar-la no només tindràs una pila, sinó el criteri per triar entre implementacions equivalents, una habilitat que faràs servir amb cada estructura de la resta del curs.

Contingut

  1. El contracte que totes dues implementacions han de complir
  2. Implementació 1: Pila sobre list
  3. Implementació 2: PilaEnllacada sobre nodes
  4. Mateix contracte, mateixos tests
  5. Comparació de costos: amortitzat vs garantit, i memòria
  6. Mesurant amb timeit
  7. Quina triar i per què?
  8. TaskFlow: la classe HistorialAccions

El contracte que totes dues implementacions han de complir

Fixem per escrit el que hem acordat a les lliçons anteriors. Tota pila d'aquest curs ha d'oferir:

Operació Comportament Pila buida Cost exigit
push(e) Apila e al cim (no aplica) O(1)
pop() Retira i retorna el cim IndexError O(1)
peek() Retorna el cim sense retirar-lo IndexError O(1)
esta_buida() True/False True O(1)
mida() Nombre d'elements 0 O(1)

Qui faci servir la pila només pot dependre d'aquesta taula: mai dels detalls interns. Això ens dona llibertat total per implementar per dins com vulguem... sempre que la taula es compleixi.

Implementació 1: Pila sobre list

A la lliçó anterior vam fer servir una list "a pèl" com a pila provisional i en vam detectar el defecte: res no impedeix saltar-se el contracte (insert(0, ...), accés per índex...). La solució és l'encapsulació: guardar la llista com a atribut intern i exposar únicament les cinc operacions.

class Pila:
    """Pila (LIFO) implementada sobre la list de Python.

    El cim es el FINAL de la llista interna: append/pop del final son O(1).
    """

    def __init__(self):
        self._elements = []           # llista interna; el _ senyala "privat"

    def push(self, element):
        self._elements.append(element)        # apilar = append al final

    def pop(self):
        if not self._elements:
            raise IndexError("pop sobre una pila buida")
        return self._elements.pop()           # pop() sense argument = del final

    def peek(self):
        if not self._elements:
            raise IndexError("peek sobre una pila buida")
        return self._elements[-1]             # nomes lectura del cim

    def esta_buida(self):
        return len(self._elements) == 0

    def mida(self):
        return len(self._elements)

    def __len__(self):                        # permet len(pila)
        return len(self._elements)

    def __str__(self):                        # cim a l'esquerra, com les traces
        elements = ", ".join(repr(e) for e in reversed(self._elements))
        return f"Pila(cim -> [{elements}])"

Explicació detallada:

  • self._elements: el guionet baix inicial és la convenció de Python per a "atribut intern: no el toquis des de fora". Python no ho prohibeix tècnicament, però tot l'ecosistema respecta el senyal. Aquesta línia és l'encapsulació: l'usuari de Pila ja no veu una llista, veu una pila.
  • El cim és el final de la llista: decisió heretada de la lliçó anterior. append i pop() del final són les operacions barates de l'array dinàmic; amb insert(0)/pop(0) hauríem pagat O(n).
  • pop i peek llancen IndexError amb un missatge propi: la list ja llançaria IndexError, però comprovar-ho nosaltres ens permet donar un missatge clar ("pop sobre una pila buida" en comptes de "pop from empty list") i, sobretot, deixa la decisió de disseny escrita al codi, no delegada per accident.
  • len(pila) i print(pila): petits luxes pythònics, igual que vam fer amb __str__ a LlistaEnllacada. __str__ imprimeix el cim primer, perquè coincideixi amb les nostres taules de traça.

Provem-la amb accions de TaskFlow:

p = Pila()
p.push({"tipus": "crear", "tasca": 7})
p.push({"tipus": "canviar_prioritat", "tasca": 7})
print(p.peek())         # {'tipus': 'canviar_prioritat', 'tasca': 7}
print(p.mida())         # 2
print(p.pop()["tipus"]) # canviar_prioritat
print(p)                # Pila(cim -> [{'tipus': 'crear', 'tasca': 7}])

Implementació 2: PilaEnllacada sobre nodes

Ara la versió promesa al final del mòdul 2: una pila sobre nodes enllaçats, "en unes poques línies". La idea completa cap en una frase: el cim de la pila és el cap d'una llista enllaçada; push és inserir_al_principi i pop és esborrar el cap — les dues operacions O(1) que ja domines.

Reutilitzem el Node del mòdul 2 (dada + següent):

class Node:
    """El mateix Node del modul 2: una dada i la referencia al seguent."""
    def __init__(self, dada):
        self.dada = dada
        self.seguent = None


class PilaEnllacada:
    """Pila (LIFO) implementada sobre nodes enllacats.

    El cim es el CAP de la cadena de nodes: push/pop pel cap son O(1).
    """

    def __init__(self):
        self._cim = None              # referencia al node superior (o None)
        self._mida = 0                # comptador per a mida() en O(1)

    def push(self, element):
        nou = Node(element)           # 1. crear el node
        nou.seguent = self._cim       # 2. el nou apunta a l'antic cim
        self._cim = nou               # 3. el nou ES el cim
        self._mida += 1

    def pop(self):
        if self._cim is None:
            raise IndexError("pop sobre una pila buida")
        node = self._cim              # 1. guardar el node a retirar
        self._cim = node.seguent      # 2. el cim passa a ser el seguent
        self._mida -= 1
        return node.dada              # 3. retornar la dada (el node s'allibera sol)

    def peek(self):
        if self._cim is None:
            raise IndexError("peek sobre una pila buida")
        return self._cim.dada

    def esta_buida(self):
        return self._cim is None

    def mida(self):
        return self._mida

    def __len__(self):
        return self._mida

    def __str__(self):
        dades, actual = [], self._cim
        while actual is not None:
            dades.append(repr(actual.dada))
            actual = actual.seguent
        return f"PilaEnllacada(cim -> [{', '.join(dades)}])"

Anàlisi pas a pas de les dues operacions clau:

  • push és exactament l'inserir_al_principi de LlistaEnllacada, amb el cap rebatejat com a _cim. Tres passos, cap bucle: O(1) sempre, hi hagi 3 o 3 milions d'elements. L'ordre dels passos 2 i 3 importa: si fessis self._cim = nou abans d'enllaçar nou.seguent, perdries la referència a l'antiga pila (el mateix error d'ordre que vam veure en inserir en llistes enllaçades).
  • pop és esborrar el cap: apartar el node, avançar el cim, retornar la dada. També sense bucles: O(1) sempre. El node retirat deixa d'estar referenciat i el recol·lector d'escombraries de Python l'allibera.
  • _mida com a comptador: comptar recorrent seria O(n); mantenir el comptador a cada push/pop dona mida() en O(1). Mateixa tècnica que a LlistaEnllacada.
flowchart LR
    subgraph ABANS["Abans de push(D)"]
        direction LR
        cim1["_cim"] --> C1["C"] --> B1["B"] --> A1["A"] --> N1["None"]
    end
    subgraph DESPRES["Despres de push(D)"]
        direction LR
        cim2["_cim"] --> D2["D"] --> C2["C"] --> B2["B"] --> A2["A"] --> N2["None"]
    end
    ABANS -->|"nou.seguent = antic cim"| DESPRES

Mateix contracte, mateixos tests

La prova definitiva que TAD i implementació estan ben separats: un únic joc de comprovacions (els invariants de la lliçó 03-02) ha de passar amb qualsevol de les dues classes, sense canviar ni una línia:

def provar_contracte(ClassePila):
    """Verifica els invariants del TAD sobre qualsevol implementacio."""
    p = ClassePila()
    assert p.esta_buida() and p.mida() == 0          # invariant 1

    p.push("a")
    assert p.peek() == "a" and p.mida() == 1         # invariant 2

    p.push("b")
    assert p.pop() == "b" and p.peek() == "a"        # invariant 3: pop desfa push

    abans = p.mida()
    p.peek()
    assert p.mida() == abans                         # invariant 4: peek no modifica

    p.pop()
    try:
        p.pop()                                      # pila buida: ha de fallar
        assert False, "hauria d'haver llancat IndexError"
    except IndexError:
        pass
    print(f"{ClassePila.__name__}: contracte OK")

provar_contracte(Pila)            # Pila: contracte OK
provar_contracte(PilaEnllacada)   # PilaEnllacada: contracte OK

La funció rep la classe com a paràmetre i funciona amb totes dues. Per al codi client (i per a TaskFlow) les dues piles són intercanviables: això és programar contra el contracte.

Comparació de costos: amortitzat vs garantit, i memòria

Si totes dues compleixen el contracte, en què es diferencien? En els matisos de rendiment i memòria:

Aspecte Pila (sobre list) PilaEnllacada (sobre nodes)
push O(1) amortitzat O(1) garantit
pop / peek O(1) O(1)
Memòria per element Compacta: referències contigües a l'array Més gran: cada dada paga un objecte Node extra (dada + següent)
Localitat de memòria Bona (contigüitat → memòria cau contenta) Pitjor (nodes dispersos per la memòria)
En buidar-se molt L'array pot conservar capacitat sobrant Allibera cada node en fer pop
Línies de codi Menys (delega en list) Més (gestiona nodes i comptador)

El matís nou és amortitzat vs garantit, i mereix explicació:

  • La list de Python és un array dinàmic (mòdul 1): quan s'omple, reserva un bloc més gran i copia tots els elements. Aquell append concret costa O(n).
  • Com que la capacitat creix de manera geomètrica (sempre un percentatge més), aquestes còpies són cada cop més rares. Repartit ("amortitzat") entre tots els append, el cost mitjà per operació és O(1). Però un push individual, de tant en tant, és lent.
  • PilaEnllacada no copia mai res: cada push crea un node i mou dues referències. O(1) en el pitjor cas, sense excepcions.

Quan importa aquesta diferència? Gairebé mai en aplicacions normals... i moltíssim en sistemes amb requisits de latència estables (àudio en temps real, sistemes encastats), on un "pic" ocasional és inacceptable. És la primera vegada al curs que dues opcions correctes es distingeixen no pel cost mitjà sinó per la seva distribució: apunta't el concepte, reapareixerà.

Mesurant amb timeit

Comprovem les afirmacions amb dades, com vam fer al mòdul 1. Mesurem apilar i desapilar 100 000 elements amb cada implementació:

import timeit

def exercitar(ClassePila, n=100_000):
    p = ClassePila()
    for i in range(n):
        p.push(i)
    while not p.esta_buida():
        p.pop()

for Classe in (Pila, PilaEnllacada):
    t = timeit.timeit(lambda: exercitar(Classe), number=10)
    print(f"{Classe.__name__:14}: {t:.3f} s (10 rondes de 100k push+pop)")

Resultats orientatius (els números exactes depenen de la teva màquina; les proporcions, no):

Pila          : 0.35 s (10 rondes de 100k push+pop)
PilaEnllacada : 1.60 s (10 rondes de 100k push+pop)

Dues lectures importants, en aparença contradictòries:

  1. Totes dues escalen igual: duplica n i veuràs que tots dos temps es dupliquen aproximadament — comportament lineal per a n operacions, és a dir, O(1) per operació. La teoria es confirma en totes dues.
  2. La constant importa: Pila és diverses vegades més ràpida. No havíem dit que PilaEnllacada tenia millor garantia? Sí: millor pitjor cas, però pitjor constant, perquè cada push crea un objecte Node a Python (car) mentre que append està implementat en C sobre memòria contigua. Big O parla de creixement, no de velocitat absoluta: dos O(1) poden diferir en un factor 5.

Aquesta és una lliçó general valuosíssima: mesurar complementa raonar. L'anàlisi asimptòtica et diu què escala; timeit et diu quant costa de debò a la teva plataforma.

Quina triar i per què?

Criteri pràctic per a Python:

  • Per defecte: Pila sobre list. Menys codi, menys memòria, més ràpida a la pràctica, i delega en una peça ultraoptimitzada del llenguatge. És l'elecció correcta per a TaskFlow i per al 95 % dels casos.
  • PilaEnllacada quan... necessitis O(1) garantit per operació (latència estable), o quan la pila comparteixi nodes amb altres estructures enllaçades. I, sobretot, és la implementació que veuràs en llibres i entrevistes, i la que es fa servir en llenguatges sense array dinàmic incorporat: entendre-la no és opcional.
  • El punt clau: com que totes dues compleixen el contracte, canviar de l'una a l'altra no toca ni una línia del codi client. Triar implementació és una decisió local i reversible; triar malament el TAD, en canvi, es paga a tot el programa.

TaskFlow: la classe HistorialAccions

Tanquem posant la pila a treballar. L'historial de TaskFlow registra accions: diccionaris amb el tipus d'acció, l'id de la tasca afectada i les dades prèvies necessàries per revertir-la:

{"tipus": "canviar_estat", "tasca": 7, "dades_previes": {"estat": "pendent"}}

HistorialAccions embolcalla una Pila i ofereix vocabulari del domini (registrar/desfer) en comptes de vocabulari d'estructura (push/pop):

class HistorialAccions:
    """Historial de desfer de TaskFlow: una pila d'accions revertibles."""

    def __init__(self):
        self._pila = Pila()               # composicio: conte una Pila

    def registrar(self, tipus, tasca_id, dades_previes):
        accio = {"tipus": tipus, "tasca": tasca_id, "dades_previes": dades_previes}
        self._pila.push(accio)

    def desfer(self):
        """Retira i retorna l'ultima accio registrada (per revertir-la)."""
        if self._pila.esta_buida():
            return None                   # aqui None SI que es correcte: "no hi havia res"
        return self._pila.pop()

    def propera_a_desfer(self):
        """Text per a la interficie, p. ex. el tooltip del boto Desfer."""
        if self._pila.esta_buida():
            return "Res a desfer"
        accio = self._pila.peek()
        return f"Desfer: {accio['tipus']} (tasca {accio['tasca']})"

    def hi_ha_accions(self):
        return not self._pila.esta_buida()

    def total(self):
        return self._pila.mida()

I una sessió d'ús sobre la nostra tasca de sempre:

tasca = {"id": 7, "titol": "Revisar el pressupost", "prioritat": 2, "estat": "pendent"}
historial = HistorialAccions()

# L'usuari canvia la prioritat a 1: guardem el valor PREVI abans de tocar res
historial.registrar("canviar_prioritat", 7, {"prioritat": tasca["prioritat"]})
tasca["prioritat"] = 1

# L'usuari la posa en curs
historial.registrar("canviar_estat", 7, {"estat": tasca["estat"]})
tasca["estat"] = "en curs"

print(historial.propera_a_desfer())  # Desfer: canviar_estat (tasca 7)

# Prem Desfer: recuperem l'accio i restaurem les dades previes
accio = historial.desfer()
tasca.update(accio["dades_previes"])
print(tasca["estat"])                # pendent
print(historial.total())             # 1

Detalls de disseny que convé subratllar:

  • dades_previes es captura abans de modificar la tasca: és la informació mínima per revertir. Registrar després ja seria tard: el valor antic s'hauria perdut.
  • Revertir és tasca.update(accio["dades_previes"]): com que les dades prèvies són un dict amb els camps antics, restaurar-los és una línia.
  • desfer retorna None si no hi ha res: contradiu la lliçó anterior? No: la pila continua llançant IndexError; és HistorialAccions, la capa de domini, qui decideix que "desfer sense historial" no és un error de programació sinó un cas normal d'interfície. L'excepció viu a l'estructura; la tolerància, a l'aplicació.
  • Fixa't que encara no hi ha "refer": si l'usuari desfà i se'n penedeix, no hi ha marxa enrere. Resoldre-ho exigeix una segona pila cooperant amb aquesta — és la primera aplicació de la propera lliçó.

Errors Comuns i Consells

  • Trencar l'encapsulació: accedir a pila._elements o pila._cim des de fora "perquè és més ràpid". Acabes de convertir la teva pila en una llista sense contracte; el dia que canviïs la implementació, tot aquell codi mor.
  • Invertir els passos del push enllaçat: assignar self._cim = nou abans de nou.seguent = self._cim perd tota la pila anterior. Si la teva PilaEnllacada "només recorda l'últim element", és això.
  • Oblidar el comptador _mida: sense ell, o mida() recorre la pila (O(n), contracte trencat) o retorna dades incorrectes. Cada push suma un, cada pop amb èxit resta un (no restis abans de comprovar si és buida).
  • Registrar l'acció a l'historial després de modificar la tasca: dades_previes capturaria ja el valor nou i el desfer no desfaria res. Primer capturar, després modificar.
  • Comparar implementacions sense mesurar: "l'enllaçada serà més ràpida perquè és O(1) garantit" — acabes de veure que no. Raona amb Big O, decideix amb timeit.
  • Consell: escriu sempre una funció tipus provar_contracte quan tinguis dues implementacions del mateix. És la xarxa de seguretat que et permet canviar d'implementació sense por.

Exercicis

Exercici 1: PilaAcotada

TaskFlow no vol un historial infinit. Crea una classe PilaAcotada que rebi capacitat al constructor i es comporti com Pila, llevat que push sobre una pila plena llanci OverflowError("pila plena"). Afegeix-hi un mètode esta_plena(). Fes-la heretant de Pila (pista: super().__init__() i super().push(...)).

Exercici 2: __iter__ per a PilaEnllacada

Afegeix a PilaEnllacada un mètode __iter__ (generador, com el de LlistaEnllacada del mòdul 2) que recorri les dades de cim a fons sense modificar la pila. Amb ell, list(pila) ha de retornar els elements en ordre de desapilat. Pregunta extra: per què "recórrer una pila" és, en rigor, sortir-se del TAD, i per què tot i això és útil a la pràctica?

Exercici 3: revertir segons el tipus d'acció

Escriu la funció revertir(accio, tasques) per a TaskFlow, on tasques és un dict de tasques per id (com el tauler del mòdul 2) i accio és un dict de l'historial. Ha de gestionar tres tipus: "canviar_estat" i "canviar_prioritat" (restaurar dades_previes sobre la tasca) i "crear" (revertir una creació = eliminar la tasca; en aquest cas dades_previes és {}).

Solucions

Solució 1:

class PilaAcotada(Pila):
    def __init__(self, capacitat):
        super().__init__()                 # inicialitza la llista interna de Pila
        self._capacitat = capacitat

    def esta_plena(self):
        return self.mida() >= self._capacitat

    def push(self, element):
        if self.esta_plena():
            raise OverflowError("pila plena")
        super().push(element)              # delega l'apilat real en Pila

L'herència ho reutilitza tot (pop, peek, esta_buida, mida, __str__); només push hi afegeix la guarda. Prova: amb capacitat=2, el tercer push llança OverflowError. (A 03-05 veurem una altra política més útil per a un historial: en comptes de fallar, descartar l'acció més antiga.)

Solució 2:

class PilaEnllacada(PilaEnllacada):        # o afegeix el metode a la classe original
    def __iter__(self):
        actual = self._cim
        while actual is not None:
            yield actual.dada              # produeix dades de cim a fons
            actual = actual.seguent

És el mateix patró generador de LlistaEnllacada.__iter__: un cursor actual que avança per seguent. list(pila) retorna [cim, ..., fons], l'ordre exacte en què sortirien amb pop, però sense treure'ls. Respecte a la pregunta extra: el contracte de la pila només dona accés al cim, així que iterar és "fer trampa" sobre el TAD pur; a la pràctica s'accepta com a operació d'inspecció (depurar, mostrar l'historial en pantalla) perquè no modifica l'estat. La línia vermella és modificar durant la iteració.

Solució 3:

def revertir(accio, tasques):
    tasca_id = accio["tasca"]
    if accio["tipus"] == "crear":
        # Desfer una creacio es eliminar la tasca del tauler
        del tasques[tasca_id]
    elif accio["tipus"] in ("canviar_estat", "canviar_prioritat"):
        # Restaurar els camps previs sobre la tasca existent
        tasques[tasca_id].update(accio["dades_previes"])
    else:
        raise ValueError(f"tipus d'accio desconegut: {accio['tipus']}")

Prova ràpida:

tasques = {7: {"id": 7, "titol": "Revisar el pressupost", "prioritat": 1, "estat": "en curs"}}
accio = {"tipus": "canviar_estat", "tasca": 7, "dades_previes": {"estat": "pendent"}}
revertir(accio, tasques)
print(tasques[7]["estat"])   # pendent

L'else amb ValueError és deliberat: si demà TaskFlow afegeix un tipus d'acció i n'oblidem la reversió, millor un error sorollós que un desfer que no desfà.

Conclusió

Ja tens dues piles completes i verificades: Pila, que encapsula una list amb el cim al final, i PilaEnllacada, que reencarna l'inserir_al_principi/esborrar-cap del mòdul 2 amb el cap rebatejat com a cim. Has comprovat amb un mateix joc de tests que totes dues compleixen un contracte idèntic —l'essència del TAD— i has après a distingir-les allà on de debò difereixen: O(1) amortitzat davant d'O(1) garantit, consum de memòria, i constants reals mesurades amb timeit (amb la moralitat que dos O(1) poden diferir en un factor 5). TaskFlow, per la seva banda, ja registra i desfà accions amb HistorialAccions i el seu patró "captura les dades prèvies, després modifica". Però li falta una cosa que tot usuari espera: penedir-se del desfer. A la propera lliçó construirem el desfer/refer complet amb dues piles cooperant, i veurem que les piles també validen parèntesis, avaluen expressions i sostenen cada crida a funció que executa Python.

◄ Anterior
◄
Següent ►
►
El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
© Copyright 2026. Tots els drets reservats