6 - Representación de una pila con listas enlazadas

Motivación del enfoque enlazado

Cuando el tamaño de la pila es impredecible o se desean inserciones sin realocaciones, una lista enlazada ofrece crecimiento nodo a nodo. Cada push crea un nodo nuevo y lo enlaza al tope; cada pop lo descarta. El recolector de basura de Python libera la memoria de los nodos que ya no tienen referencias.

El tope es un puntero (referencia) al nodo más reciente, lo que mantiene las operaciones principales en O(1) sin depender de capacidades fijas.

6.1 Nodos y clase contenedora

Definimos una clase Nodo para encapsular el valor y el enlace al siguiente nodo, y una clase PilaEnlazada que administra el tope.

class Nodo:
  def __init__(self, valor, sig=None):
    self.valor = valor
    self.sig = sig


class PilaEnlazada:
  def __init__(self):
    self.tope = None
    self._largo = 0

La variable tope apunta siempre al nodo superior; si es None, la pila está vacía. Llevar un contador interno (_largo) facilita las consultas de tamaño.

6.2 Operaciones básicas

Cada operación modifica referencias sin desplazar colecciones completas:

  def __len__(self):
    return self._largo

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

  def push(self, valor):
    self.tope = Nodo(valor, self.tope)
    self._largo += 1

  def pop(self):
    if self.esta_vacia():
      raise IndexError("Pila vacia")
    valor = self.tope.valor
    self.tope = self.tope.sig
    self._largo -= 1
    return valor

  def peek(self):
    if self.esta_vacia():
      raise IndexError("Pila vacia")
    return self.tope.valor

El costo es constante: reasignar una referencia y actualizar el contador. Esto permite manejar flujos de datos extensos sin realocar bloques contiguos como en una lista.

6.3 Ventajas y escenarios de uso

  • Crecimiento bajo demanda: se reserva memoria solo por nodo, sin espacios vacíos ni capacidades predefinidas.
  • Inserciones consistentes: operaciones O(1) sin depender de redimensionados internos.
  • Educativo: hace explícitos los enlaces y ayuda a visualizar estructuras más complejas como árboles.

Es ideal para historiales extensos, parsers o ejercicios donde la cantidad de elementos no puede anticiparse.

6.4 Limpieza y depuración

Aunque Python libera automáticamente, conviene ofrecer un método de limpieza y otro de impresión que permita inspeccionar el contenido sin romper el LIFO.

  def limpiar(self):
    self.tope = None
    self._largo = 0

  def imprimir(self):
    print(f"Pila enlazada ({len(self)} nodos):")
    actual = self.tope
    while actual:
      sufijo = " <- top" if actual is self.tope else ""
      print(f"  {actual.valor}{sufijo}")
      actual = actual.sig

limpiar permite reutilizar la misma instancia en pruebas repetidas; imprimir muestra el recorrido desde el tope hacia la base.

6.5 Código completo listo para usar

Integrando todo en un módulo ejecutable obtenemos una pila enlazada funcional en cualquier versión moderna de Python:

class Nodo:
  def __init__(self, valor, sig=None):
    self.valor = valor
    self.sig = sig


class PilaEnlazada:
  def __init__(self):
    self.tope = None
    self._largo = 0

  def __len__(self):
    return self._largo

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

  def push(self, valor):
    self.tope = Nodo(valor, self.tope)
    self._largo += 1

  def pop(self):
    if self.esta_vacia():
      raise IndexError("Pila vacia")
    valor = self.tope.valor
    self.tope = self.tope.sig
    self._largo -= 1
    return valor

  def peek(self):
    if self.esta_vacia():
      raise IndexError("Pila vacia")
    return self.tope.valor

  def limpiar(self):
    self.tope = None
    self._largo = 0

  def imprimir(self):
    print(f"Pila enlazada ({len(self)} nodos):")
    actual = self.tope
    while actual:
      sufijo = " <- top" if actual is self.tope else ""
      print(f"  {actual.valor}{sufijo}")
      actual = actual.sig


if __name__ == "__main__":
  pila = PilaEnlazada()

  for valor in (5, 15, 25):
    pila.push(valor)
  pila.imprimir()

  print("Peek:", pila.peek())

  while not pila.esta_vacia():
    print("Pop:", pila.pop())

Ejecuta el script con python tema6_demo.py o prácticalo directamente en el editor online:

Abrir editor online
Retornar