佇列資料結構

佇列

通常與堆疊一起教授，隊列也是，抽象資料類型，它們是根據我們在其中執行的操作定義的。堆疊和佇列之間的最大區別在於，它們執行的操作順序，隊列是先進先出（FIRST IN FIRST OUT），即先進先出（FIFO），這意味著，首先進入隊列的東西最先出去，而堆疊是最後進入的FIRST OUT，所以我們最後放入的就是我們第一個回傳的

隊列由三個操作定義：

• 入隊（將元素放入隊列結束時）
• 出隊（取出隊伍前面的一個元素）
• peek（取得第一個元素，但不將其從佇列中刪除）

我們可以把隊列想像成餐廳裡的隊伍，當我們排隊時，我們必須等待前面的每個人都得到服務才能到我們的時間。

執行

這是使用陣列的佇列的簡單實作：

#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>

#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 < queue->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)，為了避免這種情況，我們需要有一個LinkedList 作為底層資料結構，透過這樣做，我們可以只移動指向下一個的頭指針，而不必執行所有這些操作。

最佳實施

#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>

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

這裡可以看到，入隊和出隊時都沒有迭代，我們只是調整指針，所以這個實現在出隊時有更好的時間複雜度。
不過，有一個小警告，由於快取局部性，即使這種實現在最壞的情況下更快，但在大多數情況下可能不是這樣。

以上是佇列資料結構的詳細內容。更多資訊請關注PHP中文網其他相關文章！