stack implementation using link list

এর আগে স্ট্যাক ইমপ্লিমেন্টেশন অ্যারে দিয়ে করা হয়েছে। আজ দেখবো কিভাবে লিঙ্ক লিস্ট দিয়ে করতে হয়। অ্যারেতে যেহেতু একটা সাইজ ধরে নিতে হয় এবং সে সাইজের বেশী ডাটা প্রবেশ করাতে গেলে স্ট্যাক ওভারফ্লো নামক ঘটনা ঘটে। কিন্তু লিঙ্ক লিস্টে এরকম ঘটনা ঘটবেনা।  লিঙ্ক লিস্টে যেহেতু ডায়নামিক মেমরি ব্যাবহার সেহেতু এ ধরনের ঘটনা ঘটার কথাও না। মানে আমাদের যখনই কোন ডাটা প্রবেশ করানোর দরকার হবে তখনই মেমরি অ্যালোকেট করবো ডাটা প্রবেশ করাবো। লিঙ্ক লিস্ট নিয়ে আরো জানা যাবে এখান থেকে। যাইহোক শুরু করা যাকঃ

1:  struct Node{  
2:    int data;  
3:    struct Node* next;  
4:  };  
5:  typedef struct Node node;  
6:  node* top;  

1:  int main()  
2:  {  
3:    top=NULL;  
4:    push(10);  
5:    push(20);  
6:    push(30);  
7:    pop();  
8:    pop();  
9:    display();  
10:    return 0;  
11:  }  

1:  void push(int x)  
2:  {  
3:    node* temp;  
4:    temp=(node*)malloc(sizeof(node));  
5:    temp->data=x;  
6:    temp->next=top;  
7:    top=temp;  
8:    }  

1:  void pop()  
2:  {  
3:    node* temp;
4      temp=top;  
6:      printf("Nothing to pop\n");  
7:      return;  
8:
9:    top=top->next;  
10:    free(temp);  
11:    }  

1:  void display()  
2:  {  
3:    node* temp;  
4:    temp=top;  
5:    while(temp!=NULL){  
6:      printf("%d ",temp->data);  
7:      temp=temp->next;  
8:    }  
9:  }  

এইটা লিঙ্ক লিস্টের বিগেনিং ইমপ্লিমেন্টেশন । এর আগে লিঙ্ক লিস্ট ইমপ্লিমেন্টেশন কয়েক ধাপে আলোচনা করা হয়েছিলো।  এখানে শুধু  হেড এর পরিবর্তে top ধরা হয়েছে। Top সম্পর্কে এখানে বর্ণনা করা হয়েছে। তবুও কিছু জিনিস বলে রাখিঃ
push  ফাংশনঃ
10 20 30 push করার পর লিস্টের বর্তমান অবস্থা হবে 30 20 10  কারন এইটা বিগেনিং ইমপ্লিমেন্টেশন। ইমপ্লিমেন্টেশ সম্পর্কে দুটি পুরনাংগ পোস্ট করা হয়েছে ইতোমধ্যে। বিগেনিং ইমপ্লিমেন্টেশন পাওয়া যাবে  এখান থেকে এবং end লিঙ্ক লিস্ট পাওয়া যাবে এখান থেকে।
pop ফাংশনঃ 

pop যেভাবে কাজ করে (এখানে শুধু প্রথম পপ দেখানো হয়েছে )

যেহেতু সবার শেষে পুশ করা হয়েছে 30 , সেহেতু স্ট্যাকের নিয়ম অনুযায়ী 30 সর্বপ্রথম পপ  হবে তারপর 20 সবশেষে 10.
এই মুহূর্তে top=30. আমরা যদি Top থেকে 30 বিচ্ছিন্ন করে ফেলি তাহলেই আমাদের কাজ শেষ। মেইন ফাংশনের ৭ম লাইন থেকে যখন pop করা হল তখন pop ফাংশনে এসে temp=top হলো কারন পরে আমাদের যায়গাটি ফ্রি করার দরকার হবে । তারপর Top কে ঘুরিয়ে পরবর্তী নোডে নিয়ে গেলাম। এখন আর 30 নাই। কিন্তু 30 কিছু মেমরি দখল করে আছে । তা ফ্রি করার জন্য free(temp) ব্যাবহার করা হয়েছে ।
একইভাবে যখন আরেকবার pop করা হল তখন একই ভবে 20 চলে যাবে। এবার যখন display ফাংশন কল করা হল স্বভাবতই প্রিন্ট করবে শুধু 10.
আজ এ পর্যন্তই। ধন্যবাদ