স্ট্যাক ( Stack )

স্ট্যাক (stack)

ধরি আমি কোন রেস্টুরেন্ট এ কাজ করি। আমার কাজ হচ্ছে থালাবাসন পরিষ্কার করা। এখন আমি এক গাদা প্লেট খাবার টেবিল থেকে নিয়ে ধুবো এবং এরপরে প্লেটগুলি স্তুপ করে একটার উপর একটা রাখবো। এখন লক্ষ্য করলে দেখবে যে প্লেট টা সবার আগে পরিষ্কার করলাম, সেটা কিন্তু স্তুপ এর সবার নিচে আছে। অর্থ্যাৎ আরেকভাবে বললে , যে প্লেট টা সবার পরে পরিষ্কার করলাম সেটা স্তুপ এর সবার উপরে আছে। এখন আমি পরিষ্কার প্লেটগুলি যখন নিবো, তখন কিন্তু স্তুপ এর উপরের থেকেই নেয়া শুরু করবো। অর্থ্যাৎ যে সবার আগে স্তুপ থেকে বের হবে, সে আসলে সবার শেষে স্তুপ এ ঢুকেছিল।

এটি ই স্ট্যাক এর মূল বৈশিষ্ট। একে আমরা বলি “Last In First Out” বা সংক্ষেপে “LIFO”.
এই জিনিসটাকে বলে স্ট্যাক। মানে আমরা সবার পরে যাকে প্রসেসিং করতে ঢুকাচ্ছি তাকে যদি আগে প্রসেসিং করি তাহলে সেটাই স্ট্যাক। STL এ স্ট্যাক ব্যবহার করতে হয় এভাবে,

#include <stack>
using namespace std;
int main()
{
        stack s;  //  একটি ইন্টিজার এর স্ট্যাক
        s.push( 10 );
        s.push( 20 );
        s.push( 30 );
}
/* 10, 20, 30 কে স্ট্যাক এ পুশ করলাম। এখন আমার স্ট্যাক টা দেখতে হবে অনেকটা এরকম
30 // top value of the stack (LIFO)
20
10
*/অর্থাৎ স্ট্যাক এ এখন ৩ টি ভ্যালু আছে।

তাই, স্ট্যাক এর সাইজ হবে ৩।  s.size() এর মাধ্যমে আমরা স্ট্যাক এর সাইজ জানতে পারি।

এখন আমরা স্ট্যাক এর টপ ভ্যালু দেখতে চাইলে যে ফাংশন ব্যবহার করবো তাহলো top() ফাংশন।

int x = s.top();    // x এর মধ্যে স্ট্যাক এর টপ (30) ভ্যালু আছে
cout << x << endl; // x = 30;

এখন যদি আমরা পরের ভ্যালু দেখতে চাই, তাহলে আমাদের আগে টপ এর ভ্যালু কে মুছে ফেলতে হবে। মুছে ফেলার জন্য আমরা ব্যবহার করবো pop() ফাংশন।

s.pop();       // স্ট্যাক এর টপ টাকে ডিলেট করে ফেললাম।
এখন আমার স্ট্যাক এর টপ ভ্যালু হবে 20.

আরেকটা গুরুত্বপুর্ণ ফাংশন হলো empty()
এর কাজ হল স্ট্যাক টা খালি (NULL) আছে কিনা তা চেক করা।

একটি কোড দেখা যাক,

while( !s.empty() )
{
        cout<< s.top() <<endl; // printing the top element;
        s.pop(); // removing the top element;
}
// যতক্ষন স্ট্যাক টা নাল না হবে, ততক্ষন স্ট্যাক এর এলেমেন্ট গুলি প্রিন্ট করলাম

স্ট্যাক দিয়ে আমরা অনেকরকম প্রব্লেম সল্ভ করতে পারি। এর মধ্যে ব্র্যাকেট ম্যাচিং (Bracket Matching or Paranthesis Matching) উল্লেখযোগ্য। তোমরা এগুলো একটু ঘাটাঘাটি করে দেখতে পারো। paranthesis matching নিয়ে পরে কোন এক পোস্ট এ কিছু লিখবো।