GUÍA 14-09-26 Estructuras de Datos

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

Colas: definición e implementación lineal

LA COLA

Estructura FIFO: el primero en entrar es el primero en salir. A diferencia de la pila, opera en dos extremos: se inserta por el final y se extrae por el frente.

OPERACIONES

• enqueue(x) — insertar al final.
• dequeue() — extraer del frente.
• front() — consultar el primero sin extraer.
• isEmpty() e isFull().

IMPLEMENTACIÓN CON ARREGLO Y DOS ÍNDICES

Se llevan frente y final. enqueue incrementa final y escribe; dequeue lee y incrementa frente.

EL PROBLEMA DE LA COLA LINEAL

Después de varias inserciones y extracciones, frente y final se corren hacia la derecha. Llega un momento en que final alcanza el fin del arreglo y la cola se reporta llena, aunque haya espacio libre al inicio.

Es el defecto que motiva la siguiente sesión. Vale la pena implementarlo y verlo fallar antes de aprender el arreglo circular: el problema se entiende mejor habiéndolo sufrido.

SOLUCIONES PARCIALES

• Recorrer todo al hacer dequeue: mantiene frente en 0 pero cuesta O(n) por extracción.
• Arreglo circular: reutiliza el espacio inicial con costo O(1). Es la solución correcta.

DÓNDE SE USAN LAS COLAS

• Planificación de procesos en un sistema operativo.
• Colas de impresión y de peticiones a un servidor.
• Búfer entre productor y consumidor.
• Recorrido en anchura de grafos y árboles.

PRÁCTICA

Implementar la cola lineal con arreglo y provocar deliberadamente el falso lleno.