Skip to main content

ডাটা স্ট্রাকচার- স্ট্যাক (Stack)

Programming is all about data manipulation. Data structure is way of storing data for further manipulation.

ডাটা স্ট্রাকচার আমাদেরকে বিভিন্ন ডাটা সাজিয়ে রাখার ব্যবস্থা করে দেয়। ডাটা সাজিয়ে রাখার অনেক গুলো "তরিকা" আছে। কোনকিছু আমরা কেন সাজিয়ে রাখি? যেন পরে নির্দিষ্ট একটা ডাটা সহজে খুঁজে পেতে পারি। "তরিকা" গুলোর নাম Array, Stack, Queue, Linked List, Tree, Graph.
এগুলা শ খানেক ডাটা স্ট্রাকচারের মধ্যে কিছুর নাম, যেগুলো অনেক বেশি ব্যবহার হয়।

এই পোস্টটা স্ট্যাক বুঝানোর জন্য।

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

এই বিস্কিট ভর্তি বয়ামের মধ্যে লক্ষণীয় একটা বিষয় আছে। যেই বিস্কিট সবার আগে ঢুকানো হয়েছিলো সেটা সবার পরে বের হবে। যেটা সবার পরে ঢুকেছিলো সেটা সবার আগে বের হবে। এই কনসেপ্টটাকে বলে Last In First Out (LIFO)। প্রোগ্রামিং এর স্ট্যাক ডাটা স্ট্রাকচারও এই LIFO কেই ফলো করে।

স্ট্যাক আমরা বানাই সাধারনত সেই আগের Array দিয়েই (হ্যা এই Array সারাজীবন থাকবে 😄) । একটা একটা করে ডাটা Array তে ঢুকাই আবার পরে দরকারে বের করে আনা যায়। কিন্তু মনে রাখতে হবে যেটা সবার আগে ঢুকাবো সেটা সবার পরে বের হবে।

    PUSH: স্ট্যাকে ডাটা ঢুকানোকে পুশ করা বলে। কিছু কিছু প্রোগ্রামিং ল্যাংগুয়েজে আলাদা পুশ ফাংশন থাকে। আবার নিজেও বানিয়ে নেয়া যায়।
    POP: স্ট্যাক থেকে একটা ডাটা বের করে ফেলাকে পপ করা বলে। এটাও অনেক ল্যাংগুয়েজে আগে থেকেই বানানো থাকে। আবার নিজেও বানায় নেয়া যায়। পপ করলে সবসময় সবার শেষে যেই ডাটা ঢুকানো হয়েছিলো সেটাই পপ হবে।
    TOP: এই ফাংশনটা স্ট্যাকের সবার উপরে কোন ডাটাটা আছে সেটা দেখার জন্য ব্যবহার হয়। এটা আমরা একটা ডাটা রিড করার জন্য ব্যবহার করি।

একটা বেসিক স্ট্যাক প্রোগ্রামঃ
-----------------------------------------------------------------------------------------------------------------------

#include<iostream>
#define SIZE 5

using namespace std;

int STACK[MAX],TOP;

//stack initialization
void initStack(){
    TOP=-1;
}
//check it is empty or not
int isEmpty(){
    if(TOP==-1)
       return 1;
    else
       return 0;
}

//check stack is full or not
int isFull(){
	if(TOP==MAX-1)
		return 1;
	else
		return 0;
}

void push(int num){
	if(isFull()){
		cout<<"STACK is FULL."<<endl;
		return; 
	}
	++TOP;
	STACK[TOP]=num;
	cout<<num<<" has been inserted."<<endl;
}

void display(){
    int i;
    if(isEmpty()){
        cout<<"STACK is EMPTY."<<endl;
        return;
    }
    for(i=TOP;i>=0;i--){
        cout<<STACK[i]<<" ";
    }
    cout<<endl;
}

//pop - to remove item
void pop(){
    int temp;
    if(isEmpty()){
        cout<<"STACK is EMPTY."<<endl;
        return;
    }
     
    temp=STACK[TOP];
    TOP--;
    cout<<temp<<" has been deleted."<<endl;   
}
int main(){
    int num;
    initStack();
    char ch;
    do{
            int a;
            cout<<"Chosse \n1.push\n"<<"2.pop\n"<<"3.display\n";
            cout<<"Please enter your choice: ";
            cin>>a;
            switch(a)
            {
                case 1:
                    cout<<"Enter an Integer Number: ";
                    cin>>num;
                    push(num);
                break;
                 
                case 2: 
                    pop();
                    break;
                 
                case 3: 
                    display();
                    break;
                 
                default : 
                cout<<"An Invalid Choice!!!\n";
                 
                 
            }
            cout<<"Do you want to continue ? ";
            cin>>ch;
            }while(ch=='Y'||ch=='y');
    return 0;
}

এই প্রোগ্রামের মাধ্যমে পুশ পপ আর টপ বোঝানোর চেষ্টা করা হয়েছে। একটু হিজিবিজি মনে হতে পারে। বাট একটু বোঝার চেষ্টা করে দেখা যায়। বুঝলে দেখা যাবে খুবই ইজি।

এতক্ষন দেখে মনে হতে পারে যে এই স্ট্যাক জিনিসটার কাজ কি? অনেক কাজ আছে আসলে। একটা সিম্পল উদাহরণ দেই। ধরা যাক অনেক গুলা সংখ্যা ইনপুট নিয়ে সেগুলাকে রিভার্স অর্ডারে প্রিন্ট করতে চাচ্ছি। তখন স্ট্যাক ইউজ করা যেতে পারে। কারন সবার আগে যেটা ইনপুট নিলাম সেটা সবার শেষে প্রিন্ট হবে। আর সবার পরেরটা সবার আগে।
আশা করি বুঝাতে পারলাম।

For Further Studies about Stack:

  1. C Plus Plus
  2. Geeks for Geeks
  3. Tutorials Point
Code Used in this Post: Include Help

Comments

Some of My Bests

ডাটা স্ট্রাকচার- কিউ (Queue)

Programming is all about data manipulation. Data structure is way of storing data for further manipulation. ডাটা স্ট্রাকচার আমাদেরকে বিভিন্ন ডাটা সাজিয়ে রাখার ব্যবস্থা করে দেয়। ডাটা সাজিয়ে রাখার অনেক গুলো "তরিকা" আছে। কোনকিছু আমরা কেন সাজিয়ে রাখি? যেন পরে নির্দিষ্ট একটা ডাটা সহজে খুঁজে পেতে পারি। "তরিকা" গুলোর নাম Array, Stack, Queue, Linked List, Tree, Graph. এগুলা শ খানেক ডাটা স্ট্রাকচারের মধ্যে কিছুর নাম, যেগুলো অনেক বেশি ব্যবহার হয়। এই পোস্টটা কিউ বুঝানোর জন্য। কিউ জিনিসটার সাথে আমরা সবাই পরিচিত। জীবনে আমরা সবাই কখনো না কখনো লাইনে দাঁড়ায়ছি। কিউ এর বেসিক ক্যারেক্টারিস্টিকসের সাথে মিলিয়েই প্রোগ্রামিং এ কিউ এর কনসেপ্ট। বাস্তব জীবনে একটা কিউ তে কি হয়? সবাই লাইন ধরে দাঁড়ায় কিছু একটা কারনে। যে সবার আগে দাঁড়ায় সেই সবার আগে কার্জসিদ্ধি করে। সবার পরের জন সবার পরে। স্ট্যাকের ক্ষেত্রে আমরা পড়েছিলাম Last In First Out (LIFO) or First In Last Out (FILO)। কেমন আনফেয়ার শোনায় না? সবার পরে আসবে, আবার সবার আগে চলে যাবে। অ্যাটলিস্ট আমার আনফেয়ার লেগেছিলো যখন স্ট্যাক শিখছিল

কম্পিউটার বচন

কম্পিউটারের সাথে আমার পরিচয় খুব ছোট বয়সে না। অন্তত চেনাপরিচিত বন্ধুমহলের অনেকের তুলনায় আমি বাচ্চাই বলা চলে। ক্লাস ২ বা ৩ তে পড়ি যখন ফুফাতো ভাই প্রথম কম্পিউটার কেনে। ফুফুর বাসা কাছেই হওয়ায় মাঝে মাঝেই সেটা দেখার সৌভাগ্য হতো। কিন্তু ছুয়ে দেখার সাহস তখনও হয়নি। সেই বছর থেকে আমাদের রেওয়াজ, ঈদের দিন নামাজ পড়েই সোজা ভাইয়ার রুমে। ভাইয়া নতুন একটা গেম ইন্সটল করে রাখতো আর আমরা কাজিনেরা লাইন দিয়ে সেটা খেলতাম (যদিও আমার ভাগে কমই পড়তো :p )  ক্লাস সিক্সে নতুন স্কুলে ভর্তি হলাম। এ এক আজব জায়গা। সবাই বড়লোকের পোলাপাইন। কতজন গাড়িতে করে আসে। তাদের তো কথাই নাই। যাদের গাড়ি নাই তাদেরও রোজকার বাজেট বিশাল। ইচ্ছামত উড়ায়। আর আমি মধ্যবিত্তের ছেলে। যাওয়া আসার ভাড়া বাদে কোনো টাকা পেতামনা। টিফিন বাসা থেকে বানায়ে দিতো। এই যখন আমার অবস্থা তখন ক্লাসমেটরা নিত্যনতুন গ্যাজেটের সাথে শুধু পরিচয়ই না, পকেটে নিয়ে ঘুরে (যদিও স্কুলে নিষিদ্ধ ছিলো )। সবাই এসব নিয়ে কত গল্প চালায় যায়। আর আমার মত বোকা কিছু পাবলিক হা করে এদের গল্প শুনি। কম্পিউটারের কত বচন, কত আড্ডা। এসব আড্ডায় ঢুকতে কত ইচ্ছা করতো, কিন্তু ঢুকবো কি করে? আমার কম্পিউটা