El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
HOME Mis cursos Finalizados
◄ Anterior
◄

Implementación de Pilas

Siguiente ►
►

Ha llegado el momento de cumplir la promesa: implementar la pila. Y lo haremos dos veces. En el módulo 1 distinguimos el TDA (el contrato: qué operaciones y con qué coste) de la implementación (el cómo), con PilaConLista y PilaConDiccionario como ejemplo de que un contrato admite varios "cómos". Hoy esa idea deja de ser teórica: escribiremos una clase Pila sobre la list de Python y una PilaEnlazada sobre los nodos del módulo 2, comprobaremos que ambas cumplen exactamente el mismo contrato y los mismos invariantes, las mediremos con timeit, y discutiremos cuál conviene en cada situación. Como cierre, TaskFlow estrena su HistorialAcciones: la pila que registra cada acción del usuario con los datos necesarios para revertirla. Esta lección es el corazón del módulo: al terminarla no solo tendrás una pila, sino el criterio para elegir entre implementaciones equivalentes, una habilidad que usarás con cada estructura del resto del curso.

Contenido

  1. El contrato que ambas implementaciones deben cumplir
  2. Implementación 1: Pila sobre list
  3. Implementación 2: PilaEnlazada sobre nodos
  4. Mismo contrato, mismos tests
  5. Comparación de costes: amortizado vs garantizado, y memoria
  6. Midiendo con timeit
  7. ¿Cuál elegir y por qué?
  8. TaskFlow: la clase HistorialAcciones

El contrato que ambas implementaciones deben cumplir

Fijemos por escrito lo acordado en las lecciones anteriores. Toda pila de este curso debe ofrecer:

Operación Comportamiento Pila vacía Coste exigido
push(e) Apila e en la cima (no aplica) O(1)
pop() Retira y devuelve la cima IndexError O(1)
peek() Devuelve la cima sin retirar IndexError O(1)
esta_vacia() True/False True O(1)
tamano() Número de elementos 0 O(1)

Quien use la pila solo puede depender de esta tabla: nunca de los detalles internos. Eso nos da libertad total para implementar por dentro como queramos... siempre que la tabla se cumpla.

Implementación 1: Pila sobre list

En la lección anterior usamos una list "a pelo" como pila provisional y detectamos su defecto: nada impide saltarse el contrato (insert(0, ...), acceso por índice...). La solución es la encapsulación: guardar la lista como atributo interno y exponer únicamente las cinco operaciones.

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

    La cima es el FINAL de la lista interna: append/pop del final son O(1).
    """

    def __init__(self):
        self._elementos = []          # lista interna; el _ señala "privado"

    def push(self, elemento):
        self._elementos.append(elemento)      # apilar = append al final

    def pop(self):
        if not self._elementos:
            raise IndexError("pop sobre una pila vacía")
        return self._elementos.pop()          # pop() sin argumento = del final

    def peek(self):
        if not self._elementos:
            raise IndexError("peek sobre una pila vacía")
        return self._elementos[-1]            # solo lectura de la cima

    def esta_vacia(self):
        return len(self._elementos) == 0

    def tamano(self):
        return len(self._elementos)

    def __len__(self):                        # permite len(pila)
        return len(self._elementos)

    def __str__(self):                        # cima a la izquierda, como las trazas
        elementos = ", ".join(repr(e) for e in reversed(self._elementos))
        return f"Pila(cima -> [{elementos}])"

Explicación detallada:

  • self._elementos: el guion bajo inicial es la convención de Python para "atributo interno: no lo toques desde fuera". Python no lo prohíbe técnicamente, pero todo el ecosistema respeta la señal. Esta línea es la encapsulación: el usuario de Pila ya no ve una lista, ve una pila.
  • La cima es el final de la lista: decisión heredada de la lección anterior. append y pop() del final son las operaciones baratas del array dinámico; con insert(0)/pop(0) habríamos pagado O(n).
  • pop y peek lanzan IndexError con un mensaje propio: la list ya lanzaría IndexError, pero comprobarlo nosotros nos permite dar un mensaje claro ("pop sobre una pila vacía" en lugar de "pop from empty list") y, sobre todo, deja la decisión de diseño escrita en el código, no delegada por accidente.
  • len(pila) y print(pila): pequeños lujos pythónicos, igual que hicimos con __str__ en ListaEnlazada. __str__ imprime la cima primero, para que coincida con nuestras tablas de traza.

Probémosla con acciones de TaskFlow:

p = Pila()
p.push({"tipo": "crear", "tarea": 7})
p.push({"tipo": "cambiar_prioridad", "tarea": 7})
print(p.peek())        # {'tipo': 'cambiar_prioridad', 'tarea': 7}
print(p.tamano())      # 2
print(p.pop()["tipo"]) # cambiar_prioridad
print(p)               # Pila(cima -> [{'tipo': 'crear', 'tarea': 7}])

Implementación 2: PilaEnlazada sobre nodos

Ahora la versión prometida al final del módulo 2: una pila sobre nodos enlazados, "en unas pocas líneas". La idea completa cabe en una frase: la cima de la pila es la cabeza de una lista enlazada; push es insertar_al_inicio y pop es borrar la cabeza — las dos operaciones O(1) que ya dominas.

Reutilizamos el Nodo del módulo 2 (dato + siguiente):

class Nodo:
    """El mismo Nodo del módulo 2: un dato y la referencia al siguiente."""
    def __init__(self, dato):
        self.dato = dato
        self.siguiente = None


class PilaEnlazada:
    """Pila (LIFO) implementada sobre nodos enlazados.

    La cima es la CABEZA de la cadena de nodos: push/pop por la cabeza son O(1).
    """

    def __init__(self):
        self._cima = None             # referencia al nodo superior (o None)
        self._tamano = 0              # contador para tamano() en O(1)

    def push(self, elemento):
        nuevo = Nodo(elemento)        # 1. crear el nodo
        nuevo.siguiente = self._cima  # 2. el nuevo apunta a la antigua cima
        self._cima = nuevo            # 3. el nuevo ES la cima
        self._tamano += 1

    def pop(self):
        if self._cima is None:
            raise IndexError("pop sobre una pila vacía")
        nodo = self._cima             # 1. guardar el nodo a retirar
        self._cima = nodo.siguiente   # 2. la cima pasa a ser el siguiente
        self._tamano -= 1
        return nodo.dato              # 3. devolver el dato (el nodo se libera solo)

    def peek(self):
        if self._cima is None:
            raise IndexError("peek sobre una pila vacía")
        return self._cima.dato

    def esta_vacia(self):
        return self._cima is None

    def tamano(self):
        return self._tamano

    def __len__(self):
        return self._tamano

    def __str__(self):
        datos, actual = [], self._cima
        while actual is not None:
            datos.append(repr(actual.dato))
            actual = actual.siguiente
        return f"PilaEnlazada(cima -> [{', '.join(datos)}])"

Análisis paso a paso de las dos operaciones clave:

  • push es exactamente el insertar_al_inicio de ListaEnlazada, con la cabeza rebautizada como _cima. Tres pasos, ningún bucle: O(1) siempre, haya 3 o 3 millones de elementos. El orden de los pasos 2 y 3 importa: si hicieras self._cima = nuevo antes de enlazar nuevo.siguiente, perderías la referencia a la antigua pila (el mismo error de orden que vimos al insertar en listas enlazadas).
  • pop es borrar la cabeza: apartar el nodo, avanzar la cima, devolver el dato. También sin bucles: O(1) siempre. El nodo retirado deja de estar referenciado y el recolector de basura de Python lo libera.
  • _tamano como contador: contar recorriendo sería O(n); mantener el contador en cada push/pop da tamano() en O(1). Misma técnica que en ListaEnlazada.
flowchart LR
    subgraph ANTES["Antes de push(D)"]
        direction LR
        cima1["_cima"] --> C1["C"] --> B1["B"] --> A1["A"] --> N1["None"]
    end
    subgraph DESPUES["Después de push(D)"]
        direction LR
        cima2["_cima"] --> D2["D"] --> C2["C"] --> B2["B"] --> A2["A"] --> N2["None"]
    end
    ANTES -->|"nuevo.siguiente = antigua cima"| DESPUES

Mismo contrato, mismos tests

La prueba definitiva de que TDA e implementación están bien separados: un único juego de comprobaciones (los invariantes de la lección 03-02) debe pasar con cualquiera de las dos clases, sin cambiar ni una línea:

def probar_contrato(ClasePila):
    """Verifica los invariantes del TDA sobre cualquier implementación."""
    p = ClasePila()
    assert p.esta_vacia() and p.tamano() == 0        # invariante 1

    p.push("a")
    assert p.peek() == "a" and p.tamano() == 1       # invariante 2

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

    antes = p.tamano()
    p.peek()
    assert p.tamano() == antes                       # invariante 4: peek no modifica

    p.pop()
    try:
        p.pop()                                      # pila vacía: debe fallar
        assert False, "debería haber lanzado IndexError"
    except IndexError:
        pass
    print(f"{ClasePila.__name__}: contrato OK")

probar_contrato(Pila)           # Pila: contrato OK
probar_contrato(PilaEnlazada)   # PilaEnlazada: contrato OK

La función recibe la clase como parámetro y funciona con ambas. Para el código cliente (y para TaskFlow) las dos pilas son intercambiables: eso es programar contra el contrato.

Comparación de costes: amortizado vs garantizado, y memoria

Si ambas cumplen el contrato, ¿en qué se diferencian? En los matices de rendimiento y memoria:

Aspecto Pila (sobre list) PilaEnlazada (sobre nodos)
push O(1) amortizado O(1) garantizado
pop / peek O(1) O(1)
Memoria por elemento Compacta: referencias contiguas en el array Mayor: cada dato paga un objeto Nodo extra (dato + siguiente)
Localidad de memoria Buena (contigüidad → caché contenta) Peor (nodos dispersos por la memoria)
Al vaciarse mucho El array puede conservar capacidad sobrante Libera cada nodo al hacer pop
Líneas de código Menos (delega en list) Más (gestiona nodos y contador)

El matiz nuevo es amortizado vs garantizado, y merece explicación:

  • La list de Python es un array dinámico (módulo 1): cuando se llena, reserva un bloque mayor y copia todos los elementos. Ese append concreto cuesta O(n).
  • Como la capacidad crece de forma geométrica (siempre un porcentaje más), esas copias son cada vez más raras. Repartido ("amortizado") entre todos los append, el coste medio por operación es O(1). Pero un push individual, de vez en cuando, es lento.
  • PilaEnlazada nunca copia nada: cada push crea un nodo y mueve dos referencias. O(1) en el peor caso, sin excepciones.

¿Cuándo importa esta diferencia? Casi nunca en aplicaciones normales... y muchísimo en sistemas con requisitos de latencia estables (audio en tiempo real, sistemas embebidos), donde un "pico" ocasional es inaceptable. Es la primera vez en el curso que dos opciones correctas se distinguen no por el coste medio sino por su distribución: apunta el concepto, reaparecerá.

Midiendo con timeit

Comprobemos las afirmaciones con datos, como hicimos en el módulo 1. Medimos apilar y desapilar 100 000 elementos con cada implementación:

import timeit

def ejercitar(ClasePila, n=100_000):
    p = ClasePila()
    for i in range(n):
        p.push(i)
    while not p.esta_vacia():
        p.pop()

for Clase in (Pila, PilaEnlazada):
    t = timeit.timeit(lambda: ejercitar(Clase), number=10)
    print(f"{Clase.__name__:14}: {t:.3f} s (10 rondas de 100k push+pop)")

Resultados orientativos (los números exactos dependen de tu máquina; las proporciones, no):

Pila          : 0.35 s (10 rondas de 100k push+pop)
PilaEnlazada  : 1.60 s (10 rondas de 100k push+pop)

Dos lecturas importantes, en apariencia contradictorias:

  1. Ambas escalan igual: duplica n y verás que ambos tiempos se duplican aproximadamente — comportamiento lineal para n operaciones, es decir, O(1) por operación. La teoría se confirma en las dos.
  2. La constante importa: Pila es varias veces más rápida. ¿No habíamos dicho que PilaEnlazada tenía mejor garantía? Sí: mejor peor caso, pero peor constante, porque cada push crea un objeto Nodo en Python (caro) mientras que append está implementado en C sobre memoria contigua. Big O habla de crecimiento, no de velocidad absoluta: dos O(1) pueden diferir en un factor 5.

Esta es una lección general valiosísima: medir complementa a razonar. El análisis asintótico te dice qué escala; timeit te dice cuánto cuesta de verdad en tu plataforma.

¿Cuál elegir y por qué?

Criterio práctico para Python:

  • Por defecto: Pila sobre list. Menos código, menos memoria, más rápida en la práctica, y delega en una pieza ultraoptimizada del lenguaje. Es la elección correcta para TaskFlow y para el 95 % de los casos.
  • PilaEnlazada cuando... necesites O(1) garantizado por operación (latencia estable), o cuando la pila comparta nodos con otras estructuras enlazadas. Y, sobre todo, es la implementación que verás en libros y entrevistas, y la que se usa en lenguajes sin array dinámico incorporado: entenderla no es opcional.
  • El punto clave: como ambas cumplen el contrato, cambiar de una a otra no toca ni una línea del código cliente. Elegir implementación es una decisión local y reversible; elegir mal el TDA, en cambio, se paga en todo el programa.

TaskFlow: la clase HistorialAcciones

Cerremos poniendo la pila a trabajar. El historial de TaskFlow registra acciones: diccionarios con el tipo de acción, el id de la tarea afectada y los datos previos necesarios para revertirla:

{"tipo": "cambiar_estado", "tarea": 7, "datos_previos": {"estado": "pendiente"}}

HistorialAcciones envuelve una Pila y ofrece vocabulario del dominio (registrar/deshacer) en lugar de vocabulario de estructura (push/pop):

class HistorialAcciones:
    """Historial de deshacer de TaskFlow: una pila de acciones revertibles."""

    def __init__(self):
        self._pila = Pila()               # composición: contiene una Pila

    def registrar(self, tipo, tarea_id, datos_previos):
        accion = {"tipo": tipo, "tarea": tarea_id, "datos_previos": datos_previos}
        self._pila.push(accion)

    def deshacer(self):
        """Retira y devuelve la última acción registrada (para revertirla)."""
        if self._pila.esta_vacia():
            return None                   # aquí None SÍ es correcto: "no había nada"
        return self._pila.pop()

    def proxima_a_deshacer(self):
        """Texto para la interfaz, p. ej. el tooltip del botón Deshacer."""
        if self._pila.esta_vacia():
            return "Nada que deshacer"
        accion = self._pila.peek()
        return f"Deshacer: {accion['tipo']} (tarea {accion['tarea']})"

    def hay_acciones(self):
        return not self._pila.esta_vacia()

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

Y una sesión de uso sobre nuestra tarea de siempre:

tarea = {"id": 7, "titulo": "Revisar presupuesto", "prioridad": 2, "estado": "pendiente"}
historial = HistorialAcciones()

# El usuario cambia la prioridad a 1: guardamos el valor PREVIO antes de tocar nada
historial.registrar("cambiar_prioridad", 7, {"prioridad": tarea["prioridad"]})
tarea["prioridad"] = 1

# El usuario la pone en curso
historial.registrar("cambiar_estado", 7, {"estado": tarea["estado"]})
tarea["estado"] = "en_curso"

print(historial.proxima_a_deshacer())  # Deshacer: cambiar_estado (tarea 7)

# Pulsa Deshacer: recuperamos la acción y restauramos los datos previos
accion = historial.deshacer()
tarea.update(accion["datos_previos"])
print(tarea["estado"])                 # pendiente
print(historial.total())               # 1

Detalles de diseño que conviene subrayar:

  • datos_previos se captura antes de modificar la tarea: es la información mínima para revertir. Registrar después ya sería tarde: el valor antiguo se habría perdido.
  • Revertir es tarea.update(accion["datos_previos"]): como los datos previos son un dict con los campos antiguos, restaurarlos es una línea.
  • deshacer devuelve None si no hay nada: ¿contradice la lección anterior? No: la pila sigue lanzando IndexError; es HistorialAcciones, la capa de dominio, quien decide que "deshacer sin historial" no es un error de programación sino un caso normal de interfaz. La excepción vive en la estructura; la tolerancia, en la aplicación.
  • Fíjate en que aún no hay "rehacer": si el usuario deshace y se arrepiente, no hay vuelta. Resolverlo exige una segunda pila cooperando con esta — es la primera aplicación de la próxima lección.

Errores Comunes y Consejos

  • Romper la encapsulación: acceder a pila._elementos o pila._cima desde fuera "porque es más rápido". Acabas de convertir tu pila en una lista sin contrato; el día que cambies la implementación, todo ese código muere.
  • Invertir los pasos del push enlazado: asignar self._cima = nuevo antes de nuevo.siguiente = self._cima pierde toda la pila anterior. Si tu PilaEnlazada "solo recuerda el último elemento", es esto.
  • Olvidar el contador _tamano: sin él, o tamano() recorre la pila (O(n), contrato roto) o devuelve datos incorrectos. Cada push suma uno, cada pop con éxito resta uno (no restes antes de comprobar si está vacía).
  • Registrar la acción en el historial después de modificar la tarea: datos_previos capturaría ya el valor nuevo y el deshacer no desharía nada. Primero capturar, luego modificar.
  • Comparar implementaciones sin medir: "la enlazada será más rápida porque es O(1) garantizado" — acabas de ver que no. Razona con Big O, decide con timeit.
  • Consejo: escribe siempre una función tipo probar_contrato cuando tengas dos implementaciones de lo mismo. Es la red de seguridad que te permite cambiar de implementación sin miedo.

Ejercicios

Ejercicio 1: PilaAcotada

TaskFlow no quiere un historial infinito. Crea una clase PilaAcotada que reciba capacidad en el constructor y se comporte como Pila, salvo que push sobre una pila llena lance OverflowError("pila llena"). Añade un método esta_llena(). Hazla heredando de Pila (pista: super().__init__() y super().push(...)).

Ejercicio 2: __iter__ para PilaEnlazada

Añade a PilaEnlazada un método __iter__ (generador, como el de ListaEnlazada del módulo 2) que recorra los datos de cima a fondo sin modificar la pila. Con él, list(pila) debe devolver los elementos en orden de desapilado. Pregunta extra: ¿por qué "recorrer una pila" es, en rigor, salirse del TDA, y por qué aun así es útil en la práctica?

Ejercicio 3: revertir según el tipo de acción

Escribe la función revertir(accion, tareas) para TaskFlow, donde tareas es un dict de tareas por id (como el tablero del módulo 2) y accion es un dict del historial. Debe manejar tres tipos: "cambiar_estado" y "cambiar_prioridad" (restaurar datos_previos sobre la tarea) y "crear" (revertir una creación = eliminar la tarea; en este caso datos_previos es {}).

Soluciones

Solución 1:

class PilaAcotada(Pila):
    def __init__(self, capacidad):
        super().__init__()                 # inicializa la lista interna de Pila
        self._capacidad = capacidad

    def esta_llena(self):
        return self.tamano() >= self._capacidad

    def push(self, elemento):
        if self.esta_llena():
            raise OverflowError("pila llena")
        super().push(elemento)             # delega el apilado real en Pila

La herencia reutiliza todo (pop, peek, esta_vacia, tamano, __str__); solo push añade la guardia. Prueba: con capacidad=2, el tercer push lanza OverflowError. (En 03-05 veremos otra política más útil para un historial: en vez de fallar, descartar la acción más antigua.)

Solución 2:

class PilaEnlazada(PilaEnlazada):          # o añade el método a la clase original
    def __iter__(self):
        actual = self._cima
        while actual is not None:
            yield actual.dato              # produce datos de cima a fondo
            actual = actual.siguiente

Es el mismo patrón generador de ListaEnlazada.__iter__: un cursor actual que avanza por siguiente. list(pila) devuelve [cima, ..., fondo], el orden exacto en que saldrían con pop, pero sin sacarlos. Respecto a la pregunta extra: el contrato de la pila solo da acceso a la cima, así que iterar es "hacer trampa" sobre el TDA puro; en la práctica se acepta como operación de inspección (depurar, mostrar el historial en pantalla) porque no modifica el estado. La línea roja es modificar durante la iteración.

Solución 3:

def revertir(accion, tareas):
    tarea_id = accion["tarea"]
    if accion["tipo"] == "crear":
        # Deshacer una creación es eliminar la tarea del tablero
        del tareas[tarea_id]
    elif accion["tipo"] in ("cambiar_estado", "cambiar_prioridad"):
        # Restaurar los campos previos sobre la tarea existente
        tareas[tarea_id].update(accion["datos_previos"])
    else:
        raise ValueError(f"tipo de acción desconocido: {accion['tipo']}")

Prueba rápida:

tareas = {7: {"id": 7, "titulo": "Revisar presupuesto", "prioridad": 1, "estado": "en_curso"}}
accion = {"tipo": "cambiar_estado", "tarea": 7, "datos_previos": {"estado": "pendiente"}}
revertir(accion, tareas)
print(tareas[7]["estado"])   # pendiente

El else con ValueError es deliberado: si mañana TaskFlow añade un tipo de acción y olvidamos su reversión, mejor un error ruidoso que un deshacer que no deshace.

Conclusión

Ya tienes dos pilas completas y verificadas: Pila, que encapsula una list con la cima en el final, y PilaEnlazada, que reencarna el insertar_al_inicio/borrar-cabeza del módulo 2 con la cabeza rebautizada como cima. Has comprobado con un mismo juego de tests que ambas cumplen idéntico contrato —la esencia del TDA— y has aprendido a distinguirlas donde de verdad difieren: O(1) amortizado frente a O(1) garantizado, consumo de memoria, y constantes reales medidas con timeit (con la moraleja de que dos O(1) pueden diferir en un factor 5). TaskFlow, por su parte, ya registra y deshace acciones con HistorialAcciones y su patrón "captura los datos previos, luego modifica". Pero le falta algo que todo usuario espera: arrepentirse del deshacer. En la próxima lección construiremos el deshacer/rehacer completo con dos pilas cooperando, y veremos que las pilas también validan paréntesis, evalúan expresiones y sostienen cada llamada a función que ejecuta Python.

◄ Anterior
◄
Siguiente ►
►
El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
© Copyright 2026. Todos los derechos reservados