En la ciencia de la computación, las estructuras de datos juegan un papel crucial en la organización y gestión eficiente de la información. Entre estas estructuras, la cola (también conocida como queue en inglés) es una de las más fundamentales y ampliamente utilizadas. A lo largo de este artículo, exploraremos qué es una cola, cómo funciona y cuáles son sus aplicaciones más comunes.
Definición de una cola
Una cola es una estructura de datos lineal que sigue una metodología de acceso conocida como FIFO (First In, First Out), lo que significa que el primer elemento que entra en la cola es el primero en salir. Este comportamiento es análogo a una fila de personas en una taquilla: la primera persona que llega es la primera en ser atendida, mientras que las personas que llegan después deben esperar su turno.
Una cola se caracteriza principalmente por dos operaciones básicas:
Encolar (enqueue): Insertar un nuevo elemento al final de la cola.
Desencolar (dequeue): Eliminar el primer elemento de la cola, que es el que ha estado en la estructura durante más tiempo.
Operaciones en una cola
Existen varias operaciones que se pueden realizar en una estructura de datos tipo cola. Las más comunes son:
Encolar (enqueue): Añade un elemento al final de la cola. Si la cola tiene un límite en su tamaño y ya está llena, esta operación puede fallar, dependiendo de la implementación.
Desencolar (dequeue): Elimina el elemento en la parte frontal de la cola y lo devuelve. Si la cola está vacía, esta operación puede devolver un valor nulo o generar una excepción, dependiendo de la implementación.
Frente (front o peek): Permite acceder al primer elemento de la cola sin eliminarlo.
Vacía (isEmpty): Verifica si la cola no contiene ningún elemento.
Tamaño (size): Devuelve la cantidad de elementos presentes en la cola.
Estas operaciones permiten gestionar el comportamiento básico de la cola y son fundamentales para su implementación en diferentes escenarios.
Tipos de colas
Existen diferentes variaciones de la estructura de datos cola, cada una con características particulares según el caso de uso:
Cola simple: Es la implementación básica de una cola que sigue el principio FIFO. Los elementos se añaden al final y se eliminan desde el frente.
Cola circular: En esta versión, el último elemento de la cola está conectado al primero, formando una estructura circular. Esto permite un uso más eficiente de la memoria, ya que cuando se elimina un elemento del frente, el espacio liberado puede ser reutilizado.
Cola de prioridad: Los elementos en la cola no se organizan solo por el orden de llegada, sino también por su prioridad. Los elementos con mayor prioridad se procesan antes que los de menor prioridad, independientemente de cuándo hayan llegado.
Cola doble (deque): Esta estructura permite insertar y eliminar elementos tanto por el frente como por el final de la cola, lo que le proporciona una gran flexibilidad.
Implementación de una cola
Las colas pueden implementarse utilizando diferentes estructuras subyacentes, como arreglos (vectores) o listas enlazadas.
Con arreglos: La implementación con arreglos es sencilla y rápida. Sin embargo, el tamaño de la cola puede estar limitado por el tamaño del arreglo. Además, si se realiza el desencolado, los elementos deben moverse hacia adelante, lo que puede ser ineficiente.
Con listas enlazadas: La implementación con listas enlazadas resuelve el problema de mover elementos, ya que solo se cambia la referencia al siguiente nodo. Sin embargo, implica un mayor uso de memoria debido al almacenamiento de punteros.
Ejemplo de codificación de una estructura de datos cola en C
Mi propósito es mostraros una estructura de datos típica escrita en C. A continuación os muestro el fichero .h y .c que desarrollará esta estructura que ya hemos descrito en los apartados anteriores y que podéis usar libremente en vuestros propios desarrollos.
#ifndef C1CP_tip_TYPO
#define C1CP_tip_TYPO
struct c_int_typo {
int x;
}
typedef struct c_int_ele *c_int;
c_int c_nuevo ();
int c_vacia ( c_int c );
void c_mete ( c_int *c, c_int_typo e );
void c_saca ( c_int *c, c_int_typo *e );
void c_destruye ( c_int *c );
c_int c_copia ( c_int c );
#endif#include <stdlib.h>
#include <stdio.h>
#include "colaenteros.h"
struct c_int_ele {
struct c_int_typo val;
struct c_int_ele *sig;
}
c_int c_nuevo () {
return NULL;
}
int c_vacia ( c_int c ) {
return ( c==NULL);
}
void c_mete ( c_int *c, c_int_typo e ) {
c_int nuevo, ultimo;
nuevo = ( struct c_int_ele * )
malloc ( sizeof ( struct c_int_ele ) );
if ( !nuevo ) {
fprintf ( stderr, "c_mete: no hay memorio. \n" );
exit (1);
}
nuevo->val = e;
nuevo->sig = NULL;
if ( !*c ) *c = nuevo;
else {
for ( ultimo=*c; ultimo->sig; ultimo = ultimo->sig );
ultimo->sig = nuevo;
}
}
void c_saca ( c_int *c, c_int_typo *e ) {
c_int nuevo;
if ( !*c ) {
fprintf ( stderr, "c_saca: la cola está vacía \n" );
exit ( 1 );
}
viejo = *c;
*e = viejo->val;
*c = viejo->sig;
free ( viejo );
}
void c_destruye ( c_int *c ) {
c_int viejo;
while ( *c ) {
viejo = *c;
*c =(*c)->viejo;
free ( viejo );
}
}
c_int c_copia ( c_int c ) {
c_int b, corr, nuevo;
b = NULL;
if ( c ) {
nuevo ( struct c_int_ele* )
malloc ( sizeof ( struct c_int_ele ));
if ( !nuevo ) {
fprintf ( stderr, "c_copia: no hay memoria \n" );
exit (1);
}
nuevo->val = c->val;
b = corr = nuevo;
c = c->sig;
while ( c ) {
nuevo = ( struct c_int_ele *)
malloc ( sizeof ( struct c_int_ele ));
if ( !nuevo ) {
fprintf ( stderr, "c_copia: no hay memoria \n" );
exit (11);
}
nuevo->val = c->val;
corr = corr->sig = nuevo;
c = c->sig;
}
corr->sig = NULL;
}
return (b);
}Explicando el código paso a paso
La primera función trata de crear una nueva estructura de datos Cola. Es muy simple. Inicializamos el puntero a NULL de la misma forma en la que se inicializa cualquier variable. No hay mucho más que explicar.
c_int c_nuevo () {
return NULL;
}La siguiente función devuelve una estructura lógica con valor true si la estructura de datos Cola es igual NULL ( está vacía ) o false, si es distinto de NULL ( en caso de que no esté vacía );
int c_vacia ( c_int c ) {
return ( c==NULL);
}El siguiente procedimiento se encarga de insertar un nuevo nodo en la cola, el cuál tendrá dos campos: el valor y un puntero al siguiente nodo. En este procedimiento se pasa la cola como un argumento por referencia y el nodo que contiene el valor y el puntero al nodo siguiente por valor.
Paso a paso: se reserva memoria para un nuevo nodo ( un nuevo elemento de la cola). Se valorará si existe memoria suficiente para hacerlo. De lo contrario, salimos del programa.
Ahora, en caso de que la cola esté vacía, se le agrega el elemento o nodo al frente, de lo contrario, se añadirá al final de la estructura de datos usando un bucle for para hacerlo.
void c_mete ( c_int *c, c_int_typo e ) {
c_int nuevo, ultimo;
nuevo = ( struct c_int_ele * )
malloc ( sizeof ( struct c_int_ele ) );
if ( !nuevo ) {
fprintf ( stderr, "c_mete: no hay memorio. \n" );
exit (1);
}
nuevo->val = e;
nuevo->sig = NULL;
if ( !*c ) *c = nuevo;
else {
for ( ultimo=*c; ultimo->sig; ultimo = ultimo->sig );
ultimo->sig = nuevo;
}
}En este procedimiento, sacaremos un elemento o nodo de la Cola. La idea es verificar primero si la cola está vacía o no. En caso positivo, se imprimirá un mensaje de advertencia y se saldrá del programa.
A continuación, en caso de que la Cola no esté vacía, se eliminará el nodo actualizando los punteros. Finalmente se eliminará el nodo con el procedimiento free.
void c_saca ( c_int *c, c_int_typo *e ) {
c_int nuevo;
if ( !*c ) {
fprintf ( stderr, "c_saca: la cola está vacía \n" );
exit ( 1 );
}
viejo = *c;
*e = viejo->val;
*c = viejo->sig;
free ( viejo );
}Este procedimiento, al que se le pasa la cola por referencia como argumento, lo que se hace es eliminar nodo a nodo la Cola y eliminado cada uno de ellos con el procedimiento free.
void c_destruye ( c_int *c ) {
c_int viejo;
while ( *c ) {
viejo = *c;
*c =(*c)->viejo;
free ( viejo );
}
}En esta última función, devolvemos una copia de la Cola que se le pasa como argumento por valor ( no por referencia porque no se la va a modificar ).
Inicializamos la cola copia y vamos a iniciar un proceso en el que reservamos memoria para el primer nodo o elemento de la Cola. Si no hay memoria, imprimieremos un mensaje que informe de ello y saldremos del programa. En caso de que no haya problemas, actualizaremos los punteros y los valores de los nodos. Iniciamos un bucle while en el que iremos copiando uno a uno cada uno de los elementos o nodos de la Cola.
Finalmente devolvemos mediante return la Cola copia.
c_int c_copia ( c_int c ) {
c_int b, corr, nuevo;
b = NULL;
if ( c ) {
nuevo ( struct c_int_ele* )
malloc ( sizeof ( struct c_int_ele ));
if ( !nuevo ) {
fprintf ( stderr, "c_copia: no hay memoria \n" );
exit (1);
}
nuevo->val = c->val;
b = corr = nuevo;
c = c->sig;
while ( c ) {
nuevo = ( struct c_int_ele *)
malloc ( sizeof ( struct c_int_ele ));
if ( !nuevo ) {
fprintf ( stderr, "c_copia: no hay memoria \n" );
exit (11);
}
nuevo->val = c->val;
corr = corr->sig = nuevo;
c = c->sig;
}
corr->sig = NULL;
}
return (b);
}Aplicaciones comunes de las colas
Las colas tienen una amplia variedad de aplicaciones en informática y en la vida diaria, ya que modelan eficazmente situaciones en las que se requiere un procesamiento secuencial. Algunas de las aplicaciones más comunes incluyen:
Sistemas de impresión: Cuando varias personas envían documentos a una impresora compartida, estos se almacenan en una cola. El primer documento enviado es el primero en imprimirse.
Gestión de procesos en sistemas operativos: Los sistemas operativos utilizan colas para manejar procesos en ejecución. Por ejemplo, en un sistema de multitarea, los procesos que esperan por tiempo de CPU se gestionan en una cola de prioridad.
Colas de espera en redes: En las redes de comunicación, los paquetes de datos que se transmiten por la red a menudo se colocan en colas para ser enviados en el orden en que llegaron.
Simulación de colas en sistemas: Las colas se utilizan para modelar líneas de espera en simulaciones, como en supermercados o bancos, donde el servicio se proporciona en el orden en que los clientes llegan.
La cola es una estructura de datos fundamental que organiza la información de manera que el primer elemento en ingresar es el primero en ser procesado, siguiendo el principio FIFO. Su simple pero efectivo mecanismo de operación hace que las colas sean indispensables en la resolución de problemas que requieren procesamiento secuencial o gestión de recursos en orden. Las colas son ampliamente utilizadas en diversas áreas, desde la programación de sistemas hasta la optimización de procesos en la vida real.
Comprender el funcionamiento y las variaciones de esta estructura de datos es esencial para todo programador o profesional que trabaja con la gestión de datos y recursos.