স্ট্যাক(Stack) ডাটা-স্ট্রাকচার ইন পাইথন

স্ট্যাক(Stack) ডাটা-স্ট্রাকচার ইন পাইথন

28 ফেব্রুয়ারি 2022

কম্পিউটার সাইন্সে কমন এবং বহুল ব্যবহৃত ডাটা- স্ট্রাকচার গুলোর মাঝে Stack একটি । আমরা আজকে এই ডাটা- স্ট্রাকচার সমন্ধে শিখতে যাচ্ছি, Stack কি তা জানার আগে একটু বোঝার চেষ্টা করি যে লিনিয়ার(Linear) ডাটা- স্ট্রাকচার কি ?

লিনিয়ার(Linear) ডাটা-স্ট্রাকচার কি ?

যেসব ডাটা- স্ট্রাকচারে ডাটা গুলো একটি নির্দিষ্ট সিকুয়েন্সিয়াল(sequential) অর্ডারে(order) থাকে অর্থাৎ ডাটা সমূহ নির্দিষ্ট ভাবে সাজানো গোছানো অবস্থায় রাখা হয় । যেখানে ডাটা সমূহ একটি আরেকটির সাথে কানেক্টেড থাকে এবং খুব দ্রুত বিভিন্ন অপারেশনসমূহ সম্পন্ন করা হয় যেমন - ট্রাভারসিং(Traversing), সার্চিং(Searching), মারজিং(Merging) ইত্যাদি তাদেরকেই লিনিয়ার(Linear) ডাটা- স্ট্রাকচার বলা হয়।

Stack কি ?

Stack একটি লিনিয়ার(Linear) ডাটা- স্ট্রাকচার যা LIFO প্যাঁরাডাইম(paradigm) মেনে চলে । LIFO এর পূর্ণরূপ হইলো - Last In First Out অর্থাৎ Stack এ কোনো একটা ভ্যালু শেষে সংযোজন করা হইলে তা প্রথমেই বিয়োজন হবে। এখন একটু রিয়েল লাইফ উদাহরণ দেওয়া যাক -

রিয়েল লাইফ উদাহরণ -

অনেক স্বপ্ন ছিলো আপনার মামার মেয়েকে বিয়ে করবেন কিন্তু আজ সেই মেয়ের বিয়ে। আমি খুবই দুঃখিত যে বরটা আপনাকে বানাতে পারলাম নাহ । তবে আপনি সেই বিয়েতে একজন ওয়ার্কার যে কিনা মেহমানদের মাঝে থালা(Plate) সার্ভ করার দায়িত্ব পালন করবেন ।

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

এইখানে একটা জিনিস খেয়াল করেছেন ? এই যে আপনি বেসিন থেকে থালা একটি একটি করে হাতে নিচ্ছেন এবং তা আবার একটি একটি করে মেহমানদের মাঝে সার্ভ করতেছেন ।

ধরি যে, এইবার আপনি ৮টি থালা বেসিন থেকে হাতে নিয়েছেন । যখন ৮টি থালার ১ম টি হাতে নিয়েছেন তখন আপনার হাতে থালা একটি । তারপর যখন ২ নাম্বার থালা হাতে নিলেন তখন আপনার হাতে থালা দুইটি এবং প্রথম যে থালাটা হাতে নিয়েছেন সেইটা কিন্তু এখন ২য় থালার নিচে। এভাবে পর্যায়ক্রমে আপনি ৮ টি থালা হাতে নিয়েছেন ।

তাহলে সবশেষে যে থালাটা হাতে নিলেন অর্থাৎ ৮ নাম্বার থালা সেইটা কিন্তু এখন সবার ওপরে । এবং প্রথমে যে থালাটা নিয়েছিলেন সেইটা কিন্তু এখন সবার শেষে । তাই নাহ ?

plate.jpg

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

তাহলে সারমর্ম এই যে, বেসিন থেকে সর্বশেষে যে থালাটা আপনি হাতে নিয়েছিলেন তা সর্বপ্রথম হাত থেকে সরিয়ে ফেললেন । এবং সর্বপ্রথম যে থালাটা হাতে নিয়েছিলেন তা সর্বশেষে হাত থেকে সরিয়ে ফেললেন।

এখানেও কিন্তু LIFO প্যাঁরাডাইম(paradigm) মেনে চললো অর্থাৎ - Last In First Out, শেষে যে থালাটা হাতে ইন করলেন প্রথেমেই সেইটাকে আউট করে দিলেন । আশা করি এখন আপনি Stack সম্পর্কে Theoretical একটা ধারণা পেলেন।

যেহেতু আমরা মোটামোটি বুঝি যে, Stack ডাটা- স্ট্রাকচার কি তাহলে চলুন এখন আমরা খুব সহজেই এইটা কে ইমপ্লিমেন্ট(implement) অর্থাৎ তৈরি করে ফেলি ।

Stack ডাটা-স্ট্রাকচার ইমপ্লিমেন্ট(implement) করার আগে :-

যে কোনো ল্যাংগুয়েজেই হোক নাহ কেনো Stack ইমপ্লিমেন্ট(implement) করার সময় মাস্ট(must) আমাদেরকে দুইটা মেথড তৈরি করতেই হবে -

১। push - Stack এ আইটেম সংযোজন ।

২। pop - Stack থেকে আইটেম বিয়োজন ।

এইখানে মেথডস নেইম যে push এবং pop ই হবে সেরকম বাধা- ধরা কোনো নিয়ম নেই । আপনি চাইলে add, remove বা আপনার সুবিধা- মতো যেকোনো নেইম দিতে পারেন ।

তবে এই দুইটা মেথড ছাড়াও Stack এ আমাদের প্রয়োজন মতো অনেক মেথডস তৈরি করতে পারি ।

Stack এ আমরা যে মেথডস গুলো তৈরি করতে যাচ্ছি :-

1। push() - stack এ আইটেম সংযোজন হবে।

2। pop() - stack থেকে আইটেম বিয়োজন হবে।

3। size() - stack এ আইটেম কতগুলো আছে তা জানা যাবে।

4। isEmpty() - stack খালি কি নাহ তা জানা যাবে।

5। topElement() - stack থেকে প্রথম আইটেম নেওয়া যাবে ।

6। tailElement() - stack থেকে শেষ আইটেম নেওয়া যাবে ।

Stack ইমপ্লিমেন্ট(implement) :-

Stack ইমপ্লিমেন্ট(implement) করতে আমি লিস্ট(list) এবং ক্লাস(class) কে বেছে নিবো । তবে লিঙ্কড-লিস্ট(linked-list) দিয়েও চাইলে করতে পারেন । সামনের কোনোদিন সময় করে লিঙ্কড-লিস্ট(linked-list) দিয়ে কিভাবে Stack` ইমপ্লিমেন্ট(implement) করতে হয় তা নিয়ে একটি Article লিখার চেষ্টা করবো ।

ক্লাস(class) ডিফাইন :-

class Stack:
    # code here

কন্সট্রাক্টর(constructor) তৈরি :-

def __init__(self):
    self.data = []

এখানে একটি constructor ফাংশন নিয়েছি এবং data নামে একটা প্রোপার্টি নিয়েছি যা মুলত একটা লিস্টকে হোল্ড করে । এই লিস্টই মুলত Stack এর আইটেমগুলো কে কনট্রোল করবে ।

push method :-

def push(self, item):
    self.data.append(item)

লিস্টের append মেথডের সাহায্য নেওয়া হয়েছে যা এলিমেন্টকে খুব সহজেই Stack এর শেষে যুক্ত করে দিবে ।

pop method :-

def pop(self):
    if(len(self.data)):
        return self.data.pop()
    else:
        return "Pop failed!"

এখানে বলা হয়েছে যে যদি Stack এর লেন্থ শুন্য(0) থেকে বড় হয় তাহলে Stack থেকে শেষের এলিমেন্টকে ডিলিট করে দিবে। শুন্য(0) থেকে বড় মানে Stack এ এলিমেন্ট আছে। আর যদি Stack এ এলিমেন্ট নাহ থাকে তাহলে Pop failed! রিটার্ন করবে ।

size method :-

def size(self):
    return len(self.data)

Stack এ কতোগুলো আইটেম আছে তা এই সাইজ(size) মেথড রিটার্ন করবে ।

isEmty method :-

def isEmpty(self):
    return len(self.data) == 0

Stack খালি কি নাহ তা জানা যাবে isEmty এর সাহায্যে । যদি stack এ আইটেম থাকে তাহলে false আইটেম নাহ থাকলে true রিটার্ন করবে।

topElement method :-

def topElement(self):
    if(len(self.data)):
        return self.data[0]
    else:
        return "stack is empty!"

Stack থেকে প্রথম এলিমেন্ট নেওয়া যাবে topElement মেথডের সাহায্যে ।

tailElement method :-

def tailElement(self):
    if(len(self.data)):
        return self.data[-1]
    else:
        return "stack is empty!"

Stack থেকে শেষ এলিমেন্ট নেওয়া যাবে tailElement মেথডের সাহায্যে ।

Final Stack :-

class Stack:
    # constructor
    def __init__(self):
        self.data = []

    # push method
    def push(self, item):
        self.data.append(item)

    # pop method
    def pop(self):
        if(len(self.data)):
            return self.data.pop()
        else:
            return "Pop failed!"

    # isEmpty method
    def isEmpty(self):
        return len(self.data) == 0

    # size method
    def size(self):
        return len(self.data)

    # topElement method
    def topElement(self):
        if(len(self.data)):
            return self.data[0]
        else:
            return "stack is empty!"

    # tailElement
    def tailElement(self):
        if(len(self.data)):
            return self.data[-1]

        else:
            return "stack is empty!"

আপনি চাইলে stack এ প্রয়োজন মতো আরও অনেক মেথড যুক্ত করতে পারেন । এখন আমাদের তৈরি করা stack টেস্ট করে দেখবো যে সব কিছু ঠিকমতো কাজ করছে কি নাহ ।

Create a Stack :-

stack = Stack()

Add Item To Stack :-

stack.push('torikus')
stack.push('fahim')
stack.push('afifa')

# ['torikus', 'fahim', 'afifa']

stack এ সবশেষে afifa কে সংযোজন করা হয়েছে এখন যদি বিয়োজন করি তাহলে -

Remove Last Item To Stack :-

print(stack.pop())  # 'afifa'
# [ 'torikus', 'fahim' ]

যেহেতু stack এ সবশেষে afifa কে সংযোজন করা হয়েছে তাই pop() করার পর afifa কেই প্রথম বিয়োজন করে ফেলছে ।

size in stack :-

print(stack.size())  # 2

যেহেতু, stack এ দুইটি আইটেম আছে তাই আউটপুট হিসেবে 2 কেই রিটার্ন করা হয়েছে।

Check If Stack Is Empty :-

print(stack.isEmty())
# false

যেহেতু, stack এ আইটেম আছে তাই আউটপুট হিসেবে false কেই রিটার্ন করা হয়েছে যদি আইটেম নাহ থাকতো তাহলে true রিটার্ন করতো। আমাদের stack ঠিক-ঠাক মতো কাজ করতেছে। আশা করি আপনি বুঝতে পেরেছেন ।

শেষের কথা :-

কোনো একটি বিষয় একবারে নাহ বুঝলে বার বার চেষ্টা করতে হয় । আপনারা যদি কোথাও বুঝতে নাহ পারেন তাহলে আরেকবার দেখতে পারেন । এতে অনেক কিছুই পরিস্কার হয়ে যাবে।

যদি এই আর্টিকেলে কোনো প্রকার ভূল পেয়ে থাকেন তাহলে আমাকে জানাতে ভূলবেন নাহ প্লিজ । আমরা শিখতে চাই সেটা ভূল থেকে হলেও ।