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

stack
ছবিটা সুন্দর না?? হুম, এটাই একটা স্ট্যাকের ছবি।
কি অবাক হচ্ছো?? ভাবছো, এইসব ‘ইট-পাত্থরের’ সাথে স্ট্যাকের কি সম্পর্ক?
আসলে সম্পর্কটা হলো, জিনিসটা সাজানোর ধরনে। এই যে একটার ওপর আরেকটা বসিয়ে একটা কাঠামো তৈরি করা হলো, এই কাঠামোটার নামই স্ট্যাক (Stack)।
আজকে আমি ডাটা স্ট্রাকচারের অত্যন্ত গুরুত্বপূর্ণ একটা বিষয় স্ট্যাক নিয়ে বলবো।
স্ট্যাক (Stack) ডাটা স্ট্রাকচারে ডাটাগুলো রাখা হয় এমনভাবে যেন নতুন কোনো ডাটা সেখানে রাখতে হলে সবচাইতে উপরে রাখতে হয়, এবং নেয়ার সময়ও সবসময় প্রথমে উপরের ডাটাটাকে নিতে হবে। তারমানে স্ট্যাকে তুমি যাই করো না কেন, সেটা হতে হবে সবচাইতে উপরের ডাটাতে। আমরা কোনো ডাটা রাখতে হলে সেটাকে রাখবো আগের গুলোর ওপরে, আর নেয়ার সময়ও নিতে হবে সবার উপরেরটা।
জিনিসটা হবে এরকম-
Data_stack.svg
স্ট্যাকে ডাটা রাখাকে বলা হয় Push আর ডাটা তুলে নেয়াকে বলা হয় Pop ।
এখন আমরা যখন কোড করবো কিংবা মেমোরীতে কিভাবে ডাটা থাকবে সেটা যদি চিন্তা করি, তাহলে কিন্তু এই যে ‘উপরে’ ডাটা রাখার কথা বলছি সেটার কিন্তু কোনো অর্থ হয় না। কারণ মেমোরীতে ‘উপরে’ বলে আবার কিছু আছে নাকি??
আসলে পুরো ব্যাপারটা এভাবে বলা হয় জিনিসটা বোঝার সুবিধার্থে, তাতে করে ব্যাপারটা সহজে মাথায় ঢোকে।
তারমানে আসলে যেটা হয় সেটা হলো, আমরা সবার শেষে যেটাকে রাখবো, আমাদের লিস্টে, তুলতে হলে সেটাকেই প্রথমে তুলতে হবে, শেষেরটা না তুলে অন্য কোনোটা তোলা যাবে না। আর মাঝখানে হুট করে কোনো ডাটাও রাখা যাবে না (যেমনটা অ্যারে আর লিংকড লিস্টে করা যায়)।
এই পদ্ধতিকে সুন্দর করে বলা হয় “Last In First Out (LIFO)” । মানে যাই করো না কেন সেটা হতে হবে সবার শেষে। খেয়াল করে দেখো তো আমরা আমাদের বাস্তব জীবনে কি এরকম কোনো পদ্ধতি ব্যবহার করি??
আচ্ছা, আমরা যখন খাবার প্লেট সাজিয়ে রাখি, সেটা কিভাবে রাখি? আমরা যখন সিডি বক্সে সিডি রাখি সেটা কি আমরা অ্যারের মত করে রাখি না কি অন্য কোনোভাবে রাখি?
87626928-horz
এতক্ষণে নিশ্চয়ই বোঝা হয়ে গেছে, স্ট্যাক বলতে আসলে কি বোঝাচ্ছে??
আচ্ছা, এবার আসি কিভাবে স্ট্যাক কোড করা যায়। এ্যারে আর লিংকড লিষ্ট দুইটা দিয়েই স্ট্যাক কোড করা যায়।
প্রথমে বলি, এ্যারে দিয়ে কিভাবে কোড করা যায়।
যেহেতু আমরা সবসময় শেষ পজিশনে ডাটা রাখবো এবং সেখান থেকে ডাটা উঠিয়ে নিবো, তার মানে আমরা প্রথমে একটা এ্যারে নিয়ে নিবো ডাটা রাখার জন্য আর একটা ভ্যারিয়েবল top নিবো যেটা দিয়ে আমরা বুঝতে পারবো এ্যারের শেষ কোন পজিশন পর্যন্ত ডাটা রাখা হয়েছে।
এরকম-
#include<stdio.h>
#define sz 100   

int arr[sz],top=0;

এখন আমাদের ডাটা Push করার জন্য একটা ফাংশন হবে এরকম-

void push(int val)
{
    if(top>=sz)
        printf("No more space on Stack.\n");
    else
        arr[top++]=val;
}
যেহেতু আমাদের এ্যারের সাইজ নির্দিষ্ট, এজন্য আমাদের একটা চেকিং রাখতে হচ্ছে যাতে করে আমাদের এ্যারেতে জায়গা শেষ হয়ে গেলে আমরা আর ডাটা insert করবো না। তানাহলে arr তে ডাটা রাখবো আর top কে increase করবো।
আর pop করার জন্য ফাংশনটা হবে এরকম-
void pop()
{
    if(top<=0)
    {
        printf("Stack is empty\n");
    }
    else
    {
        top--;
        printf("Popped element: %d\n",arr[top]);
    }
}
এখানেও একটা চেকিং রাখতে হচ্ছে, যখন স্ট্যাকে আর কোন ডাটা থাকবে না তখনকার জন্য।
লক্ষ্য করার বিষয় হলো, যেহেতু আমাদের top সব সময় এক ঘর এগিয়ে থাকে, মানে এমন জায়গায় থাকে যেখানে ডাটা বসিয়ে top পরের ঘরে চলে যায় যেখানে এখনো ডাটা ইনসার্ট করা হয়নি, তাই আমরা pop করার সময় প্রথমে top কে একঘর আগে নিয়ে আসি, যেখানে শেষ ডাটাটা আছে। তারপর সেখান থেকে ডাটাটা নিয়ে নেই।

আর তারপর যদি দেখতে চাই আমাদের স্ট্যাকে কি কি ভ্যালু আছে তাহলে এভাবে দেখে নিতে পারি-

void printlist()
{
    int i;
    for(i=0;i<top;i++)
        printf("%d ",arr[i]);
    puts("");
}
ব্যস, এভাবেই আমাদের স্ট্যাকের কোডিং করা হয়ে গেলো।
পুরো কোড পাবে এখানে
স্ট্যাকের অপারেশনটা দেখতে হয় এরকম-
1-tile
আর আমরা যদি লিংকড লিস্ট দিয়ে ইমপ্লিমেন্টেশন করতে চাই, তাহলে আইডিয়া পুরোপুরি এ্যারের মতই। আগের মতই আলাদা আলাদা ফাংশনে Push, Pop এর কাজ হবে, শুধু এ্যারের বদলে লিংকড লিস্ট ব্যবহার হবে। লিংকড লিস্ট কিভাবে কোড করতে হয়আগের পোস্টে দেখিয়েছি। শুধু একটা জিনিস এখানে পরিবর্তন হবে। লিংকড লিস্টে আমরা লিস্ট এমনভাবে করেছি যাতে করে নতুন ভ্যালু লিস্টের প্রথমে যোগ হবে। আর স্ট্যাকের সুবিধার্থে আমরা লিস্ট এমনভাবে বানাবো যাতে করে লিস্টের শেষে ভ্যালু যোগ হয়। তাহলে আমরা স্ট্যাকের অপারেশনগুলো সহজে করতে পারবো। ভয় পাবার কারণ নেই, কোড প্রায় একই রকমই হয়।
লিংকড লিস্ট দিয়ে স্ট্যাকের কোড এখানে

তাহলে চলতে থাকুক কোডিং…………………………………..।

Want to like or share?:
0

4 comments

  1. হাতের কাছে এই রিলেটেড প্রবলেম আসলে আর্টিকেলের নিচে এড করে দিয়েন। 🙂

  2. ভোলাদি, তোমার লেখার জন্যে কি যে আগ্রহ নিয়ে বসে থাকি ! ! অনেক সহজ করে লেখো তুমি । 🙂
    যা হোক আমি বলছিলাম যে Array দিয়ে যদি stack implement করি তো under the hood আমার কোড তো অনেক মেমরি নষ্ট করবে । তার চেয়ে linked list দিয়ে করাটা মনে হয় ভালো হবে । আর আমার একটা প্রশ্ন ছিলো হে

    top=tmp;

    এখানে tmp কে top এ assign করবার পরে মনে হচ্ছে সব শেষে পরপর দুটা নোড (tmp -> top) একই থাকবে ।
    🙂 কোথাও ভুল করে থাকলে শুধরে দিও । আমি বিগিনার ।
    অগ্রিম ধন্যবাদ ।

    1. অবশ্যই এ্যারের চাইতে লিংকড লিস্ট দিয়ে স্ট্যাক ইমপ্লিমেন্ট করাটা বেটার। এখানে একেবারেই বিগিনারদের জন্য আগে স্ট্যাকের আইডিয়াটা সহজে বোঝানোর জন্য এ্যারে দিয়ে ইমপ্লিমেন্টেশন দেখানো হয়েছে। 🙂
      top=tmp
      এটা কোথায় লেখা? খুঁজে পেলাম না তো।

Leave a Reply

Your email address will not be published. Required fields are marked *