대기열 데이터 구조

대기줄

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

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

• enqueue(큐의 끝에 요소 넣기)
• dequeue(큐 앞부분의 요소 가져오기)
• 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!