Fila

Muitas vezes ensinadas junto com pilhas, as filas também são tipos de dados abstratos que são definidos em termos das operações que realizamos nelas. A grande diferença entre pilhas e filas é que a ordem das operações que elas impõem, as filas são FIRST IN FIRST OUT, ou FIFO, o que significa que a primeira coisa que entra em uma fila é a primeira a sair, enquanto as pilhas são LAST IN PRIMEIRO A SAIR, então o último que colocamos é o primeiro que voltaremos

As filas são definidas em termos de três operações:

• enfileirar (colocar um elemento no final da fila)
• desenfileirar (pegar um elemento do início da fila)
• peek (obtém o primeiro elemento sem removê-lo da fila)

Podemos pensar nas filas como filas em um restaurante, quando entramos em uma fila, temos que esperar que todos na nossa frente sejam atendidos antes que chegue a nossa hora.

Implementação

Aqui está uma implementação simples de uma fila usando um array:

#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];
}

Há um detalhe de implementação interessante aqui, sempre que desenfileiramos, já que estamos removendo um elemento do início da fila,
devemos mover todos os elementos a seguir de volta, portanto, nesta implementação, a fila tem uma complexidade de O(n), para evitar isso, precisaríamos ter um LinkedList como estrutura de dados subjacente, ao fazer isso, poderíamos simplesmente mover o ponteiro principal para o próximo, em vez de ter que fazer tudo isso.

A melhor implementação

#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);
        }
    }
}

Aqui você pode ver que não há iteração ao enfileirar nem desenfileirar, estamos apenas ajustando os ponteiros, por isso esta implementação tem uma complexidade de tempo melhor ao desenfileirar.
Porém, há uma pequena ressalva: graças à localidade do cache, embora essa implementação seja mais rápida no pior caso, provavelmente não é na maioria deles.