طابور

غالبًا ما يتم تدريسها جنبًا إلى جنب مع الأكوام، وقوائم الانتظار هي أيضًا أنواع بيانات مجردة يتم تعريفها من حيث العمليات التي نقوم بها فيها. الفرق الكبير بين المكدسات وقوائم الانتظار هو أن ترتيب العمليات التي تنفذها، قوائم الانتظار هي أول ما يدخل أولاً يخرج، أو FIFO، وهذا يعني أن أول شيء يدخل إلى قائمة الانتظار هو أول ما يخرج، في حين أن المكدسات تكون آخر ما يدخل أولًا، آخر ما نضعه هو أول ما سنعود إليه

يتم تعريف قوائم الانتظار من خلال ثلاث عمليات:

• قائمة الانتظار (ضع عنصرًا في نهاية قائمة الانتظار)
• dequeue (خذ عنصرًا من مقدمة قائمة الانتظار)
• نظرة خاطفة (احصل على العنصر الأول دون إزالته من قائمة الانتظار)

يمكننا أن نفكر في طوابير الانتظار كطوابير في مطعم، فعندما نصل إلى طابور، علينا أن ننتظر الجميع في المقدمة ليتم تقديم الخدمة لهم قبل أن يحين وقتنا.

تطبيق

إليك تنفيذ بسيط لقائمة الانتظار باستخدام مصفوفة:

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

توجد هنا تفاصيل تنفيذ مثيرة للاهتمام، عندما نقوم بإزالة عنصر من قائمة الانتظار، لأننا نقوم بإزالة عنصر من مقدمة قائمة الانتظار،
يجب علينا إعادة جميع العناصر التالية مرة أخرى، لذلك في هذا التنفيذ، تحتوي قائمة الانتظار على تعقيد O(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);
        }
    }
}

هنا يمكنك أن ترى أنه لا يوجد تكرار عند وضع قائمة الانتظار أو إزالة قائمة الانتظار، فنحن نقوم فقط بتعديل المؤشرات، ولهذا السبب يتمتع هذا التنفيذ بتعقيد زمني أفضل عند عملية إلغاء قائمة الانتظار.
هناك تحذير صغير، بفضل منطقة ذاكرة التخزين المؤقت، على الرغم من أن هذا التنفيذ أسرع في أسوأ الحالات، فمن المحتمل ألا يكون كذلك في معظمها.