স্ট্যাক – লিংকড লিস্ট ইমপ্লিমেন্টেশন

স্ট্যাক-এর অ্যারে ইমপ্লিমেন্টেশন অনেক বেশি সহজ হলেও এর সমস্যা হল এখানে মেমরির অপচয় হয়। এছাড়াও খেয়াল করে দেখো আমরা এখানে অ্যারের সাইজ ডিফাইন করে দিচ্ছি। অন্য কথায় আমরা আমাদের স্ট্যাক-এর সর্বোচ্চ সাইজকেও লিমিটেড করে দিচ্ছি। এসব ঝামেলা থেকে বাঁচতেই আমরা আশ্রয় নেবো লিংকড লিস্টের। তবে চিন্তার কোনো কারণ নেই, নতুন কিছুই শেখা লাগবে না। পুরো লেখাটি পড়লেই বুঝতে পারবে যে আমরা আসলে ইতোমধ্যেই এসব কাজ একবার করে ফেলেছি লিংকড লিস্ট ব্যবহার করে!

স্ট্যাকে আমাদের দরকার হবে শেষ উপাদানটির দিকে নজর রাখা। কারণ আগেই বলেছি স্ট্যাক হল Last In First Out, যে শেষে এসেছে তার কাজই কিনা সবার আগে হয়ে যাবে! তার মানে আমাদের শুরুতে কী আছে, তা নিয়ে মাথা না ঘামালেও চলবে। তবে আমরা যদি display করতে চাই, সেক্ষেত্রে এটি লাগবে। তাহলে আমরা আমাদের স্ট্রাকচারটি ডিফাইন করবো এভাবেঃ

 

typedef struct node {
    int val;
    struct node * NEXT;
    struct node * PREV
} node_t;

 

তাহলে আমরা প্রথমেই আমাদের কোডের মূল কাঠামোটা লিখে ফেলি।

#include <stdio.h>
int count=-1;
typedef struct node {
    int val;
    struct node * NEXT;
    struct node * PREV;
} node_t;
node_t * last;
void create() {

}
int isEmpty () {
  
}

int size() {
    
}
void push (int num) {

}
int pop () {

}
int top () {

}
void menu () {
     while (1) {
        printf("Press 1 to create a new Stack.\n");
        printf("Press 2 to push.\n");
        printf("Press 3 to check if the Stack is empty.\n");
        printf("Press 4 to pop.\n");
        printf("Press 5 to show the top element.\n");
        printf("Press 0 to Exit.\n");
        int n;
        scanf("%d", &n);
        if (n==0) break;
        else if (n==1) create();
        else if (n==2) {
            printf("Enter the number: ");
            int num;
            scanf("%d", &num);
            push(num);
        }
        else if (n==3) {
            if (isEmpty()) printf("The Stack is empty.\n");
            else printf("The Stack is not empty.\n");
        }
        else if (n==4) {
            if (!isEmpty()) printf("Popped value = %d\n", pop());
            else printf("The Stack is empty.\n");
        }
        else if (n==5) {
            if (!isEmpty()) printf("The top element = %d\n", top());
            else printf("The Stack is empty.\n");
        }
        else {
            printf("Invalid choice! Try again.\n");
        }
    }
}
int main () {
    menu();
    return 0;
}

 

create()

যেহেতু আমরা লিংকড লিস্ট নিয়ে কাজ করছি, তাই আমাদের প্রথমেই একটা create() ফাংশন লাগবে। যেটি মূলত last পয়েন্টারটিতে নতুন একটি অ্যাড্রেস অ্যাসাইন করে দিবে। আগেও করেছি এধরণের কাজ। এখন আবার করে ফেলি!

void create() {
    last = (struct node*) malloc(sizeof(node_t));
    last = NULL;
}

তবে এখানে কিছু কাজ করি নাই আমি। তোমার জন্য রেখে দিলাম। :p ধর তোমার আগে থেকেই একটি লিংকড লিস্ট আছে, যেখানে ৫০০০০-টা উপাদান। এখন ইউজার নতুন একটি লিংকড লিস্ট তৈরি করতে বললে তো আগের সেই ৫০০০০ হাজার উপাদানের কথা ভুলে গেলেই হবে না। ওই মেমরিগুলো free করে দিয়ে এর পর নতুন লিংকড লিস্টটি তৈরি করতে হবে। এর জন্য ইউজ করতে হবে free() ফাংশনটি। লিংকড লিস্ট লেখাটিতে এ জিনিসটি দেখানো হয়েছিল। তাই এখানে আর নতুন করে দেখানো হচ্ছে না। আশা করি সেটা নিজে করে নিতে পারবে। 🙂

 

isEmpty()

এই ফাংশনের কাজ স্ট্যাকে কোনো উপাদান নেই কি না সেটি চেক করে দেখা। সেটি চেক করার জন্য আমরা দেখবো স্ট্যাকের last পয়েন্টারটি NULL কি না!

int isEmpty () {
    if (last == NULL) return 1;
    else return 0;
}

size()

এটি রিটার্ন করবে স্ট্যাকে মোট কতটি উপাদান আছে। খেয়াল কর আমরা একটি গ্লোবাল ভ্যারিয়েবল রেখেছি count নামের। তাই কাজটি একেবারেই সোজা হয়ে গিয়েছে। আমরা শুরু সেই ভ্যারিয়েবলের মানটি রিটার্ন করে দিবো!

int size() {
    return count;
}

খেয়াল কর, count-এর মান -1 এর অর্থ হল কোনো লিংকড লিস্ট তৈরি হয়নি।

 

push()

স্ট্যাকে পুশ করার অর্থ হল, সবার শেষে নতুন আরেকটি উপাদান যোগ  করে দেওয়া। তাহলে আমরা পুশ ফাংশনের মধ্যে last নামের পয়েন্টারটিতে নতুন একটি লিংক তৈরি করে নিবো! তবে তার আগে মাথায় রাখতে হবে স্ট্যাকটি খালি কি না।

void push (int num) {
    node_t * temp;
    temp = (struct node*) malloc(sizeof(node_t));
    temp->val = num;
    temp->NEXT = NULL;
    temp->PREV = last;
    if (last != NULL) {
        last->NEXT = temp;
        last = temp;
    }
    else last = temp;
    count ++;
}

 

pop()

এই কাজ আরও সহজ। শুধু last-এর PREV পয়েন্টারে যে লিংক আছে, সেটার NEXT-কে NULL করে দিবো, last-এর মান আপডেট করবো, সবশেষে পূর্বের last-কে ফ্রী করে দিবো। তবে এক্ষেত্রে খেয়াল রাখতে হবে pop করার পর স্ট্যাকটি খালি হয়ে যাচ্ছে কি না। যদি এমন হয় যে স্ট্যাকে একটি মাত্র উপাদান থাকে, সেক্ষেত্রে pop() করার পর স্ট্যাক খালি হয়। এবং এটাকে বিশেষভাবে হ্যান্ডেল না করলে রানটাইম এরর খাওয়া নিশ্চিত হয়। :p

int pop () {
    int v;
    v = last->val;
    node_t * temp;
    temp = (struct node*) malloc(sizeof(node_t));
    temp = last;
    last = last->PREV;
    if(last!= NULL) last->NEXT = NULL;
    free(temp);
    count--;
    return v;
}

 

আমাদের কাজ প্রায় শেষ। তবে এগুলো করে আসলে বোঝার উপায় নেই আমাদের কাজ আসলেই হচ্ছে কি না। এজন্য আমাদের display() ফাংশনটি লিখে নিতে হবে। কিন্তু আমরা তো first পয়েন্টার রাখিনি। এখন display করবো কীভাবে! চিন্তার কোনো কারণ নেই। আমরা এবার সাহায্য নেবো রিকার্শনের। রিকার্শনের সাথে নিশ্চয়ই তোমরা পরিচিত, কারণ সেটি ছিল সি টিউটোরিয়ালের অংশ। আমরা ততক্ষন পর্যন্ত এক্ষেত্রে পেছাতে থাকবো যতক্ষন না আমরা NULL-এ পৌছায়!

void display(node_t *temp) {
    if (temp->PREV!=NULL) display(temp->PREV);
    printf("%d ", temp->val);
}

আমার পুরো কোডটি আছে এখানে।

যদি লেখাটি ভাল মত পড়ে দেখো, তাহলে বুঝতে পারার কথা এটা আসলে ডাবলি লিংকড লিস্টের মতই। শুধু কিছু ভ্যারিয়েবল ফাংশনের নাম বদলে দেওয়া হয়েছে – এই আর কী। 😛