File d'attente

Souvent enseignées avec les piles, les files d'attente sont également des types de données abstraits qui sont définis en termes des opérations que nous y effectuons. La grande différence entre les piles et les files d'attente réside dans l'ordre des opérations qu'elles appliquent. Les files d'attente sont PREMIER IN, PREMIER SORTI, ou FIFO, ce qui signifie que la première chose qui entre dans une file d'attente est la première à en sortir, tandis que les piles sont LAST IN. PREMIER SORTI, donc le dernier que nous mettons est le premier que nous reviendrons

Les files d'attente sont définies en termes de trois opérations :

• mettre en file d'attente (mettre un élément en fin de file d'attente)
• dequeue (prendre un élément du début de la file d'attente)
• peek (récupère le premier élément sans le supprimer de la file d'attente)

Nous pouvons considérer les files d'attente comme des files d'attente dans un restaurant. Lorsque nous faisons la queue, nous devons attendre que tout le monde devant nous soit servi avant que ce soit notre heure.

Mise en œuvre

Voici une implémentation simple d'une file d'attente utilisant un tableau :

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

Il y a un détail d'implémentation intéressant ici, chaque fois que nous sortons de la file d'attente, puisque nous supprimons un élément du début de la file d'attente,
nous devons déplacer tous les éléments suivants en arrière, donc dans cette implémentation, la file d'attente a une complexité de O(n), pour éviter cela, nous aurions besoin d'une LinkedList comme structure de données sous-jacente, ce faisant, nous pourrions simplement déplacer le pointeur de tête vers le suivant, au lieu d'avoir à faire tout cela.

La meilleure mise en œuvre

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

Ici, vous pouvez voir qu'il n'y a pas d'itération lors de la mise en file d'attente ou du retrait de la file d'attente, nous ajustons simplement les pointeurs, c'est pourquoi cette implémentation a une meilleure complexité temporelle lors du retrait de la file d'attente.
Il y a cependant une petite mise en garde, grâce à la localité du cache, même si cette implémentation est plus rapide dans le pire des cas, elle ne l'est probablement pas dans la plupart d'entre eux.