대기줄

종종 스택과 함께 가르쳐지는 대기열도 추상 데이터 유형으로, 우리가 수행하는 작업의 관점에서 정의됩니다. 스택과 큐의 가장 큰 차이점은 그들이 적용하는 작업 순서입니다. 큐는 FIRST IN FIRST OUT(FIFO)입니다. 즉, 큐 내부로 들어가는 첫 번째 항목이 가장 먼저 나가는 반면 스택은 LAST IN입니다. 먼저 넣습니다. 따라서 마지막에 넣은 것이 가장 먼저 돌아올 것입니다.

큐는 세 가지 작업으로 정의됩니다.

• enqueue(큐의 끝에 요소 넣기)
• dequeue(큐 앞부분의 요소 가져오기)
• Peek(큐에서 제거하지 않고 첫 번째 요소 가져오기)

줄은 레스토랑의 줄로 생각할 수 있습니다. 줄을 서면 우리 시간이 되기 전에 앞에 있는 모든 사람이 음식을 받을 때까지 기다려야 합니다.

구현

다음은 배열을 사용한 간단한 대기열 구현입니다.

#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가 있어야 합니다. 그렇게 하면 간단히 이동할 수 있습니다. 이 모든 작업을 수행하는 대신 다음 항목에 대한 헤드 포인터입니다.

최고의 구현

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

여기서 대기열에 추가하거나 대기열에서 제거할 때 반복이 없다는 것을 알 수 있습니다. 우리는 단지 포인터를 조정하고 있으므로 이 구현이 대기열에서 제거할 때 더 나은 시간 복잡도를 갖는 이유입니다.
그러나 캐시 지역성 덕분에 이 구현이 최악의 경우 더 빠르더라도 대부분의 경우에는 그렇지 않을 수 있다는 작은 주의 사항이 있습니다.