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

Ejercicios con Pilas

Siguiente ►
►

Esta lección cierra el módulo de pilas y es íntegramente práctica: seis ejercicios progresivos, sin teoría nueva, que consolidan todo lo aprendido —el contrato del TDA (03-01 y 03-02), las implementaciones Pila y PilaEnlazada (03-03) y los patrones de aplicación (03-04)— y varios de ellos amplían directamente TaskFlow. Trabaja cada ejercicio de verdad antes de mirar la solución: intenta primero la traza en papel (como en 03-02), después el código, y solo entonces compara. Las soluciones están completas y comentadas, con el razonamiento que lleva hasta ellas, porque el objetivo no es "que te salga" sino que sepas por qué sale. En todos los ejercicios puedes usar la clase Pila de la lección 03-03 (o una list con append/pop, ya sabes por qué por el final).

Contenido

  1. Ejercicio 1: invertir una cadena (y una lista de tareas)
  2. Ejercicio 2: procesar retrocesos de teclado
  3. Ejercicio 3: validar secuencias de push/pop
  4. Ejercicio 4: min-stack — el mínimo en O(1)
  5. Ejercicio 5: historial de deshacer con límite
  6. Ejercicio 6: de recursión a iteración con pila explícita

Ejercicio 1: invertir una cadena (y una lista de tareas)

Nivel: básico. El "hola mundo" de las pilas: como los elementos salen en orden inverso al que entran, apilar todo y desapilarlo invierte cualquier secuencia.

  1. Escribe invertir_cadena(texto) que devuelva el texto invertido usando una pila (sin [::-1] ni reversed, claro: el objetivo es el patrón).
  2. Escribe invertir_tareas(tareas) que reciba una lista de dicts de tarea y devuelva una lista nueva en orden inverso — TaskFlow la usará para mostrar "las últimas tareas creadas primero".
  3. Pregunta de análisis: ¿coste en tiempo y en espacio? ¿Y si en vez de apilar/desapilar hicieras dos pasadas con pop(0)?

Solución

def invertir_cadena(texto):
    pila = Pila()
    for caracter in texto:        # fase 1: apilar todo (entra en orden)
        pila.push(caracter)
    resultado = []
    while not pila.esta_vacia():  # fase 2: desapilar todo (sale invertido)
        resultado.append(pila.pop())
    return "".join(resultado)

def invertir_tareas(tareas):
    pila = Pila()
    for tarea in tareas:
        pila.push(tarea)
    invertidas = []
    while not pila.esta_vacia():
        invertidas.append(pila.pop())
    return invertidas

print(invertir_cadena("TaskFlow"))     # wolFksaT
print(invertir_tareas([{"id": 1, "titulo": "A", "prioridad": 2, "estado": "pendiente"},
                       {"id": 2, "titulo": "B", "prioridad": 1, "estado": "pendiente"}]))
# [{'id': 2, ...}, {'id': 1, ...}]

Comentarios:

  • El patrón es el doble volcado: todo dentro, todo fuera. Una pasada de push (n operaciones O(1)) más una de pop (otras n): O(n) tiempo, O(n) espacio (la pila llega a contener los n elementos).
  • Nota el eco de 03-04 (ejercicio 1): una inversión cambia el orden; dos inversiones lo restauran. Por eso deshacer+rehacer con dos pilas devuelve el orden cronológico.
  • Sobre la pregunta 3: recorrer con pop(0) sobre una list sería O(n) por elemento → O(n²) total. Es la trampa insert(0)/pop(0) del módulo 1 otra vez; con 100 000 tareas, la diferencia entre milisegundos y minutos.

Ejercicio 2: procesar retrocesos de teclado

Nivel: básico. En el campo "título de la tarea" de TaskFlow llega la secuencia de teclas pulsadas, donde # representa la tecla de retroceso (borra el último carácter escrito, si lo hay). Escribe texto_final(teclas) que devuelva el texto resultante.

Ejemplos: texto_final("Revisar#####dactar") → "Redactar"; texto_final("##Hola#") → "Hol" (retrocesos sobre texto vacío no hacen nada).

Solución

def texto_final(teclas):
    pila = Pila()
    for tecla in teclas:
        if tecla == "#":
            if not pila.esta_vacia():   # retroceso sin texto: se ignora
                pila.pop()              # borra el último carácter escrito
        else:
            pila.push(tecla)
    # La pila tiene el texto de cima a fondo = invertido: lo damos la vuelta
    caracteres = []
    while not pila.esta_vacia():
        caracteres.append(pila.pop())
    return "".join(reversed(caracteres))

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

Comentarios:

  • "Borrar lo último escrito" es la definición operativa de pop: el texto en edición es una pila de caracteres (lo identificaste ya en el ejercicio 2 de 03-01).
  • La guardia esta_vacia() antes del pop es obligatoria: sin ella, "##Hola#" lanzaría IndexError en el primer #. Es el error común número uno de 03-02 en estado puro.
  • Al final la pila contiene el texto invertido (la cima es el último carácter): hay que volcar y re-invertir. Coste total O(n).

Ejercicio 3: validar secuencias de push/pop

Nivel: medio. Te dan dos listas: entradas (el orden en que se apilaron n elementos distintos) y salidas (un orden de desapilado que alguien afirma haber observado). Escribe secuencia_valida(entradas, salidas) que devuelva True si esa secuencia de salida es posible en una pila, intercalando pushes y pops como se quiera.

Ejemplos con entradas = [1, 2, 3, 4]:

  • salidas = [2, 1, 4, 3] → True (push 1, push 2, pop 2, pop 1, push 3, push 4, pop 4, pop 3).
  • salidas = [3, 1, 2] con entradas = [1, 2, 3] → False: para sacar el 3 primero, 1 y 2 quedan apilados con el 2 encima; es imposible que salga el 1 antes que el 2.

Pista: simula. Apila las entradas en orden y, tras cada push, desapila con avidez mientras la cima coincida con el siguiente elemento esperado de salidas.

Solución

def secuencia_valida(entradas, salidas):
    if len(entradas) != len(salidas):
        return False
    pila = Pila()
    i = 0                                  # índice del próximo pop esperado
    for elemento in entradas:              # simulamos los push en su orden
        pila.push(elemento)
        # Desapilado ávido: mientras la cima sea justo lo que se espera, pop
        while not pila.esta_vacia() and i < len(salidas) and pila.peek() == salidas[i]:
            pila.pop()
            i += 1
    return pila.esta_vacia()               # todo salió en el orden pedido

print(secuencia_valida([1, 2, 3, 4], [2, 1, 4, 3]))  # True
print(secuencia_valida([1, 2, 3], [3, 1, 2]))        # False
print(secuencia_valida([1, 2, 3], [1, 2, 3]))        # True (pop tras cada push)
print(secuencia_valida([1, 2, 3], [3, 2, 1]))        # True (todos los push, luego pops)

Comentarios:

  • La idea profunda: no hace falta razonar sobre todas las intercalaciones posibles; basta simular la única estrategia sensata (desapilar en cuanto la cima coincide con lo esperado). Si esa estrategia no logra la secuencia, ninguna lo hará: retrasar un pop posible solo entierra más el elemento.
  • peek decide y pop ejecuta: el patrón "mirar antes de actuar" de 03-02 y del shunting-yard de 03-04.
  • Al terminar, si la pila no quedó vacía es que algún elemento no pudo salir cuando le tocaba: False (lo devuelve esta_vacia() directamente).
  • Coste O(n): cada elemento se apila una vez y se desapila a lo sumo una vez, aunque haya un while dentro del for (cuenta operaciones totales, no anidamiento: un razonamiento de coste amortizado como el de 03-03).

Ejercicio 4: min-stack — el mínimo en O(1)

Nivel: medio-alto. TaskFlow quiere mostrar en todo momento "la tarea más prioritaria del historial" (recuerda: prioridad 1 = máxima, así que buscamos el mínimo valor). Recorrer el historial en cada consulta sería O(n). Diseña PilaConMinimo con el contrato habitual (push, pop, peek, esta_vacia, tamano) más una operación minimo() que devuelva el valor mínimo apilado, todo en O(1).

Pista: una pila auxiliar que, en paralelo a la principal, guarde "el mínimo vigente hasta este nivel". Piensa qué debe apilarse en la auxiliar en cada push y qué ocurre en cada pop.

Solución

class PilaConMinimo:
    """Pila con minimo() en O(1) mediante una pila auxiliar de mínimos vigentes."""

    def __init__(self):
        self._pila = Pila()        # los datos reales
        self._minimos = Pila()     # mínimos vigentes, en paralelo nivel a nivel

    def push(self, valor):
        self._pila.push(valor)
        if self._minimos.esta_vacia():
            self._minimos.push(valor)
        else:
            # El mínimo vigente tras este push: el menor entre el nuevo y el anterior
            self._minimos.push(min(valor, self._minimos.peek()))

    def pop(self):
        self._minimos.pop()        # las dos pilas crecen y menguan a la vez
        return self._pila.pop()

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

    def minimo(self):
        return self._minimos.peek()   # O(1): el mínimo vigente está en la cima

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

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


p = PilaConMinimo()
for prioridad in [3, 1, 2]:
    p.push(prioridad)
print(p.minimo())   # 1
p.pop()             # sale el 2
print(p.minimo())   # 1  (el 1 sigue dentro)
p.pop()             # sale el 1
print(p.minimo())   # 3  (¡el mínimo anterior "revive" solo!)

Comentarios:

  • El truco es el invariante paralelo: _minimos tiene siempre el mismo tamaño que _pila, y su cima es "el mínimo de todo lo que hay ahora en _pila". Cada push apila en _minimos el min entre el valor nuevo y el mínimo anterior; cada pop desapila de ambas.
  • La magia está en el último print: al desapilar el 1, el mínimo vuelve a ser 3 sin recalcular nada, porque la pila auxiliar recuerda el mínimo de cada nivel histórico. Un contador simple ("el mínimo es 1") no podría: al sacar el 1 no sabría cuál era el anterior.
  • Coste: todas las operaciones O(1); espacio O(n) extra por la pila auxiliar. Es un intercambio espacio-por-tiempo, la moneda de cambio más habitual en estructuras de datos.
  • Traza de las dos pilas para push de 3, 1, 2 (cima arriba):
_pila _minimos
2 1
1 1
3 3
  • Conexión con TaskFlow: si se apilan acciones y en _minimos se guarda la prioridad mínima vista, minimo() responde "la tarea más prioritaria tocada en esta sesión" al instante. (Para extraer siempre la tarea más prioritaria del tablero —no solo consultarla— la estructura adecuada es la cola de prioridad, que llega en el módulo 4.)

Ejercicio 5: historial de deshacer con límite

Nivel: medio-alto. El historial infinito de GestorDeshacerRehacer (03-04) gasta memoria sin freno. TaskFlow decide: "se conservan como máximo las últimas k acciones deshacibles". Ojo: a diferencia de la PilaAcotada de 03-03 (que rechazaba el push), aquí al superar el límite debe descartarse la acción más antigua (la del fondo), no rechazarse la nueva.

  1. ¿Puede una pila pura (solo cima) descartar por el fondo en O(1)? Razona la respuesta.
  2. Implementa HistorialConLimite con registrar(accion), deshacer() (→ acción o None) y tamano(), cumpliendo el límite. Puedes apoyarte en la list interna (asumiendo el coste que tenga) o proponer algo mejor.

Solución

Parte 1. No. El contrato de la pila solo da acceso a la cima; el fondo es, por definición, inalcanzable sin desapilarlo todo (O(n)). Necesitamos una estructura con acceso a los dos extremos: insertar/quitar por arriba y descartar por abajo. Esa estructura existe y se llama deque (cola doble); el módulo 2 la mencionó (collections.deque, una doblemente enlazada por bloques) y el módulo 4 la desarrolla. Este ejercicio te hace sentir por qué hace falta.

Parte 2. Versión honesta con list, documentando el coste:

class HistorialConLimite:
    """Historial de deshacer que conserva solo las últimas k acciones."""

    def __init__(self, limite):
        self._limite = limite
        self._acciones = []               # cima = final de la lista, como siempre

    def registrar(self, accion):
        self._acciones.append(accion)     # push normal: O(1) amortizado
        if len(self._acciones) > self._limite:
            self._acciones.pop(0)         # descartar la MÁS ANTIGUA: O(n) ¡ay!

    def deshacer(self):
        if not self._acciones:
            return None                   # capa de dominio: None, como en 03-03
        return self._acciones.pop()       # la más reciente: O(1)

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


h = HistorialConLimite(3)
for n in (1, 2, 3, 4):
    h.registrar({"tipo": "cambiar_estado", "tarea": n, "datos_previos": {}})
print(h.tamano())                 # 3  (la acción de la tarea 1 fue descartada)
print(h.deshacer()["tarea"])      # 4  (la más reciente sigue siendo la cima)
print(h.deshacer()["tarea"])      # 3
print(h.deshacer()["tarea"])      # 2
print(h.deshacer())               # None (la 1 ya no existe: se descartó)

Comentarios:

  • El comportamiento LIFO se conserva íntegro por arriba; el límite solo actúa por abajo, y solo cuando se supera k.
  • Ese pop(0) es nuestra vieja conocida trampa O(n). ¿Es aceptable? Depende: con limite = 50 acciones, desplazar 50 referencias es despreciable; con limite = 1 000 000, no. Saber cuantificar cuándo un O(n) es tolerable también es ingeniería (los n pequeños y acotados no duelen).
  • La solución elegante sustituye la list por collections.deque(maxlen=limite): con maxlen, el propio deque descarta por el fondo automáticamente al hacer append, todo en O(1). Escríbelo mentalmente y guárdalo: lo haremos con fundamento en el módulo 4, cuando el deque deje de ser una mención y pase a ser protagonista.

Ejercicio 6: de recursión a iteración con pila explícita

Nivel: alto. En 03-04 viste que sumar_ids recursivo revienta con RecursionError en cadenas largas. Generalicemos la cura. TaskFlow organiza ahora proyectos con subtareas anidadas: una tarea puede contener una lista "subtareas" de tareas, que a su vez pueden tener las suyas, a cualquier profundidad.

  1. Escribe contar_pendientes_rec(tarea) (recursiva): cuenta cuántas tareas del árbol de subtareas (incluida la raíz) tienen "estado": "pendiente".
  2. Reescríbela como contar_pendientes_iter(tarea) sin recursión, usando una pila explícita de "tareas pendientes de visitar".
  3. Comprueba que la versión recursiva falla con una cadena de 100 000 subtareas anidadas y la iterativa no.

Solución

Parte 1: versión recursiva.

def contar_pendientes_rec(tarea):
    total = 1 if tarea["estado"] == "pendiente" else 0
    for subtarea in tarea.get("subtareas", []):   # get: puede no haber subtareas
        total += contar_pendientes_rec(subtarea)  # un marco de pila por nivel
    return total

Parte 2: versión iterativa. La receta general de conversión: donde la recursión dejaba trabajo pendiente en la pila de llamadas, nosotros dejamos trabajo pendiente en una Pila propia.

def contar_pendientes_iter(tarea):
    total = 0
    pendientes = Pila()               # tareas aún no visitadas
    pendientes.push(tarea)            # empezamos por la raíz
    while not pendientes.esta_vacia():
        actual = pendientes.pop()     # visitar la pendiente más reciente
        if actual["estado"] == "pendiente":
            total += 1
        for subtarea in actual.get("subtareas", []):
            pendientes.push(subtarea) # sus hijas quedan pendientes de visitar
    return total

Parte 3: la prueba de fuego.

# Construimos una cadena de 100 000 tareas anidadas (cada una con una subtarea)
raiz = {"id": 0, "titulo": "T0", "prioridad": 2, "estado": "pendiente"}
actual = raiz
for i in range(1, 100_000):
    hija = {"id": i, "titulo": f"T{i}", "prioridad": 2, "estado": "pendiente"}
    actual["subtareas"] = [hija]
    actual = hija

print(contar_pendientes_iter(raiz))   # 100000: sin despeinarse
print(contar_pendientes_rec(raiz))    # RecursionError: maximum recursion depth exceeded

Comentarios:

  • Compara los esqueletos: son el mismo algoritmo. La recursiva dice "cuenta esta y delega las hijas en la pila de llamadas"; la iterativa dice "cuenta esta y deja las hijas en mi pila". La diferencia es quién guarda lo pendiente: una pila implícita limitada a ~1000 marcos, o una pila explícita limitada solo por tu RAM.
  • El bucle while not pendientes.esta_vacia(): actual = pendientes.pop() es el patrón de vaciado de 03-02, ahora con la sutileza de que el propio bucle añade elementos: la pila crece y mengua hasta agotar el trabajo.
  • El orden de visita cambia respecto a la recursiva (las hijas apiladas salen en orden inverso), pero para contar el orden es irrelevante. Cuando el orden importe, se controla el orden de apilado — exactamente lo que harás en los recorridos de árboles (módulo 6) y en DFS de grafos (módulo 7): esta función es un DFS sobre el árbol de subtareas, aunque aún no lo llamemos así.

Errores Comunes y Consejos

  • Mirar la solución al primer atasco: el atasco es donde se aprende. Concédete al menos 15 minutos y una traza en papel por ejercicio antes de comparar.
  • Olvidar la guardia esta_vacia(): ha aparecido en los ejercicios 2, 3 y 5. Si tu solución lanza IndexError con entradas raras (vacías, todo retrocesos...), casi seguro que falta una guardia.
  • En el ejercicio 3, intentar enumerar intercalaciones: la explosión combinatoria es enorme; la simulación ávida es O(n). Ante un problema de "¿es posible esta secuencia?", piensa antes en simular que en enumerar.
  • En el min-stack, guardar un solo mínimo global: falla en cuanto el mínimo se desapila. Si tu minimo() se queda obsoleto tras un pop, es este error: necesitas el mínimo por nivel.
  • En la conversión a iterativo, olvidar apilar la raíz o no consumir con pop: bucle que no arranca o bucle infinito. Plantilla mental: push semilla → while no vacía → pop → procesar → push hijos.
  • Consejo final: vuelve a los ejercicios en una semana e intenta resolverlos de memoria. Las pilas se fijan con las manos, no con los ojos.

Conclusión

Módulo de pilas completado. En cinco lecciones has pasado de una promesa ("el deshacer de TaskFlow te está esperando") a un arsenal: el contrato LIFO y sus invariantes, dos implementaciones intercambiables medidas con timeit, el deshacer/rehacer real de TaskFlow con dos pilas, validación de balanceo, evaluación de expresiones, y —en esta lección— los patrones de doble volcado, simulación ávida, pila auxiliar paralela (min-stack) y conversión de recursión en iteración, que es un DFS sin saberlo aún. Por el camino han quedado dos señales luminosas apuntando al próximo módulo: el historial con límite pedía descartar por el fondo mientras operaba por la cima (dos extremos: un deque), y el min-stack consultaba el mínimo pero no podía extraer siempre el más prioritario (una cola de prioridad). Ambas necesidades, junto con la política opuesta a LIFO —FIFO, el primero en llegar es el primero en salir, como las tareas de TaskFlow esperando a ser procesadas por orden justo de llegada— son exactamente el programa del módulo 4: las colas. Nos vemos allí.

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