ডাটা স্ট্রাকচার - ৫ঃ স্ট্যাক

তোমার বাসায় সাতটি চেয়ার আছে। প্রথমে একটি চেয়ার রাখলে, তার উপর দ্বিতীয় চেয়ারটি, তারপর তৃতীয় চেয়ারটি এবং তারপর  চতুর্থ চেয়ার এরপর যথাক্রমে পঞ্চম , ষষ্ঠ এবং সপ্তম! অতঃপর চেয়ারের একটি স্তুপ তৈরী হল। এখন তোমাকে যদি চেয়ারগুলো স্তুপ থেকে আলাদা করতে বলা হয়  তাহলে তুমি  কি করবে? তোমাকে নিশ্চয়ই প্রথমে সাত নাম্বার চেয়ারটা তুলতে হবে তারপর ছয় নাম্বার তারপর পাঁচ নাম্বার  নাম্বার এভাবে সবশেষে এক নাম্বারটা তুলতে হবে। লক্ষ্য করবে  তুমি যে  ১ নাম্বার চেয়ারটি  প্রথমে রেখেছিলে তা তুলতে হল শেষে এবং ৭ নাম্বার চেয়ারটি শেষে দিলেন তা তুলতে হলো প্রথমে। এখানে চেয়ারের স্তুপ এক ধরনের স্ট্যাক। এইতো গেলো থিওরিটিকাল কনসেপ্ট। প্রোগ্রামিং এ  ব্যাপারটা ঠিক একইরকম। 

প্রোগ্রামিং এ আমরা নানান ধরনের ডেটা নিয়ে খেলা করি। ভিবিন্ন উপায়ে আমরা ডেটা রাখতে পারি। স্ট্যাক হল ডেটা রাখার এমনই এক ধরনের উপায়। এই উপায়ে ডেটা গুলো এমনভাবে রাখা হয় বা সাজানো থাকে যাতে পুরোপুরি উপরে বর্ণিত স্ট্যাক পদ্ধতি মেন্টেন করে। মানে প্রথমে যে ডেটা রাখলাম তা শেষে পাবো এবং শেষে যে ডেটা দিলাম তা আগে পাবো। এটাকে সংক্ষেপে বলা হয় FIFO বা ফার্স্ট ইন লাস্ট আউট।

ডেটা আমরা অ্যারে বা লিঙ্ক লিস্ট যেখানেই রাখিনা কেন এমন পদ্ধতি মেন্টেন করবো যাতে স্ট্যাকের নিয়ম অনুযায়ী আমরা ডেটাগুলো পাই। স্ট্যাক পদ্ধতিতে ডেটা রাখাকে বলা হয় Push এবং ডেটা বের করে নিয়ে আসাকে বলা হয় Pop


মুল তত্ত্বঃ  ডেটা ইন্সার্ট করার সময় সর্বশেষ ডেটার ইন্ডেক্স ট্রেস করে রাখবো। সেই ইন্ডেক্সকে বাড়িয়ে কমিয়ে আমরা প্রবেশ করাবো কিম্বা বের করে নিয়ে আসবো। আমাদের ক্ষেত্রে সেই ইন্ডেক্সটার নাম হবে top. যেহেতু প্রথমে অ্যারেতে কোন ডেটা থাকবেনা তাই প্রথমে top = -1 হবে। 

 Push Algorithm:  
 1. Initialize top with -1 and create array stack[MAX]   
 2. Insert data in array and increase the value of top   
 3. Continue 2 until array is not is not full   
 4. If array is full then exit   

 Pop Algorithm:   
 1. Return stack[top] and decrease the top  
 2. Continue 1 until stack is not empty   
 3. If stack is empty then exit   

Pseudo code:

 void push(int data)  
 {  
   top++;  
   if(top==MAX)  
   {  
     printf("Stack is full: ");  
     return sizeOfStack()-1;  
   }  
   stack[top] = data;  
 }  

 int pop()  
 {  
   if(top == -1)  
   {  
     printf("Stack is empty: ");  
     return sizeOfStack();  
   }  
   return stack[top--];  
 }