C++ STL :: stack

স্ট্যাকঃ

STL কন্টেইনারদের মধ্যে সম্ভবত সবচেয়ে সিম্পল ডাটা স্ট্রাকচার হল stack, এটা একটা লাস্ট ইন ফার্স্ট আউট (LIFO) ডাটা স্ট্রাকচার, মানে হল যে সবার শেষে আসবে, সে সবার আগে ভাগবে… সোজা কথায় এই কন্টেইনারের শুধুমাত্র একটা দিকেই ডাটা ইন্সার্ট বা এক্সট্র্যাক্ট করা হয়। আর STL এ stack তার ডিফল্ট ইন্টার্নাল ডাটা স্ট্রাকচার হিসাবে ব্যবহার করে STL এরই deque কন্টেইনার, তবে চাইলে vector বা list ও ব্যবহার করা যেতে পারে। যে সব কন্টেইনার push_back() আর pop_back() মেথড ২ টা সাপোর্ট করে সেগুলোকেই stack এর কন্টেইনার ক্লাস হিসাবে ব্যবহার করা যায়। stack আসলে একটা অ্যাডাপ্টার ক্লাস, অর্থাৎ, এটা তৈরি করা হয় এর ইন্টারনাল কন্টেইনারের স্পেসিফিক কিছু ফাংশনকে এলিমেন্ট একসেসের অনুমতি দিয়ে।

stack ব্যবহার করতে চাইলে সর্বপ্রথম কাজটা হল std <stack> হেডারটা প্রোগ্রামে ইনক্লুড করাঃ

#include <stack>
using namespace std;

কন্সট্রাক্টরঃ

অন্যান্য STL কন্টেইনার ক্লাসের মত stack এরও সাধারণ কন্সট্রাক্টর stack< type_t > myStack; এই রকমের, তবে আরো অনেকভাবে ডিক্লেয়ার করা যায়। যেমনঃ

// constructing stacks
#include <list>
#include <vector>
#include <deque>
#include <stack>
using namespace std;

int main ()
{
    // using default container deque

    stack< int > first; // empty stack
    deque< int > mydeque(3, 100); // deque with 3 elements
    stack< int > second(mydeque); // from mydeque
    stack< int > third(second); // from another stack second

    // explicit container declarations

    stack< int, deque< int > > fourth; // empty stack using deque
    deque< int > newdeque(10, 100); // deque with 10 elements
    stack< int, deque< int > > fifth(newdeque); // from newdeque

    stack< int, vector< int > > sixth;  // empty stack using vector
    vector< int > myvector(2, 200); // vector with 2 elements
    stack< int, vector< int > > seventh(myvector); // from myvector

    stack< int, list< int > > eighth; // empty srack using list
    list< int > mylist(4, 100); // list with 4 elements
    stack< int, list< int > > ninth(mylist); // from mylist

    // can refer to some other stack
    stack< int > tenth = first; // declaration time initialization

    return 0;
}

কমপ্লেক্সিটিঃ কন্টেইনার কন্সট্রাকশনের সাপেক্ষে কন্সট্যান্ট, অতএব কি ধরণের কন্টেইনার ব্যবহার করা হচ্ছে তার উপরে নির্ভর করে।

এলিমেন্ট একসেসঃ

stack ক্লাসের এলিমেন্ট গুলাকে একসেস করার জন্য ৩ টা মেম্বার ফাংশন আছেঃ

1. top()
2. push()
3. pop()

push() ফাংশনটার কাজ stack এর শেষে কোন এলিমেন্ট ইন্সার্ট করা, আর pop() দিয়ে লাস্ট এলিমেন্ট টা বের করে দেয়া। top() এর সাহায্যে কারেন্টলি stack এ সবার উপরের এলিমেন্ট কে পাওয়া যায়। top() এলিমেন্টকে স্ট্যান্ডার্ড অপারেটরদের সাহায্যে মডিফাই করা যায়।

আর, stack এর এলিমেন্ট কাউন্ট করার জন্য ২ টা ফাংশন আছেঃ

1. size()
2. empty()

size() ব্যবহার করে জানতে পারি এই মুহূর্তে stack এ কতগুলো এলিমেন্ট আছে, আর empty() একটা boolean ফাংশন, stack খালি থাকলে এটা true দেয়, না হলে false, stack এ pop() মেথডটা ব্যবহার করতে চাইলে আগে অবশ্যই চেক করে নিতে হবে stack এ কিছু আছে কিনা, তা না হলে run-time error হতে পারে।

নিচে এই ফাংশন গুলার কাজ দেখানো হলঃ

// stack::push/pop/top/size/empty
#include <iostream>
#include <stack>
using namespace std;

int main ()
{
    stack< int > mystack;
    // lets push and pop some values
    for (int i=0; i<5; i++) mystack.push(i);

    cout << "Popping out elements...";
    while (!mystack.empty())
    {
        cout << " " << mystack.top();
        mystack.pop();
    }
    cout << endl;

    // changing the value of top
    mystack.push(100);
    mystack.top() += 1000;
    cout << "Now top is: " << mystack.top() << endl;
    mystack.pop();

    // not a good way to check if stack is empty
    if(mystack.size() == 0) cout << "Stack is empty" << endl;
    // better we do this
    if(mystack.empty()) cout << "Stack is empty" << endl;

    return 0;
}

কমপ্লেক্সিটিঃ প্রতিটা ফাংশনের কম্পলেক্সিটি কন্সট্যান্ট।

ব্যবহারঃ

সাধারণত এক্সপ্রেশন / গ্রামার প্রসেসিং, রিকারসিভ এলগরিদমের নন রিকারসিভ প্রয়োগ, DFS ট্রাভার্সাল, LIFO অপারেশনে stack ব্যবহার করা হয়। STL এর stack একটা টেমপ্লেট ক্লাস, তাই যে কোন ডাটা টাইপের জন্য খুব দ্রুত stack ইম্পলিমেন্ট করা যায় STL ব্যবহার করে।

বিস্তারিতঃ http://www.cplusplus.com/reference/stl/stack/