2 - Tipos de colas

2.1 Cola lineal

La cola lineal es la versión más intuitiva: se reserva una lista de tamaño fijo, se define un frente y un final y se desplazan ambos índices a medida que las solicitudes entran y salen. Es ideal para colas pequeñas o cuando el volumen de operaciones es moderado y previsiblemente inferior a la capacidad establecida.

Su mayor debilidad es el despericio de espacio cuando se desencolan elementos al comienzo y las posiciones liberadas no se reutilizan. Esto provoca el conocido problema de "falsa saturación" si se alcanzó el límite una vez.

TAM_MAX = 64


class ColaLineal:
  def __init__(self, capacidad=TAM_MAX):
    self.capacidad = capacidad
    self.datos = [None] * capacidad
    self.frente = 0
    self.final = 0

  def esta_vacia(self):
    return self.frente == self.final

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

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

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

Este diseño obliga a reinicializar la cola cuando frente alcanza a final y ambos valen TAM_MAX. En sistemas interactivos se suele copiar los elementos remanentes al comienzo o recurrir a colas circulares.

2.2 Cola circular

En la cola circular se reutilizan las posiciones liberadas volviendo a la posición cero mediante el operador módulo. Solo se necesita un contador de elementos activos para diferenciar entre cola llena y vacía cuando frente == final.

  • Ventaja principal: aprovecha cada casillero del buffer sin mover datos.
  • Consideración: deben actualizarse los índices en aritmética modular para evitar desbordes.
TAM_CIRC = 64


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

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

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

Las colas circulares aparecen en drivers, buffers de audio o protocolos de red porque encajan con la naturaleza repetitiva de los flujos.

2.3 Deque (double-ended queue)

El deque permite insertar y eliminar por ambos extremos. Se lo usa cuando la lógica requiere alternar prioridades, simular estructuras híbridas o implementar algoritmos de ventanas deslizantes.

En Python se apoya en collections.deque, que optimiza inserciones y extracciones en los extremos con complejidad O(1) amortizada.

from collections import deque


def demo_deque():
  fila = deque()

  fila.append("A")        # push back
  fila.append("B")
  fila.appendleft("VIP")  # push front

  print("Frente:", fila[0])
  print("Sale:", fila.popleft())   # pop front
  print("Sale por atras:", fila.pop())  # pop back


if __name__ == "__main__":
  demo_deque()

Cada operación mantiene la complejidad O(1) amortizada, lo que vuelve al deque una opción atractiva frente a combinaciones ad hoc de dos pilas o dos colas.

2.4 Cola de prioridad

La cola de prioridad modifica la regla FIFO permitiendo que el elemento con mayor o menor prioridad (según la definición del problema) sea atendido antes. En Python se implementa eficientemente con heapq, que usa un heap binario representado sobre una lista.

Las operaciones de inserción y extracción logran complejidad O(log n) al reorganizar el heap. Esta estructura es indispensable para planificadores, rutas de menor costo o simulaciones con eventos.

import heapq


class ColaPrioridad:
  def __init__(self):
    self._heap = []

  def encolar(self, prioridad, valor):
    heapq.heappush(self._heap, (prioridad, valor))

  def desencolar(self):
    if not self._heap:
      raise IndexError("Cola vacia")
    prioridad, valor = heapq.heappop(self._heap)
    return prioridad, valor

  def peek(self):
    return self._heap[0] if self._heap else None


if __name__ == "__main__":
  cola = ColaPrioridad()
  cola.encolar(2, "soporte estandar")
  cola.encolar(1, "soporte urgente")
  cola.encolar(3, "consulta general")

  while cola.peek():
    prioridad, valor = cola.desencolar()
    print(f"Atendiendo ({prioridad}): {valor}")

Una cola de prioridad debe exponer también una operación peek para consultar el próximo elemento a salir sin modificar la estructura, y una función de comparación cuando se necesitan prioridades compuestas.

Retornar