Cola

A menudo se enseñan junto con las pilas, las colas también son tipos de datos abstractos que se definen en términos de las operaciones que realizamos en ellas. La gran diferencia entre pilas y colas es el orden de las operaciones que imponen, las colas son PRIMERO EN ENTRAR, PRIMERO EN SALIR, o FIFO, lo que significa que lo primero que entra a una cola es el primero en salir, mientras que las pilas son ÚLTIMOS EN ENTRAR. PRIMERO EN SALIR, por lo que lo último que pongamos será el primero que recuperaremos

Las colas se definen en términos de tres operaciones:

• poner en cola (poner un elemento al final de la cola)
• sacar de la cola (tomar un elemento del principio de la cola)
• mirar (obtener el primer elemento sin eliminarlo de la cola)

Podemos pensar en las colas como filas en un restaurante, cuando nos ponemos en fila, tenemos que esperar a todos los que están en nuestro frente para que nos atiendan antes de que llegue nuestro momento.

Implementación

Aquí hay una implementación simple de una cola usando una matriz:

#include 
#include 
#include 

#define QUEUE_LEN 1024

struct queue_t {
    uint32_t data[QUEUE_LEN];
    size_t ptr;
};

void enqueue(struct queue_t *queue, uint32_t value)
{
    if (queue->ptr   1 >= QUEUE_LEN)
    {
        fprintf(stderr, "The queue is full");
        exit(1);
    }

    queue->data[queue->ptr  ] = value;
}

uint32_t dequeue(struct queue_t *queue)
{
    if (queue->ptr == 0)
    {
        fprintf(stderr, "Cannot dequeue empty queue");
        exit(1);
    }
    uint32_t val = queue->data[0];

    for (size_t i = 1; i ptr;   i)
    {
        queue->data[i - 1] = queue->data[i];
    }
    queue->ptr--;
    return val;
}

uint32_t peek(struct queue_t *queue)
{
    if (queue->ptr == 0)
    {
        fprintf(stderr, "Cannot peek empty queue");
        exit(1);
    }
    return queue->data[0];
}

Aquí hay un detalle de implementación interesante, cada vez que retiramos la cola, ya que estamos eliminando un elemento del frente de la cola,
debemos mover todos los elementos siguientes hacia atrás, por lo que en esta implementación, la cola tiene una complejidad de O(n), para evitar eso, necesitaríamos tener una LinkedList como estructura de datos subyacente, al hacerlo, podríamos simplemente mover el puntero principal al siguiente, en lugar de tener que hacer todo esto.

La mejor implementación

#include 
#include 
#include 

struct node_t {
    uint32_t data;
    struct node_t *next;
};

struct linked_list_t {
    struct node_t *head;
    struct node_t *tail;
    size_t len;
};

void enqueue(struct linked_list_t *list, uint32_t data)
{
    struct node_t *node = malloc(sizeof(struct node_t));

    node->data = data;
    node->next = NULL;

    list->len  ;

    if (list->len == 1)
    {
        list->head = list->tail = node;
        return;
    }

    list->tail->next = node;
    list->tail = node;
}

uint32_t dequeue(struct linked_list_t *list)
{
    if (list->len == 0)
    {
        fprintf(stderr, "Cannot dequeue empty list");
        exit(1);
    }

    struct node_t *aux = list->head;
    uint32_t data = aux->data;

    list->head = list->head->next;
    list->len--;
    free(aux);

    return data;
}

uint32_t peek(struct linked_list_t *list)
{
    if (list->len == 0)
    {
        fprintf(stderr, "Cannot peek empty list");
        exit(1);
    }

    return list->head->data;
}

void list_free(struct linked_list_t *list)
{
    struct node_t *prev = NULL;
    struct node_t *aux = list->head;
    while (aux != NULL)
    {
        prev = aux;
        aux = aux->next;
        if (prev) {
            free(prev);
        }
    }
}

Aquí puede ver que no hay iteración al poner en cola ni al quitar la cola, solo estamos ajustando punteros, por eso esta implementación tiene una mejor complejidad de tiempo al quitar la cola.
Sin embargo, hay una pequeña advertencia: gracias a la localidad de caché, aunque esta implementación es más rápida en el peor de los casos, probablemente no lo sea en la mayoría de ellos.