GUÍA 21-09-26 Estructuras de Datos

CN122 · lunes 21/09/2026 · 13:00-14:15 · Sesión 12

Colas circulares

LA IDEA

El arreglo se trata como si sus extremos estuvieran unidos. Al llegar al final, los índices regresan al inicio con aritmética modular.

• final = (final + 1) % capacidad
• frente = (frente + 1) % capacidad

DISTINGUIR VACÍA DE LLENA

Con la sola condición frente == final ambas situaciones se ven idénticas. Hay dos soluciones estándar y conviene conocer las dos.

• Contador de elementos: vacía si cont == 0, llena si cont == capacidad. Es la más clara.
• Sacrificar una celda: llena si (final + 1) % capacidad == frente. Ahorra el contador y desperdicia un lugar.

IMPLEMENTACIÓN CON CONTADOR

1. Inicializar frente = 0, final = −1, cont = 0.

2. enqueue: si cont == capacidad, error; si no, final = (final+1)%cap, escribir, cont++.

3. dequeue: si cont == 0, error; si no, leer en frente, frente = (frente+1)%cap, cont−−.

VENTAJA

Todas las operaciones son O(1) y el espacio se reutiliza completo. Es la implementación que se usa en la práctica: los búferes circulares están en drivers, en audio y en comunicación serial precisamente por esto.

BÚFER CIRCULAR EN SISTEMAS REALES

Un búfer circular con un productor y un consumidor puede operar sin bloqueos si cada uno modifica solo su propio índice. Es una estructura que reaparecerá en Sistemas Embebidos al manejar UART e interrupciones.

PRÁCTICA

Implementar la cola circular con las dos estrategias de detección de llena y comparar el uso de memoria.