队列数据结构

队列

通常与堆栈一起教授，队列也是，抽象数据类型，它们是根据我们在其中执行的操作定义的。堆栈和队列之间的最大区别在于，它们执行的操作顺序，队列是先进先出，即先进先出，这意味着，首先进入队列的东西首先出去，而堆栈是最后进入的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中文网其他相关文章！