キューのデータ構造

列

スタックと一緒に教えられることが多いキューは、そこで実行される操作の観点から定義される抽象データ型でもあります。スタックとキューの大きな違いは、強制される操作の順序です。キューは FIRST IN FIRST OUT (FIFO) です。つまり、最初にキュー内に入ったものが最初に出力されますが、スタックは LAST IN です。 FIRST OUT、つまり最後に入力したものが最初に返されます

キューは 3 つの操作で定義されます:

• エンキュー (キューの最後に要素を置きます)
• デキュー (キューの先頭の要素を取得します)
• ピーク (キューから削除せずに最初の要素を取得します)

行列はレストランの行列と考えることができます。列に並ぶと、自分の時間になる前に前に並んでいる全員がサービスを受けるのを待たなければなりません。

実装

ここでは、配列を使用したキューの簡単な実装を示します。

#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 を使用する必要があります。そうすることで、単に移動するだけで済みます。これをすべて実行する代わりに、次への head ポインタを使用します。

最良の実装

#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 中国語 Web サイトの他の関連記事を参照してください。