1 - Introducción a las colas (Queues)

Visión general

Las colas son estructuras de datos lineales que atienden elementos en el orden exacto en el que llegan. En Python se modelan como un TDA que suele apoyarse en collections.deque o listas, exponiendo operaciones acotadas para insertar y extraer sin romper los invariantes del frente.

A lo largo del tutorial exploramos el modelo FIFO, revisamos colas simples, circulares y dobles, y explicamos cuándo conviene derivar hacia una cola de prioridad respaldada por un heap para asignar turnos según importancia.

Esta visión general también conecta con la implementación de colas de tareas, productores/consumidores y planificadores que veremos en los temas siguientes.

1.1 ¿Qué es una cola?

Una cola mantiene un frente lógico (próximo elemento a retirar) y un final donde se inserta la siguiente solicitud. Al igual que cualquier TDA, define una capacidad y estados especiales para cola vacía o llena, lo que obliga a validar condiciones antes de operar.

Relación entre los punteros front y rear de una cola

Los punteros avanzan en sentidos complementarios para garantizar el orden FIFO.

El siguiente fragmento muestra una implementación simple basada en deque que deja listos los auxiliares de capacidad y las operaciones principales:

from collections import deque


class Cola:
  def __init__(self, capacidad=None):
    self._capacidad = capacidad
    self._datos = deque()

  def encolar(self, valor):
    if self._capacidad is not None and len(self._datos) >= self._capacidad:
      raise OverflowError("Cola llena")
    self._datos.append(valor)

  def desencolar(self):
    if not self._datos:
      raise IndexError("Cola vacia")
    return self._datos.popleft()

  def frente(self):
    return self._datos[0] if self._datos else None

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

El método encolar valida el estado de cola llena, mientras que desencolar evita leer fuera de rango cuando no hay elementos pendientes. El frente se mantiene sin desplazar datos gracias al popleft() de deque.

Para ver la cola en acción, basta con un script que simule el ingreso de eventos y reporte qué elemento se encuentra en la cabecera:

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

  cola.encolar(5)
  cola.encolar(8)
  cola.encolar(13)

  while not cola.esta_vacia():
    print("Atendido:", cola.desencolar())
Ejecutar en el editor online

Puedes copiar ambos fragmentos en VS Code o en tu entorno favorito para observar cómo se respetan los estados vacío/lleno y para instrumentar pruebas con aserciones.

Simulación visual de operaciones en la cola

1.2 Modelo FIFO (First In, First Out)

FIFO describe la regla principal de una cola: el primer elemento que ingresa debe salir antes que los demás. En Python se implementa controlando el frente y el final sin recorrer posiciones intermedias, apoyándose en la eficiencia de deque.

  1. Con la cola vacía encolamos los valores 12, 18 y 4. frente queda en 12 y el final lógico se desplaza tres posiciones.
  2. El primer desencolar entrega 12 y actualiza el frente a 18 sin tocar el resto de la memoria.
  3. Si agregamos otro valor (por ejemplo 30) este se ubica al final de la fila hasta que los anteriores sean atendidos.

Este modelo mantiene la predictibilidad en colas de impresión, colas de mensajes o buffers de red. Solo se altera en escenarios de prioridad, donde la ordenación se delega a una estructura auxiliar.

1.3 Diferencias con una pila

Aunque pilas y colas son lineales, se utilizan para objetivos distintos. La comparación siguiente resume los contrastes más relevantes:

Característica Cola lineal Pila Cola de prioridad
Orden de servicio FIFO estricto LIFO (el último en entrar sale primero) Depende de la prioridad asignada
Extremos usados Frente para extraer, final para insertar Un solo tope Frente virtual definido por el valor más prioritario
Complejidad O(1) encolado y desencolado O(1) push/pop O(log n) al insertar o extraer si se usa un heap
Casos de uso Turnos, buffers, tareas pendientes Deshacer/rehacer, evaluación de expresiones Planificadores, sistemas de tickets VIP, Dijkstra

1.4 Ventajas y limitaciones

  • Determinismo: al consumir y producir en extremos fijos, las colas simplifican la razón de cómo progresa el sistema.
  • Eficiencia: las operaciones se implementan en O(1) sin recorrer el arreglo ni realinear datos.
  • Limitaciones: no existe acceso directo a elementos intermedios y se debe manejar el caso de cola llena para evitar sobrescrituras.
  • Consideraciones de memoria: en Python la administración es automática, pero conviene fijar una capacidad y validar los límites para prevenir estados inconsistentes.

1.5 Ejemplos cotidianos

  • Sistemas de turnos: bancos o centros de atención usan colas para entregar tickets y atender en el orden emitido.
  • Spool de impresoras: los documentos se encolan y la impresora retira uno por vez, respetando la hora de llegada.
  • Planificación Round Robin: los procesos se encolan y reciben un quantum de CPU antes de volver al final de la lista.
  • Colas de red: los routers mantienen paquetes encolados mientras los enlaces están ocupados.

Visualizar estos comportamientos ayuda a diseñar APIs claras para las colas específicas que abordaremos en los siguientes temas.

Retornar