3 - Representación de una cola lineal con listas

3.1 Estructura Cola

La cola lineal se define a partir de una clase que agrupa el buffer de datos, los índices de control y, opcionalmente, un contador de elementos. Este bloque encierra toda la información necesaria para respetar el TDA sin exponer detalles internos al resto del programa.

CAPACIDAD = 100


class Cola:
  def __init__(self, capacidad=CAPACIDAD):
    self.capacidad = capacidad
    self.datos = [None] * capacidad
    self.frente = 0
    self.final = 0
    self.cantidad = 0

Los campos frente y final contienen índices sobre la lista. El contador cantidad permite discriminar estados sin realizar restas costosas ni depender de banderas externas.

3.2 Índices frente y final

La inicialización posiciona ambos índices al comienzo de la lista y pone el contador en cero. A partir de allí cada inserción incrementa final y cada extracción incrementa frente. El ejemplo siguiente ilustra la rutina base:

class Cola:
  ...

  def encolar(self, valor):
    if self.final == self.capacidad:
      raise OverflowError("Cola llena")
    self.datos[self.final] = valor
    self.final += 1
    self.cantidad += 1

  def desencolar(self):
    if self.frente == self.final:
      raise IndexError("Cola vacia")
    valor = self.datos[self.frente]
    self.frente += 1
    self.cantidad -= 1
    return valor

El reposicionamiento lineal tiene la limitación de que frente nunca vuelve a cero sin realizar desplazamientos o reinicios, tema que se retomará en el punto 3.5.

3.3 Capacidad máxima

Definir una constante como CAPACIDAD hace explícito el límite de la cola. Es importante calcularla considerando el peor caso de solicitudes pendientes y, si es necesario, agregar una función para ajustar la capacidad o recrear la estructura.

Un patrón conveniente es exponer auxiliares es_vacia y es_llena para facilitar las validaciones desde el código de alto nivel:

class Cola:
  ...

  def es_vacia(self):
    return self.cantidad == 0

  def es_llena(self):
    return self.final == self.capacidad

Estas funciones evitan repetir comparaciones y reducen el riesgo de estados inconsistentes.

3.4 Cola llena y cola vacía

La detección de estados extremos debe ejecutarse antes de modificar los índices. Si la cola está vacía, un intento de desencolar debe devolver un código de error y dejar los punteros intactos. En sentido inverso, si se detecta cola llena, encolar tiene que rechazar el valor antes de escribir sobre la lista.

  • Cola vacía: frente == final y cantidad == 0. El consumidor no tiene elementos para procesar.
  • Cola llena: final == CAPACIDAD. El productor debe esperar o disparar una ampliación del buffer.
  • Estado intermedio: frente < final y cantidad > 0. Hay datos disponibles y también espacio libre.

Documentar claramente estos estados simplifica la integración con módulos de negocio o hilos concurrentes.

3.5 Problema del modelo lineal

La implementación lineal pura desperdicia posiciones al comienzo de la lista a medida que se desencolan elementos, porque frente avanza y nunca regresa. Cuando final alcanza CAPACIDAD, la cola se considera llena aunque existan casilleros libres al inicio.

Existen tres estrategias para mitigar esta desventaja:

  1. Compactación periódica: mover los elementos pendientes hacia el inicio y ajustar los índices. Es costoso para colas grandes.
  2. Reinicialización controlada: cuando la cola queda vacía, reiniciar frente y final a cero.
  3. Transición a modelo circular: utilizar aritmética modular para reciclar espacios, solución presentada en el tema 5.

Comprender este problema es crucial para dimensionar correctamente los buffers y evitar que la cola lineal se convierta en un cuello de botella.

3.6 Código completo listo para Python

El siguiente archivo main.py integra la estructura, las funciones auxiliares y un flujo de pruebas que imprime el estado de la cola tras cada operación. Puedes copiarlo y ejecutarlo con python main.py o probarlo en el simulador.

CAPACIDAD = 8


class Cola:
  def __init__(self, capacidad=CAPACIDAD):
    self.capacidad = capacidad
    self.datos = [None] * capacidad
    self.frente = 0
    self.final = 0
    self.cantidad = 0

  def es_vacia(self):
    return self.cantidad == 0

  def es_llena(self):
    return self.final == self.capacidad

  def encolar(self, valor):
    if self.es_llena():
      raise OverflowError("Cola llena")
    self.datos[self.final] = valor
    self.final += 1
    self.cantidad += 1

  def desencolar(self):
    if self.es_vacia():
      raise IndexError("Cola vacia")
    valor = self.datos[self.frente]
    self.frente += 1
    self.cantidad -= 1
    if self.frente == self.final:  # reinicio simple para reutilizar espacio
      self.frente = 0
      self.final = self.cantidad
    return valor

  def imprimir(self):
    contenido = " ".join(str(self.datos[i]) for i in range(self.frente, self.final))
    print(f"[cola] frente={self.frente} final={self.final} cantidad={self.cantidad} -> {contenido}")


if __name__ == "__main__":
  cola = Cola()

  for i in range(1, 6):
    cola.encolar(i * 10)
  cola.imprimir()

  while not cola.es_vacia():
    valor = cola.desencolar()
    print("Desencolado:", valor)
    if valor == 20:
      cola.encolar(99)
  cola.imprimir()
Ejecutar en el editor online

El bloque imprimir ayuda a visualizar en la consola la evolución de los índices y evidencia el problema del modelo lineal cuando el frente avanza más rápido que el final.

Retornar