Struktur Data Giliran

Beratur

Sering diajar bersama tindanan, baris gilir juga, jenis data abstrak yang ditakrifkan dari segi operasi yang kami lakukan di dalamnya. Perbezaan besar antara tindanan dan baris gilir ialah, susunan operasi yang mereka laksanakan, baris gilir adalah FIRST IN FIRST OUT, atau FIFO, itu bermakna, perkara pertama yang masuk ke dalam baris gilir ialah yang pertama keluar, manakala tindanan adalah LAST IN DAHULU, jadi yang terakhir kita letak adalah yang pertama kita akan dapat balik

Baris gilir ditakrifkan dalam istilah tiga operasi:

• enqueue (letakkan elemen di hujung baris gilir)
• dequeue (ambil elemen bahagian hadapan baris gilir)
• intip (dapatkan elemen pertama sambil tidak mengeluarkannya daripada baris gilir)

Kita boleh menganggap barisan sebagai barisan di restoran, apabila kita masuk ke barisan, kita perlu menunggu semua orang di hadapan untuk dihidangkan sebelum tiba masa kita.

Perlaksanaan

Berikut ialah pelaksanaan mudah baris gilir menggunakan tatasusunan:

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

Terdapat perincian pelaksanaan yang menarik di sini, setiap kali kami menunda giliran, kerana kami mengalih keluar elemen dari hadapan baris gilir,
kita mesti memindahkan semua elemen berikut kembali, jadi dalam pelaksanaan ini, baris gilir mempunyai kerumitan O(n), untuk mengelakkannya, kita perlu mempunyai LinkedList sebagai struktur data asas, dengan melakukannya, kita hanya boleh bergerak penunjuk kepala ke seterusnya, bukannya perlu melakukan semua ini.

Pelaksanaan terbaik

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

Di sini anda dapat melihat bahawa tiada lelaran semasa beratur atau nyah gilir, kami hanya melaraskan penunjuk, jadi itulah sebabnya pelaksanaan ini mempunyai kerumitan masa yang lebih baik semasa nyah gilir.
Terdapat kaveat kecil, terima kasih kepada lokaliti cache walaupun pelaksanaan ini lebih pantas dalam kes yang paling teruk, ia mungkin tidak berlaku dalam kebanyakannya.

Atas ialah kandungan terperinci Struktur Data Giliran. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!