ডেটা স্ট্রাকচার: লিংকড লিস্ট, স্ট্যাক, কিউ, ট্রি

ডেটা স্ট্রাকচার হলো ডেটা সংগঠিত করার একটি পদ্ধতি, যা কম্পিউটারে ডেটা সংরক্ষণ ও পরিচালনা করার জন্য ব্যবহৃত হয়। এখানে আমরা কিছু সাধারণ ডেটা স্ট্রাকচার যেমন লিংকড লিস্ট, স্ট্যাক, কিউ, এবং ট্রি নিয়ে আলোচনা করব।

১. লিংকড লিস্ট (Linked List)

লিংকড লিস্ট হলো একটি ডেটা স্ট্রাকচার যা একটি সিরিজ নোড দ্বারা গঠিত, যেখানে প্রতিটি নোডের মধ্যে ডেটা এবং পরবর্তী নোডের ঠিকানা থাকে। এটি ডেটাকে সংরক্ষণ করার জন্য একটি লিনিয়ার পদ্ধতি। লিংকড লিস্টের প্রধান সুবিধা হলো এর আকার পরিবর্তন করা সহজ।

গঠন:

struct Node {
    int data;                // নোডের ডেটা
    struct Node* next;      // পরবর্তী নোডের পয়েন্টার
};

উদাহরণ: লিংকড লিস্ট তৈরি ও প্রদর্শন

#include <stdio.h>
#include <stdlib.h>

// নোডের গঠন
struct Node {
    int data;
    struct Node* next;
};

// নতুন নোড তৈরি করা
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// লিংকড লিস্টে ডেটা যোগ করা
void insertNode(struct Node** head, int data) {
    struct Node* newNode = createNode(data);
    newNode->next = *head; // নতুন নোডের পরবর্তী নোড হবে পুরনো হেড
    *head = newNode; // হেড আপডেট করা
}

// লিংকড লিস্ট প্রদর্শন করা
void displayList(struct Node* node) {
    while (node != NULL) {
        printf("%d -> ", node->data);
        node = node->next;
    }
    printf("NULL\n");
}

int main() {
    struct Node* head = NULL; // লিংকড লিস্টের হেড
    insertNode(&head, 1);
    insertNode(&head, 2);
    insertNode(&head, 3);
    displayList(head); // লিংকড লিস্ট প্রদর্শন
    return 0;
}

আউটপুট:

3 -> 2 -> 1 -> NULL

২. স্ট্যাক (Stack)

স্ট্যাক হলো একটি লাস্ট ইন ফার্স্ট আউট (LIFO) ডেটা স্ট্রাকচার, যার অর্থ হলো যে ডেটা সর্বশেষে স্ট্যাকে যুক্ত হয়, সেটিই প্রথমে সরানো হয়। এটি সাধারণত মেমোরি ব্যবস্থাপনা, ফাংশন কল ট্রেস, এবং এক্সপ্রেশন মূল্যায়ন করতে ব্যবহৃত হয়।

গঠন:

#define MAX 100

struct Stack {
    int items[MAX];
    int top;
};

উদাহরণ: স্ট্যাক তৈরি ও ব্যবহার

#include <stdio.h>
#include <stdlib.h>

#define MAX 100

struct Stack {
    int items[MAX];
    int top;
};

// স্ট্যাক ইনিশিয়ালাইজ
void initStack(struct Stack* s) {
    s->top = -1;
}

// স্ট্যাকে ডেটা যোগ করা
void push(struct Stack* s, int data) {
    if (s->top == MAX - 1) {
        printf("Stack overflow!\n");
    } else {
        s->items[++s->top] = data;
    }
}

// স্ট্যাক থেকে ডেটা সরানো
int pop(struct Stack* s) {
    if (s->top == -1) {
        printf("Stack underflow!\n");
        return -1;
    } else {
        return s->items[s->top--];
    }
}

// স্ট্যাকের শীর্ষ মান দেখানো
int peek(struct Stack* s) {
    if (s->top != -1) {
        return s->items[s->top];
    }
    return -1;
}

int main() {
    struct Stack s;
    initStack(&s);
    push(&s, 10);
    push(&s, 20);
    push(&s, 30);
    printf("Top item: %d\n", peek(&s)); // শীর্ষ মান দেখানো
    printf("Popped item: %d\n", pop(&s)); // স্ট্যাক থেকে সরানো
    printf("Top item after pop: %d\n", peek(&s));
    return 0;
}

আউটপুট:

Top item: 30
Popped item: 30
Top item after pop: 20

৩. কিউ (Queue)

কিউ হলো একটি ফার্স্ট ইন ফার্স্ট আউট (FIFO) ডেটা স্ট্রাকচার, যার অর্থ হলো যে ডেটা প্রথমে যুক্ত হয়, সেটিই প্রথমে সরানো হয়। এটি সাধারণত প্রক্রিয়া সময়সূচী, ডেটা স্ট্রিম প্রক্রিয়াকরণ, এবং অন্যান্য অ্যাসিনক্রোনাস কার্যক্রমে ব্যবহৃত হয়।

গঠন:

#define MAX 100

struct Queue {
    int items[MAX];
    int front, rear;
};

উদাহরণ: কিউ তৈরি ও ব্যবহার

#include <stdio.h>
#include <stdlib.h>

#define MAX 100

struct Queue {
    int items[MAX];
    int front, rear;
};

// কিউ ইনিশিয়ালাইজ
void initQueue(struct Queue* q) {
    q->front = -1;
    q->rear = -1;
}

// কিউতে ডেটা যোগ করা
void enqueue(struct Queue* q, int data) {
    if (q->rear == MAX - 1) {
        printf("Queue overflow!\n");
    } else {
        if (q->front == -1) {
            q->front = 0;
        }
        q->items[++q->rear] = data;
    }
}

// কিউ থেকে ডেটা সরানো
int dequeue(struct Queue* q) {
    if (q->front == -1) {
        printf("Queue underflow!\n");
        return -1;
    } else {
        int data = q->items[q->front++];
        if (q->front > q->rear) {
            q->front = q->rear = -1; // কিউ খালি হলে
        }
        return data;
    }
}

// কিউয়ের শীর্ষ মান দেখানো
int peek(struct Queue* q) {
    if (q->front != -1) {
        return q->items[q->front];
    }
    return -1;
}

int main() {
    struct Queue q;
    initQueue(&q);
    enqueue(&q, 10);
    enqueue(&q, 20);
    enqueue(&q, 30);
    printf("Front item: %d\n", peek(&q)); // শীর্ষ মান দেখানো
    printf("Dequeued item: %d\n", dequeue(&q)); // কিউ থেকে সরানো
    printf("Front item after dequeue: %d\n", peek(&q));
    return 0;
}

আউটপুট:

Front item: 10
Dequeued item: 10
Front item after dequeue: 20

৪. ট্রি (Tree)

ট্রি হলো একটি হায়ারার্কিকাল ডেটা স্ট্রাকচার, যেখানে প্রতিটি নোডে ডেটা থাকে এবং একটি বা একাধিক সন্তানের নোড থাকতে পারে। ট্রি ডেটা স্ট্রাকচার সাধারণত বিভিন্ন তথ্য সংগঠিত করার জন্য ব্যবহৃত হয়।

গঠন:

struct Node {
    int data;
    struct Node* left;  // বাম সন্তান
    struct Node* right; // ডান সন্তান
};

উদাহরণ: একটি বাইনারি ট্রি তৈরি ও প্রদর্শন

#include <stdio.h>
#include <stdlib.h>

// নোডের গঠন
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// নতুন নোড তৈরি করা
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}

// ইনঅর্ডার ট্রাভার্সাল
void inorderTraversal(struct Node* root) {
    if (root != NULL) {
        inorderTraversal(root->left);
        printf("%d ", root->data);
        inorderTraversal(root->right);
    }
}

int main() {
    struct Node* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);

    printf("Inorder Traversal: ");
    inorderTraversal(root); // ইনঅর্ডার ট্রাভার্সাল
    printf("\n");

    return 0;
}

আউটপুট:

Inorder Traversal: 4 2 5 1 3