Colas (Queues)

 ¿Que son las colas o queues?

Es una estructura de datos cuyos elementos siguen la regla FIFO (First In First Out) en español, el primero en entrar es el primero en salir. Como se dijo anteriormente, la implementación tanto de las pilas y colas se realiza mediante una lista enlazada.

Tipos de colas

  • Cola simple: Es la implementación más básica, que sigue estrictamente el principio FIFO. Los elementos se añaden al final y se eliminan al principio.
  • Cola circular: Similar a la lineal, pero el último elemento se conecta de nuevo al primero, formando un anillo. Esto permite reutilizar el espacio de los elementos que ya han sido retirados.
  • Cola de prioridad: Cada elemento tiene una prioridad asociada. Los elementos con mayor prioridad se procesan primero, independientemente de su orden de llegada.
  • Cola doble (Deque): Permite insertar y eliminar elementos por ambos extremos (frente y final). Esta estructura combina las capacidades de una pila y una cola en una sola. 

Implementacion de una cola simple

Encolar (Insertar nodo)
Consiste en insertar el nodo al final de la cola, para esto el ultimo nodo en la cola debe apuntar a este nuevo nodo.
void encolar(Cola* cola)
{
    Nodo* nuevo = crear_nodo();
    if (cola->primero == NULL)
    {
        // Tanto el ultimo como el primero en la cola seran el nuevo al ser el unico
        cola->primero = nuevo;
        cola->ultimo = nuevo;
        return;
    }
    cola->ultimo->sig = nuevo;
    cola->ultimo = nuevo;
}
Desencolar (Eliminar nodo)
Consiste en eliminar el primer nodo en cola, para esto el puntero primero o cabeza debera apuntar al segundo en cola.
void desencolar(Cola* cola)
{
    // Si no existe la cola entonces abortamos
    if (cola->primero == NULL) {
        return;
    }

    // Utilizamos un auxiliar para guardar la direccion de memoria del nodo que queremos eliminar
    Nodo* eliminado = cola->primero;

    cola->primero = eliminado->sig; // El segundo en la cola pasa a ser el primero

    if (cola->primero == NULL) {
        cola->ultimo = NULL;
    }

    // Ahora si liberamos el espacio de memoria y eliminamos el nodo
    free(eliminado);
    eliminado = NULL;
    cola->size--;
}
Despachar
En ciertas ocasiones se realiza esta operación, que consiste en retornar la información que guardaba el nodo antes de eliminar, para esto, tomando como base la función desencolar o eliminar nodo, debemos recuperar la información antes de eliminar el nodo y retornar los datos recuperados después de desencolar el nodo.

Programa ejemplo del uso de las colas
El programa es un administrador de tareas que utiliza una cola con prioridad segun lo importante o urgente que es realizar cada tarea.


Referencias

Comentarios

Publicar un comentario

Entradas populares de este blog

Pilas (Stacks)

Imagen
  ¿Que son las pilas o stacks? Las pilas siguen el principio: Last In First Out (LIFO), o en español ultimo el en entrar es el primero en salir. La gran diferencia con las colas o las listas radica en que la inserción y eliminación de elementos se realizara siempre al principio de la pila, es decir, el nuevo elemento que se añadirá siempre sera la cima la pila. El equivalente a la cabeza de la lista en las pilas seria la cima. Al momento de implementar una pila o una cola se utiliza como base una lista enlazada. Realmente funcionan casi igual, ya que tanto las listas como las colas funcionan con nodos que poseen un puntero hacia el siguiente nodo.  Esto también implica que ya no necesitaremos un puntero hacia la cola o ultimo elemento de la lista, porque únicamente necesitaremos modificar la cima de la pila. Implementacion de una pila Insercion de un nodo (Apilar) void insertar_nodo(Pila** cima, int valor) {     // Reserva de memoria para el nuevo nodo     ...
Leer más