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

Exercicis amb Piles

Següent ►
►

Aquesta lliçó tanca el mòdul de piles i és íntegrament pràctica: sis exercicis progressius, sense teoria nova, que consoliden tot el que has après —el contracte del TAD (03-01 i 03-02), les implementacions Pila i PilaEnllacada (03-03) i els patrons d'aplicació (03-04)— i diversos d'ells amplien directament TaskFlow. Treballa cada exercici de debò abans de mirar la solució: intenta primer la traça en paper (com a 03-02), després el codi, i només llavors compara. Les solucions estan completes i comentades, amb el raonament que hi porta, perquè l'objectiu no és "que et surti" sinó que sàpigues per què surt. En tots els exercicis pots fer servir la classe Pila de la lliçó 03-03 (o una list amb append/pop, ja saps per què pel final).

Contingut

  1. Exercici 1: invertir una cadena (i una llista de tasques)
  2. Exercici 2: processar retrocessos de teclat
  3. Exercici 3: validar seqüències de push/pop
  4. Exercici 4: min-stack — el mínim en O(1)
  5. Exercici 5: historial de desfer amb límit
  6. Exercici 6: de recursió a iteració amb pila explícita

Exercici 1: invertir una cadena (i una llista de tasques)

Nivell: bàsic. El "hola món" de les piles: com que els elements surten en ordre invers al que entren, apilar-ho tot i desapilar-ho inverteix qualsevol seqüència.

  1. Escriu invertir_cadena(text) que retorni el text invertit fent servir una pila (sense [::-1] ni reversed, és clar: l'objectiu és el patró).
  2. Escriu invertir_tasques(tasques) que rebi una llista de dicts de tasca i retorni una llista nova en ordre invers — TaskFlow la farà servir per mostrar "les últimes tasques creades primer".
  3. Pregunta d'anàlisi: cost en temps i en espai? I si en comptes d'apilar/desapilar fessis dues passades amb pop(0)?

Solució

def invertir_cadena(text):
    pila = Pila()
    for caracter in text:         # fase 1: apilar-ho tot (entra en ordre)
        pila.push(caracter)
    resultat = []
    while not pila.esta_buida():  # fase 2: desapilar-ho tot (surt invertit)
        resultat.append(pila.pop())
    return "".join(resultat)

def invertir_tasques(tasques):
    pila = Pila()
    for tasca in tasques:
        pila.push(tasca)
    invertides = []
    while not pila.esta_buida():
        invertides.append(pila.pop())
    return invertides

print(invertir_cadena("TaskFlow"))     # wolFksaT
print(invertir_tasques([{"id": 1, "titol": "A", "prioritat": 2, "estat": "pendent"},
                        {"id": 2, "titol": "B", "prioritat": 1, "estat": "pendent"}]))
# [{'id': 2, ...}, {'id': 1, ...}]

Comentaris:

  • El patró és el doble bolcat: tot dins, tot fora. Una passada de push (n operacions O(1)) més una de pop (n més): O(n) temps, O(n) espai (la pila arriba a contenir els n elements).
  • Nota l'eco de 03-04 (exercici 1): una inversió canvia l'ordre; dues inversions el restauren. Per això desfer+refer amb dues piles retorna l'ordre cronològic.
  • Sobre la pregunta 3: recórrer amb pop(0) sobre una list seria O(n) per element → O(n²) total. És la trampa insert(0)/pop(0) del mòdul 1 una altra vegada; amb 100 000 tasques, la diferència entre mil·lisegons i minuts.

Exercici 2: processar retrocessos de teclat

Nivell: bàsic. Al camp "títol de la tasca" de TaskFlow arriba la seqüència de tecles premudes, on # representa la tecla de retrocés (esborra l'últim caràcter escrit, si n'hi ha). Escriu text_final(tecles) que retorni el text resultant.

Exemples: text_final("Revisar#####dactar") → "Redactar"; text_final("##Hola#") → "Hol" (retrocessos sobre text buit no fan res).

Solució

def text_final(tecles):
    pila = Pila()
    for tecla in tecles:
        if tecla == "#":
            if not pila.esta_buida():   # retroces sense text: s'ignora
                pila.pop()              # esborra l'ultim caracter escrit
        else:
            pila.push(tecla)
    # La pila te el text de cim a fons = invertit: li donem la volta
    caracters = []
    while not pila.esta_buida():
        caracters.append(pila.pop())
    return "".join(reversed(caracters))

print(text_final("Revisar#####dactar"))  # Redactar
print(text_final("##Hola#"))          # Hol

Comentaris:

  • "Esborrar l'últim escrit" és la definició operativa de pop: el text en edició és una pila de caràcters (ja ho vas identificar a l'exercici 2 de 03-01).
  • La guarda esta_buida() abans del pop és obligatòria: sense ella, "##Hola#" llançaria IndexError al primer #. És l'error comú número u de 03-02 en estat pur.
  • Al final la pila conté el text invertit (el cim és l'últim caràcter): cal bolcar i reinvertir. Cost total O(n).

Exercici 3: validar seqüències de push/pop

Nivell: mitjà. Et donen dues llistes: entrades (l'ordre en què es van apilar n elements diferents) i sortides (un ordre de desapilat que algú afirma haver observat). Escriu sequencia_valida(entrades, sortides) que retorni True si aquesta seqüència de sortida és possible en una pila, intercalant pushes i pops com es vulgui.

Exemples amb entrades = [1, 2, 3, 4]:

  • sortides = [2, 1, 4, 3] → True (push 1, push 2, pop 2, pop 1, push 3, push 4, pop 4, pop 3).
  • sortides = [3, 1, 2] amb entrades = [1, 2, 3] → False: per treure el 3 primer, l'1 i el 2 queden apilats amb el 2 a sobre; és impossible que surti l'1 abans que el 2.

Pista: simula. Apila les entrades en ordre i, després de cada push, desapila amb avidesa mentre el cim coincideixi amb el següent element esperat de sortides.

Solució

def sequencia_valida(entrades, sortides):
    if len(entrades) != len(sortides):
        return False
    pila = Pila()
    i = 0                                  # index del proxim pop esperat
    for element in entrades:               # simulem els push en el seu ordre
        pila.push(element)
        # Desapilat avid: mentre el cim sigui just el que s'espera, pop
        while not pila.esta_buida() and i < len(sortides) and pila.peek() == sortides[i]:
            pila.pop()
            i += 1
    return pila.esta_buida()               # tot va sortir en l'ordre demanat

print(sequencia_valida([1, 2, 3, 4], [2, 1, 4, 3]))  # True
print(sequencia_valida([1, 2, 3], [3, 1, 2]))        # False
print(sequencia_valida([1, 2, 3], [1, 2, 3]))        # True (pop despres de cada push)
print(sequencia_valida([1, 2, 3], [3, 2, 1]))        # True (tots els push, despres pops)

Comentaris:

  • La idea profunda: no cal raonar sobre totes les intercalacions possibles; n'hi ha prou de simular l'única estratègia sensata (desapilar tan bon punt el cim coincideix amb l'esperat). Si aquesta estratègia no aconsegueix la seqüència, cap no ho farà: retardar un pop possible només enterra més l'element.
  • peek decideix i pop executa: el patró "mirar abans d'actuar" de 03-02 i del shunting-yard de 03-04.
  • En acabar, si la pila no ha quedat buida és que algun element no va poder sortir quan li tocava: False (ho retorna esta_buida() directament).
  • Cost O(n): cada element s'apila una vegada i es desapila com a màxim una vegada, encara que hi hagi un while dins del for (compta operacions totals, no imbricació: un raonament de cost amortitzat com el de 03-03).

Exercici 4: min-stack — el mínim en O(1)

Nivell: mitjà-alt. TaskFlow vol mostrar en tot moment "la tasca més prioritària de l'historial" (recorda: prioritat 1 = màxima, així que busquem el valor mínim). Recórrer l'historial a cada consulta seria O(n). Dissenya PilaAmbMinim amb el contracte habitual (push, pop, peek, esta_buida, mida) més una operació minim() que retorni el valor mínim apilat, tot en O(1).

Pista: una pila auxiliar que, en paral·lel a la principal, guardi "el mínim vigent fins a aquest nivell". Pensa què s'ha d'apilar a l'auxiliar a cada push i què passa a cada pop.

Solució

class PilaAmbMinim:
    """Pila amb minim() en O(1) mitjancant una pila auxiliar de minims vigents."""

    def __init__(self):
        self._pila = Pila()        # les dades reals
        self._minims = Pila()      # minims vigents, en paral·lel nivell a nivell

    def push(self, valor):
        self._pila.push(valor)
        if self._minims.esta_buida():
            self._minims.push(valor)
        else:
            # El minim vigent despres d'aquest push: el menor entre el nou i l'anterior
            self._minims.push(min(valor, self._minims.peek()))

    def pop(self):
        self._minims.pop()         # les dues piles creixen i minven alhora
        return self._pila.pop()

    def peek(self):
        return self._pila.peek()

    def minim(self):
        return self._minims.peek()    # O(1): el minim vigent es al cim

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

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


p = PilaAmbMinim()
for prioritat in [3, 1, 2]:
    p.push(prioritat)
print(p.minim())    # 1
p.pop()             # surt el 2
print(p.minim())    # 1  (l'1 continua dins)
p.pop()             # surt l'1
print(p.minim())    # 3  (el minim anterior "reviu" tot sol!)

Comentaris:

  • El truc és l'invariant paral·lel: _minims té sempre la mateixa mida que _pila, i el seu cim és "el mínim de tot el que hi ha ara a _pila". Cada push apila a _minims el min entre el valor nou i el mínim anterior; cada pop desapila de totes dues.
  • La màgia és a l'últim print: en desapilar l'1, el mínim torna a ser 3 sense recalcular res, perquè la pila auxiliar recorda el mínim de cada nivell històric. Un comptador simple ("el mínim és 1") no podria: en treure l'1 no sabria quin era l'anterior.
  • Cost: totes les operacions O(1); espai O(n) extra per la pila auxiliar. És un intercanvi espai-per-temps, la moneda de canvi més habitual en estructures de dades.
  • Traça de les dues piles per a push de 3, 1, 2 (cim a dalt):
_pila _minims
2 1
1 1
3 3
  • Connexió amb TaskFlow: si s'apilen accions i a _minims es guarda la prioritat mínima vista, minim() respon "la tasca més prioritària tocada en aquesta sessió" a l'instant. (Per extreure sempre la tasca més prioritària del tauler —no només consultar-la— l'estructura adequada és la cua de prioritat, que arriba al mòdul 4.)

Exercici 5: historial de desfer amb límit

Nivell: mitjà-alt. L'historial infinit de GestorDesferRefer (03-04) gasta memòria sense fre. TaskFlow decideix: "es conserven com a màxim les últimes k accions desfables". Compte: a diferència de la PilaAcotada de 03-03 (que rebutjava el push), aquí en superar el límit s'ha de descartar l'acció més antiga (la del fons), no rebutjar la nova.

  1. Pot una pila pura (només cim) descartar pel fons en O(1)? Raona la resposta.
  2. Implementa HistorialAmbLimit amb registrar(accio), desfer() (→ acció o None) i mida(), complint el límit. Pots recolzar-te en la list interna (assumint el cost que tingui) o proposar alguna cosa millor.

Solució

Part 1. No. El contracte de la pila només dona accés al cim; el fons és, per definició, inabastable sense desapilar-ho tot (O(n)). Necessitem una estructura amb accés als dos extrems: inserir/treure per dalt i descartar per baix. Aquesta estructura existeix i es diu deque (cua doble); el mòdul 2 la va mencionar (collections.deque, una doblement enllaçada per blocs) i el mòdul 4 la desenvolupa. Aquest exercici et fa sentir per què cal.

Part 2. Versió honesta amb list, documentant el cost:

class HistorialAmbLimit:
    """Historial de desfer que conserva nomes les ultimes k accions."""

    def __init__(self, limit):
        self._limit = limit
        self._accions = []                # cim = final de la llista, com sempre

    def registrar(self, accio):
        self._accions.append(accio)       # push normal: O(1) amortitzat
        if len(self._accions) > self._limit:
            self._accions.pop(0)          # descartar la MES ANTIGA: O(n) ai!

    def desfer(self):
        if not self._accions:
            return None                   # capa de domini: None, com a 03-03
        return self._accions.pop()        # la mes recent: O(1)

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


h = HistorialAmbLimit(3)
for n in (1, 2, 3, 4):
    h.registrar({"tipus": "canviar_estat", "tasca": n, "dades_previes": {}})
print(h.mida())                   # 3  (l'accio de la tasca 1 va ser descartada)
print(h.desfer()["tasca"])        # 4  (la mes recent continua sent el cim)
print(h.desfer()["tasca"])        # 3
print(h.desfer()["tasca"])        # 2
print(h.desfer())                 # None (la 1 ja no existeix: es va descartar)

Comentaris:

  • El comportament LIFO es conserva íntegre per dalt; el límit només actua per baix, i només quan se supera k.
  • Aquell pop(0) és la nostra vella coneguda trampa O(n). És acceptable? Depèn: amb limit = 50 accions, desplaçar 50 referències és menyspreable; amb limit = 1 000 000, no. Saber quantificar quan un O(n) és tolerable també és enginyeria (les n petites i acotades no fan mal).
  • La solució elegant substitueix la list per collections.deque(maxlen=limit): amb maxlen, el mateix deque descarta pel fons automàticament en fer append, tot en O(1). Escriu-ho mentalment i guarda-t'ho: ho farem amb fonament al mòdul 4, quan el deque deixi de ser una menció i passi a ser protagonista.

Exercici 6: de recursió a iteració amb pila explícita

Nivell: alt. A 03-04 vas veure que sumar_ids recursiu rebenta amb RecursionError en cadenes llargues. Generalitzem la cura. TaskFlow organitza ara projectes amb subtasques imbricades: una tasca pot contenir una llista "subtasques" de tasques, que al seu torn poden tenir les seves, a qualsevol profunditat.

  1. Escriu comptar_pendents_rec(tasca) (recursiva): compta quantes tasques de l'arbre de subtasques (inclosa l'arrel) tenen "estat": "pendent".
  2. Reescriu-la com a comptar_pendents_iter(tasca) sense recursió, fent servir una pila explícita de "tasques pendents de visitar".
  3. Comprova que la versió recursiva falla amb una cadena de 100 000 subtasques imbricades i la iterativa no.

Solució

Part 1: versió recursiva.

def comptar_pendents_rec(tasca):
    total = 1 if tasca["estat"] == "pendent" else 0
    for subtasca in tasca.get("subtasques", []):   # get: pot no haver-hi subtasques
        total += comptar_pendents_rec(subtasca)    # un marc de pila per nivell
    return total

Part 2: versió iterativa. La recepta general de conversió: allà on la recursió deixava feina pendent a la pila de crides, nosaltres deixem feina pendent en una Pila pròpia.

def comptar_pendents_iter(tasca):
    total = 0
    pendents = Pila()                 # tasques encara no visitades
    pendents.push(tasca)              # comencem per l'arrel
    while not pendents.esta_buida():
        actual = pendents.pop()       # visitar la pendent mes recent
        if actual["estat"] == "pendent":
            total += 1
        for subtasca in actual.get("subtasques", []):
            pendents.push(subtasca)   # les filles queden pendents de visitar
    return total

Part 3: la prova de foc.

# Construim una cadena de 100 000 tasques imbricades (cadascuna amb una subtasca)
arrel = {"id": 0, "titol": "T0", "prioritat": 2, "estat": "pendent"}
actual = arrel
for i in range(1, 100_000):
    filla = {"id": i, "titol": f"T{i}", "prioritat": 2, "estat": "pendent"}
    actual["subtasques"] = [filla]
    actual = filla

print(comptar_pendents_iter(arrel))   # 100000: sense despentinar-se
print(comptar_pendents_rec(arrel))    # RecursionError: maximum recursion depth exceeded

Comentaris:

  • Compara els esquelets: són el mateix algorisme. La recursiva diu "compta aquesta i delega les filles a la pila de crides"; la iterativa diu "compta aquesta i deixa les filles a la meva pila". La diferència és qui guarda el pendent: una pila implícita limitada a ~1000 marcs, o una pila explícita limitada només per la teva RAM.
  • El bucle while not pendents.esta_buida(): actual = pendents.pop() és el patró de buidatge de 03-02, ara amb la subtilesa que el mateix bucle hi afegeix elements: la pila creix i minva fins a esgotar la feina.
  • L'ordre de visita canvia respecte de la recursiva (les filles apilades surten en ordre invers), però per comptar l'ordre és irrellevant. Quan l'ordre importi, es controla l'ordre d'apilat — exactament el que faràs als recorreguts d'arbres (mòdul 6) i al DFS de grafs (mòdul 7): aquesta funció és un DFS sobre l'arbre de subtasques, encara que encara no en diguem així.

Errors Comuns i Consells

  • Mirar la solució al primer entrebanc: l'entrebanc és on s'aprèn. Concedeix-te almenys 15 minuts i una traça en paper per exercici abans de comparar.
  • Oblidar la guarda esta_buida(): ha aparegut als exercicis 2, 3 i 5. Si la teva solució llança IndexError amb entrades rares (buides, tot retrocessos...), gairebé segur que hi falta una guarda.
  • A l'exercici 3, intentar enumerar intercalacions: l'explosió combinatòria és enorme; la simulació àvida és O(n). Davant d'un problema de "és possible aquesta seqüència?", pensa abans a simular que a enumerar.
  • Al min-stack, guardar un sol mínim global: falla tan bon punt el mínim es desapila. Si el teu minim() queda obsolet després d'un pop, és aquest error: necessites el mínim per nivell.
  • En la conversió a iteratiu, oblidar apilar l'arrel o no consumir amb pop: bucle que no arrenca o bucle infinit. Plantilla mental: push llavor → while no buida → pop → processar → push filles.
  • Consell final: torna als exercicis d'aquí a una setmana i intenta resoldre'ls de memòria. Les piles es fixen amb les mans, no amb els ulls.

Conclusió

Mòdul de piles completat. En cinc lliçons has passat d'una promesa ("el desfer de TaskFlow t'està esperant") a un arsenal: el contracte LIFO i els seus invariants, dues implementacions intercanviables mesurades amb timeit, el desfer/refer real de TaskFlow amb dues piles, validació de balanceig, avaluació d'expressions, i —en aquesta lliçó— els patrons de doble bolcat, simulació àvida, pila auxiliar paral·lela (min-stack) i conversió de recursió en iteració, que és un DFS sense saber-ho encara. Pel camí han quedat dos senyals lluminosos apuntant al proper mòdul: l'historial amb límit demanava descartar pel fons mentre operava pel cim (dos extrems: un deque), i el min-stack consultava el mínim però no podia extreure sempre el més prioritari (una cua de prioritat). Totes dues necessitats, juntament amb la política oposada a LIFO —FIFO, el primer a arribar és el primer a sortir, com les tasques de TaskFlow esperant a ser processades per ordre just d'arribada— són exactament el programa del mòdul 4: les cues. Ens hi veiem.

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