Stack implementation using array

স্ট্যাকে যে ধরনের অপারেশনগুলো করা হয়! push, pop এবং ডাটাগুলো দেখানোর display ফাংশন। প্রথমে কয়েকটা ছোটখাটো কাজ করে ফেলিঃ

1:  #define MAX_SIZE 5  
2:  top= -1;  
3:  int A[MAX_SIZE];  

উপরের কাজটি ফাংশনের বাইরের কাজ। গ্লোবালি ডিক্লেয়ার করা হয়েছে যাতে সকল ফাংশন তা ব্যাবহার করতে  পারে। লাইন ১ এ- একটি ম্যাক্রো তৈরী করা হয়েছে। যার মান দেওয়া হয়েছে 5. এইটা আসলে আমাদের অ্যারের হাইস্ট সাইজ।  দ্বিতীয় লাইনে ইনিসিয়ালি  top=-1 দেওয়া হয়েছে। টপ সম্পর্কে আগে পর্বে বর্ণনা করা হয়েছে। আগের পর্ব দেখা যাবে এখান থেকে।  Top হল যে বিন্দুতে ইনপুট নেওয়া বন্ধ হয় সেটা। প্রকৃত অর্থে Top আমাদের অ্যারের ইনডেক্স বহন করবে। প্রথমে এর ইনডেক্স -১ ধরলাম তার মানে হল এখনো লিস্ট তৈরী করা হয়নি। এখানে ইন্ডেক্স -১ একটি কাল্পনিক ইনডেক্স কারন অ্যারের ইনডেক্স শুন্য থেকে শুরু হয়।
এবার push ফাংশন লিখে ফেলিঃ

1:  void push(int x)  
2:  {  
3:    if(top==MAX_SIZE-1){  
4:      printf("Stack Over flaw\n");  
5:      return;  
6:    }  
7:     top++;
8:    A[top]=x;  
9:  }  

প্রথম লাইনে ফাংশনটি প্যারামিটার হিসেবে একটি একটি ইন্টেজার নিবে। সেই ইন্টেজারটি আসলে আমরা স্ট্যাকে প্রবেশ করাবো । যেহেতু আমরা অ্যারের হাইস্ট সাইজ 5 নিলাম সেহেতু আমরা ডাটা ৫ টার বেশী রাখতে পারবোনা। যদি ৫ টার বেশী রাখতে চাই over flaw. এই সিস্টেমকে বলা হয় stack over flaw. যাইহোক ডাটা পাঠানোর জন্য মেইন ফাংশন লিখে ফেললাম।

1:  int main()  
2:  {  
3:    push(10);  
4:    push(20);  
5:    push(30);  
6:    push(40); 
7:    push(50);
8:    pop();  
9:    display();  
10:  }  

যখন push(10) কল করলাম তখন  push ফাংশনে প্রবেশ করবে এবং ৩য় লাইনে কন্ডিশন চেক করবে। যেহেতু top এর মান -1 এবং (5-1)=4 সমান নয় সেহেতু ওই কন্ডিশনে ঢুকবেনা। তারপর সপ্তম লাইনে এসে top এর মান 1 বেড়ে 0 হয়ে যাবে এবং A[0] তে 10 অ্যাসাইন করবে।
তারপর আবার যখন push(20) দিলাম তখন top এর মান শুন্য যেহেতু কন্ডিশন মিথ্যা সেহেতু কন্ডিশনে ঢুকবেনা এবং top এর মান 1 বেড়ে যাবে এবং A[1] এ 20 অ্যাসাইন করবে। এভাবে push(30) পাঠাবো তখন যেহেতু top এর মান 1 সেহেতু A[2]=30 যখন push(40) দিলাম তখন top এর মান 2 সেহেতু A[3]=40 হবে আবার যখন push(50) দিলাম তখন top এর মান 3 এরপর A[4]=50 হবে।
এখন যদি আরেকবার push ফাংশন করি তখন 4=4 কন্ডিশন সত্য হয়ে যাবে এবং প্রিন্ট করবে stack over flaw দেখাবে। সুডো কোড দেখলে ব্যাপারটা আরো ক্লিয়ার হবে।

push(10)
top=-1   //-1!=4
top=0
A[0]=10

push(20)
top=0 //0!=4
top=1

A[1]=20
push(30)
top=1 // 1!=4
top=2
A[2]=30

push(40)
top=2 2!=4
top=3
A[3]=40

push(50)
top=3 3!=4
top=4
A[4]=50

push(60)
top=4 // 4==4
stack over flaw

এবার pop ফাংশন লিখে ফেলিঃ

1:  void pop()  
2:  {  
3:    if(top==-1){  
4:      printf("stack is empty\n");  
5:      return;  
6:    }  
7:    top--;  
8:  }  

পপিং এর লজিক হল যেকোনভাবে আমরা ইনডেক্স উড়িয়ে দেব। ইনডেক্স উড়িয়ে দিতে পারলেই আমাদের পপিং শেষ। আমরা আগেই জানি যে যখন top এর মান -1 হয় তখন stack empty থাকে । এবং তখন pop করার মত কিছুইনাই। কন্ডিশনে সেইটা দেওয়া আছে।
আচ্ছা বলুনতো এখন top এর মান কত? নিশ্চয় 4 তাইনা ?
-হুম।
এখন মেইন ফাংশ থেকে pop() ফাংশনকে কল করার পর কন্ডিশনে মিথ্যা হয়ে top এর মান এক কমে গেল। ব্যাস, A[4] এখন হাওয়া :D এভাবে যতবার পপ করব ততবার এক এক করে কমতে থাকবে কোন এক সময় top=-1 হয়ে যাবে তখন আর স্ট্যাকে কিছুই থাকবেনা এবং কন্ডিশন সত্য হয়ে যাবে এবং প্রিন্ট দিবে stack is empty !
এইবার display() ফাংশনের কাজঃ

1:  void display()  
2:  {  
3:    int i;  
4:    for(i=0;i<=top;i++){  
5:      printf("%d ",A[i]);  
6:    }  
7:  }  

এখানে আর কিছুই বলার নাই । শুন্য থেকে করে টপের হাইস্ট ভেলু পর্যন্ত প্রিন্ট দিবে। একবার pop করার পর top= 3
তাহলে আ[0] থেকে শুরু করে A[3] পর্যন্ত মানগুলো প্রিন্ট দিবে। যখন মেইন ফাংশনের ৯ম লাইন থেকে display() কল করা হল  স্বভাবতই প্রিন্ট করবেঃ
10 20 30 40
পূর্ণাংগ প্রোগ্রামটি কম্মেন্ট সহ পাওয়া যাবে এখানে! আজ এ পর্যন্তই! থেঙ্কু !