列

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

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

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

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

実装

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

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

最良の実装

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

ここでは、エンキューまたはデキュー時に反復が行われていないことがわかります。ポインタを調整しているだけです。そのため、この実装ではデキュー時の時間計算量がより優れています。
ただし、小さな注意点があります。この実装は最悪の場合でも高速ですが、キャッシュの局所性のおかげで、おそらくほとんどの実装では高速ではありません。