Command Palette

Search for a command to run...

স্ট্যাক(Stack) ডাটা-স্ট্রাকচার ইন পাইথন
shakilbabu
Shakil Babu
·10 min read

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

কম্পিউটার সাইন্সে কমন এবং বহুল ব্যবহৃত ডাটা- স্ট্রাকচার গুলোর মাঝে 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 ঠিক-ঠাক মতো কাজ করতেছে। আশা করি আপনি বুঝতে পেরেছেন ।

শেষের কথা :-

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

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

Comments

  • Type and hit enter to post comment
  • For multiline comments, use Shift + Enter
  • You can use markdown syntax for formatting

Cookie Consent

We use cookies to enhance your browsing experience and analyze our traffic. By clicking "Accept", you consent to our use of cookies.