FIFO (del inglés First In, First Out, en español "Primero en entrar, primero en salir") es una estructura de datos abstracta y un principio de gestión de colas donde el primer elemento que entra en el sistema o estructura es el primero en ser procesado y abandonarlo.
A diferencia de otras estructuras como LIFO (Last In, First Out), típica de las pilas, FIFO garantiza un orden estrictamente cronológico de atención. En informática e infraestructura de redes, este principio se aplica de forma masiva en la gestión de memoria RAM, sistemas operativos, colas de impresión, enrutadores y algoritmos de planificación de procesos (Scheduling).
¿Cómo funciona el principio FIFO?
El funcionamiento de una cola FIFO se rige por dos operaciones fundamentales y estrictas:
- Enqueue (Encolar): Consiste en añadir un nuevo elemento o tarea al final de la cola (por la parte trasera o tail).
- Dequeue (Desencolar): Consiste en extraer y procesar el elemento situado en el principio de la cola (por la parte delantera o head), liberando su espacio.
- Equidad (Fairness): Al no existir prioridades arbitrarias, ningún elemento puede ser relegado indefinidamente, garantizando que el primero en llegar sea siempre el primero en salir.
Comparativa de estructuras de datos y gestión
| Estructura / Principio | Orden de acceso | Operaciones principales | Caso de uso típico en informática |
|---|---|---|---|
| FIFO (Cola / Queue) | El primero que entra es el primero en salir (1 a 1) | enqueue() / dequeue() |
Colas de impresión, buffers de red, gestión de tareas en CPU |
| LIFO (Pila / Stack) | El último que entra es el primero en salir | push() / pop() |
Pila de llamadas de funciones, control de "Deshacer" (Ctrl+Z) |
| Round Robin | FIFO con asignación de tiempo rotativo (Quantum) | Asignación de turnos de CPU | Planificación de procesos multitarea en sistemas operativos |
| Priority Queue | Sale primero el elemento con mayor prioridad, no el de llegada | Inserción priorizada / Extracción del mayor | Gestión de paquetes QoS en redes, interrupciones de hardware |
Casos de uso principales en informática
| Ámbito | Descripción del beneficio de FIFO |
|---|---|
| Planificación de CPU (FIFO / FCFS) | En los algoritmos de planificación First-Come, First-Served, los procesos se ejecutan en la CPU estrictamente en el orden de llegada a la cola de listos. |
| Buffers de Red y E/S | Los búferes de los adaptadores de red o controladores de disco utilizan colas FIFO para asegurar que los paquetes de datos o bloques de lectura/escritura se transmitan en orden. |
| Colas de Impresión (Spooling) | Cuando varios usuarios envían documentos a una impresora compartida, el servidor de impresión los almacena en orden FIFO para imprimirlos de forma ordenada. |
Características principales:
- Mantiene estricta justicia cronológica (ningún elemento sufre "inanición" o starvation por prioridad).
- Su implementación en código es directa mediante arrays circulares o listas enlazadas.
- Tiene una complejidad temporal óptima de $O(1)$ tanto para inserciones como para extracciones en sus extremos.
- Es la base para el diseño de búferes de comunicación asíncrona.
- Evita el caos en la sincronización de flujos de datos continuos.
Analogía: Imagina la cola para comprar las entradas del cine en una taquilla. El primer cliente que llega a la fila se coloca el primero, compra su entrada y es atendido; los que van llegando después se colocan ordenadamente al final. Nadie se cuela y se respeta escrupulosamente el turno de llegada.
Actividad práctica
Objetivo:
Implementar y simular el comportamiento de una estructura FIFO básica utilizando un script en Python.
Tareas:
- Abre tu entorno de desarrollo o editor de código favorito (por ejemplo, VS Code o IDLE de Python).
- Crea un fichero nuevo llamado
cola_fifo.py. - Escribe un programa que utilice una lista de Python para simular una cola de impresión donde se añadan documentos con
append()y se procesen usandopop(0). - Ejecuta el script introduciendo al menos tres nombres de documentos diferentes e imprime el estado de la cola tras cada operación.
- Comprueba si el orden de salida coincide exactamente con el orden en el que fueron introducidos.
Preguntas de reflexión:
- ¿Qué diferencia conceptual clave existe entre una estructura FIFO (Cola) y una estructura LIFO (Pila)?
- ¿Por qué el uso exclusivo del algoritmo de planificación FIFO (FCFS) en sistemas operativos puede provocar el llamado "efecto convoy"?
- ¿Qué ocurre a nivel de eficiencia si implementamos una cola FIFO sobre una lista plana en lenguajes como Python o C eliminando siempre el primer elemento (`pop(0)`) en listas grandes?
- Menciona dos ejemplos cotidianos o de sistemas informáticos donde se aplique estrictamente una política FIFO.
- ¿En qué se diferencia una cola FIFO pura de una cola con prioridades (Priority Queue)?
Haz clic aquí para ver las soluciones y explicaciones
1. ¿Qué diferencia conceptual clave existe entre una estructura FIFO (Cola) y una estructura LIFO (Pila)?
En una estructura FIFO (First In, First Out), el elemento que entra primero es el primero en salir (orden de llegada estricto, como una cola de personas). En cambio, en una estructura LIFO (Last In, First Out), el último elemento en entrar es el primero en salir (como una pila de platos).
2. ¿Por qué el uso exclusivo del algoritmo de planificación FIFO (FCFS) en sistemas operativos puede provocar el llamado "efecto convoy"?
Porque si un proceso que requiere una cantidad masiva de tiempo de CPU llega primero a la cola, todos los procesos siguientes (incluso los muy cortos o interactivos) se quedan bloqueados esperando detrás de él, aumentando drásticamente el tiempo de espera medio del sistema.
3. ¿Qué ocurre a nivel de eficiencia si implementamos una cola FIFO sobre una lista plana en lenguajes como Python o C eliminando siempre el primer elemento (`pop(0)`) en listas grandes?
Se produce una gran penalización de rendimiento de orden $O(N)$. Al eliminar el elemento del índice 0 en un array dinámico o lista, todos los elementos restantes deben desplazarse una posición hacia la izquierda en memoria. Para optimizar esto, se deben usar estructuras especializadas como colas doblemente enlazadas o colas circulares ($O(1)$).
4. Menciona dos ejemplos cotidianos o de sistemas informáticos donde se aplique estrictamente una política FIFO.
Las colas de impresión de documentos en red y la gestión de paquetes de datos en un búfer de red tipo FIFO (como en colas de routers antes del enrutamiento).
5. ¿En qué se diferencia una cola FIFO pura de una cola con prioridades (Priority Queue)?
En una cola FIFO pura, el orden de salida depende exclusivamente del tiempo de llegada (el primero en llegar sale primero). En una cola con prioridades, cada elemento lleva asociado un nivel de importancia; aunque un elemento haya llegado antes, si entra otro con mayor prioridad, este último será atendido primero.