कतार

अक्सर स्टैक के साथ-साथ कतारें भी सिखाई जाती हैं, अमूर्त डेटा प्रकार जो हमारे द्वारा उनमें किए जाने वाले संचालन के संदर्भ में परिभाषित होते हैं। स्टैक और क्यू के बीच बड़ा अंतर यह है कि वे संचालन के क्रम को लागू करते हैं, क्यू फर्स्ट इन फर्स्ट आउट या फीफो होते हैं, इसका मतलब है कि, कतार के अंदर जो पहली चीज आती है वह सबसे पहले बाहर जाती है, जबकि स्टैक सबसे बाद में आते हैं। सबसे पहले बाहर, इसलिए जो अंतिम हम डालेंगे वही पहला होगा जिसे हम वापस प्राप्त करेंगे

क्यू को तीन परिचालनों की अवधि में परिभाषित किया गया है:

• पंक्तिबद्ध करें (कतार के अंत में एक तत्व रखें)
• डीक्यू (कतार के सामने का एक तत्व लें)
• झांकें (पहला तत्व प्राप्त करें, उसे कतार से न हटाएं)

हम कतारों को एक रेस्तरां में लगने वाली कतारों के रूप में सोच सकते हैं, जब हम एक कतार में लगते हैं, तो हमें अपने समय से पहले सेवा पाने के लिए अपने सामने खड़े सभी लोगों का इंतजार करना पड़ता है।

कार्यान्वयन

यहां एक सरणी का उपयोग करके कतार का एक सरल कार्यान्वयन है:

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

यहां आप देख सकते हैं कि कतारबद्ध करते समय या कतारबद्ध करते समय कोई पुनरावृत्ति नहीं होती है, हम केवल पॉइंटर्स को समायोजित कर रहे हैं, इसलिए इस कार्यान्वयन में कतारबद्ध करते समय बेहतर समय जटिलता होती है।
हालाँकि, एक छोटी सी चेतावनी है, कैश इलाके के कारण भले ही यह कार्यान्वयन सबसे खराब स्थिति में तेज़ है, यह संभवतः उनमें से अधिकांश में नहीं है।