Warteschlange

Warteschlangen werden oft zusammen mit Stapeln gelehrt und sind auch abstrakte Datentypen, die anhand der Operationen definiert werden, die wir in ihnen ausführen. Der große Unterschied zwischen Stapeln und Warteschlangen besteht in der Reihenfolge der Vorgänge, die sie erzwingen. Warteschlangen sind FIRST IN FIRST OUT oder FIFO, was bedeutet, dass das Erste, was in eine Warteschlange gelangt, auch als Erstes wieder herausgeht, während Stapel als LAST IN gelten FIRST OUT, also ist das Letzte, das wir setzen, das Erste, das wir zurückbekommen

Warteschlangen werden anhand von drei Vorgängen definiert:

• enqueue (ein Element ans Ende der Warteschlange stellen)
• aus der Warteschlange entfernen (ein Element vom Anfang der Warteschlange nehmen)
• peek (Erstes Element abrufen, ohne es aus der Warteschlange zu entfernen)

Wir können uns Warteschlangen wie Warteschlangen in einem Restaurant vorstellen. Wenn wir in eine Warteschlange kommen, müssen wir darauf warten, dass alle an unserer Rezeption bedient werden, bevor es unsere Zeit ist.

Durchführung

Hier ist eine einfache Implementierung einer Warteschlange mithilfe eines Arrays:

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

Hier gibt es ein interessantes Implementierungsdetail: Wann immer wir die Warteschlange verlassen, entfernen wir ein Element vom Anfang der Warteschlange,
Wir müssen alle folgenden Elemente zurückverschieben, daher hat die Warteschlange in dieser Implementierung eine Komplexität von O(n). Um dies zu vermeiden, müssten wir eine LinkedList als zugrunde liegende Datenstruktur haben. Auf diese Weise könnten wir einfach verschieben der Kopfzeiger auf den nächsten, anstatt das alles tun zu müssen.

Die beste Umsetzung

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

Hier können Sie sehen, dass es weder beim Einreihen noch beim Entfernen aus der Warteschlange eine Iteration gibt. Wir passen lediglich Zeiger an. Aus diesem Grund weist diese Implementierung beim Entfernen aus der Warteschlange eine bessere zeitliche Komplexität auf.
Es gibt jedoch eine kleine Einschränkung: Dank der Cache-Lokalität ist diese Implementierung zwar im schlimmsten Fall schneller, in den meisten Fällen jedoch wahrscheinlich nicht.