স্ট্যাক #

ডাটা স্ট্রাকচার নিয়ে কথা বলতে গেলে স্ট্যাক নিয়ে কথা একেবারে না বললেই নয়। শব্দটা আমি প্রথম শুনেছিলাম আমার এক বন্ধুর কাছ থেকে। ঘটনাটা বেশ মজার। কোন এক বোরিং ক্লাসে বসে ছিলাম। ভাবলাম সামনের বন্ধুটাকে কলম দিয়ে খুঁচিয়ে কিছুটা বিনোদন পাওয়া যেতে পারে। তো যেই ভাবা সেই কাজ।

সাধের ম্যাটাডোর অরবিট কলমটাকে সামনের দিকে বাগিয়ে বন্ধুর পশ্চাৎদেশে জোরসে একটা গুঁতো মারলাম। কিন্তু সে আমার গুঁতোতে তেমন একটা রেসপন্স করল না। আমি ভাবলাম রেসপন্স না করার দুটো কারণ হতে পারে। এক, ও ক্লাসের সবচেয়ে মনোযোগী ছাত্র আর দুই, ওর শরীরে গন্ডারের জিন রয়েছে। পরীক্ষা-নিরীক্ষা চালিয়ে আরো নিশ্চিত হবার জন্য আগের চেয়ে খানিক জোরসে আবার একটা গুঁতো মারলাম। এবার ব্যাটা গন্ডারের বংশধর ভয়ানক রেসপন্স করল। পিছন ফিরে চোখ রাঙিয়ে আমাকে হুমকি দিল-

আর একবার যদি গুঁতা মারস; তাইলে তোরে মাইরা, তোর হাড্ডি ভাইঙ্গা স্ট্যাক কইরা রাখমু।

এরকম হুমকির পরে গুঁতো কর্মসূচীতে আর তেমন একটা উৎসাহ পেলাম না। সেদিনের মত ইস্তফা দিয়ে বাসায় চলে আসলাম। বাসায় এসে ডিকশনারি ঘেঁটে দেখলাম, স্ট্যাক মানে স্তুপ। যাহোক, অনেক গপ্পোসপ্পো হল। এবার স্ট্যাক নিয়ে আসল কথায় আসা যাক।

সংক্ষেপে, স্ট্যাক হল স্তুপ। আর বিশদভাবে বলতে গেলে, স্ট্যাক হল কতগুলো আইটেমের এমন এক কাঠামোবদ্ধ (স্ট্রাকচারড - structured) সংগ্রহশালা (কালেকশন - collection) যেখানে নতুন আইটেমের সংযোজন (পুশ - push) বা পুরনো আইটেমের অপসারণ (পপ - pop) সংগ্রহশালার একই প্রান্তে হয়। ব্যাপারটা ঠিক বোঝা গেল না, তাই না? কোন ব্যাপার না। একটা উদাহরণ দিলেই ব্যাপারটা পরিষ্কার হয়ে যাবে।

পাঁচটা খাবার প্লেটের একটা স্তুপ (স্ট্যাক) কল্পনা করা যাক। আমরা যদি এই স্তুপে নতুন একটা প্লেট (আইটেম) সংযোজন (পুশ) করতে চাই তবে ষষ্ঠতম প্লেটটা স্তুপের একেবারে উপরে রাখতে হবে। এখন আমাদের কাছে ছয়টা প্লেটের একটা স্তুপ আছে। এবার যদি এই স্তুপ থেকে একটা প্লেট (আইটেম) অপসারণ (পপ) করতে চাই তবে ষষ্ঠতম প্লেটটাই কিন্তু অপসারণ করতে হবে। খেয়াল করলে দেখব, যে একই প্রান্তে এই কাজগুলো করছি সেটার একটা নাম দেয়া যায়- উপর বা টপ (Top)। আর এর অপর প্রান্তকে বলা যায় নিচ বা বেইস (Base)।

আমাদের ভিতর যারা অত্যন্ত বুদ্ধিমান তারা হয়ত এতক্ষণে বুঝে ফেলেছি যে এটা একটা লাস্ট-ইন-ফার্স্ট-আউট (LIFO) ডাটা স্ট্রাকচার। কারণ, আমরা সবার শেষে যে আইটেমটা সংযোজন (পুশ) করছি সেটাই কিন্তু সবার আগে অপসারণ (পপ) করছি। মানে, ঢুকছে সবার শেষে কিন্তু বের হচ্ছে সবার আগে। কি মজা!

অপারেশন #

এক নজরে এখন আমরা স্ট্যাকের সকল অপারেশন দেখব। সাধারণ পাঁচ ধরনের ফাংশন বা মেথডের মাধ্যমে এই অপারেশনগুলি সম্পাদিত হয়।

push(item) #

স্ট্যাকের উপরে (টপে) নতুন আইটেম সংযোজন করার জন্য এই ফাংশন বা মেথডটি ব্যবহার করা হয়। আর্গুমেন্ট বা প্যারামিটার হিসেবে আইটেমটাকে গ্রহণ করলেও এটি কোন কিছু রিটার্ন করে না।

pop() #

এই ফাংশন বা মেথডটি আর্গুমেন্ট বা প্যারামিটার হিসেবে কোন কিছু গ্রহণ না করলেও স্ট্যাকের একেবারে উপরের আইটেমটাকে রিটার্ন করে। এর পাশাপাশি উক্ত আইটেমটাকে স্ট্যাক থেকে অপসারণও (রিমুভ) করে।

peek() #

এই ফাংশন বা মেথডটি অনেকটা pop()-এর মতই। শুধু পার্থক্য হল এটি pop() এর মত স্ট্যাক থেকে আইটেম অপসারণ (রিমুভ) করে না।

is_empty() #

এটি একটি বুলিয়ান ফাংশন (বা মেথড)। স্ট্যাক খালি কিনা সেটি চেক করে True বা False রিটার্ন করে। এরও কোন প্যারামিটার নেই।

size() #

এই ফাংশন (বা মেথড) কোন আর্গুমেন্ট বা প্যারামিটার গ্রহণ করে না এবং স্ট্যাকের মোট আইটেম সংখ্যা রিটার্ন করে।

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

ইমপ্লিমেন্টেশন #

যেকোন স্ট্রাকচারড বা অবজেক্ট-অরিয়েন্টেড প্রোগ্রামিং ল্যাঙ্গুয়েজেই আমরা স্ট্যাককে ইমপ্লিমেন্ট করতে পারি। শুধু খেয়াল রাখতে হবে, প্রোগ্রামটিতে যেন স্ট্যাকের সকল অপারেশন করা যায়। স্ট্যাকের আইটেমগুলো স্টোর করার জন্য আমাদের একটি অ্যারে বা অ্যারের মত কিছু লাগবে। অ্যারের মত এইজন্য বললাম কারণ পাইথনে অ্যারে নেই কিন্তু অ্যারের মত (অ্যারের চেয়েও অ্যাডভান্সড) লিস্ট রয়েছে। যাহোক, অ্যারে বা লিস্টের ইনডেক্স জিরো হবে স্ট্যাকের বেইস আর সর্বোচ্চ ইনডেক্স হবে স্ট্যাকের টপ। যখন বেইস আর টপ সমান হবে তখন বুঝতে হবে স্ট্যাকের ভিতরে কিছু নেই, এটি এখন খালি (empty)। এরপর উপরে বলা পাঁচ ধরনের ফাংশন (বা মেথড) ইমপ্লিমেন্ট করতে হবে।

এবার আমরা স্ট্যাককে পাইথনে (পাইথন ৩.x) ইমপ্লিমেন্ট করব। সবাই সবারমত করে চেষ্টা করব। উদাহরণ হিসেবে এটা দেখতে পারি:

class Stack():
    """
    @description: This class defines several methods for stack.
    """

    def __init__(self):
        # defining a list which will act as stack container
        self.mystack = []

    def size(self):
        # returns the size of stack
        return len(self.mystack)

    def is_empty(self):
        # checks whether the stack is empty or not
        if self.size() > 0:
            return False
        else:
            return True

    def push(self, item):
        # push an item to the defined stack
        return self.mystack.append(item)

    def pop(self):
        # pop an item from defined stack
        if self.is_empty():
            print("Sorry, the stack is empty.")
        else:
            return self.mystack.pop()

    def peek(self):
        # peeks an item from the stack means won't remove
        # it
        if self.is_empty():
            print("Sorry, the stack is empty.")
        else:
            return self.mystack[len(self.mystack) - 1]


def main():
    # defining the main function for the stack
    s = Stack()
    # s is an object of Stack class
    while True:
        print("1. Push \n2. Pop \n3. Peek \n4. Show \n5. Quit")
        print("\nWhat do you wanna do now?")
        case = int(input())
        # starting something, equivalent to Switch statement in C/C++
        if case == 1:
            # in this case, we will call our push method
            print("Input item, you wanna push to stack:")
            item = input()
            s.push(item)
            print("Congrats!", item, "has been pushed.")
        elif case == 2:
            # in this case, we will call our pop method
            if s.is_empty():
                print("Sorry, the stack is empty.")
            else:
                print(s.pop())
        elif case == 3:
            # in this case, we will call our peek method
            if s.is_empty():
                print("Sorry, the stack is empty.")
            else:
                print(s.peek(), "has been peeked.")
        elif case == 4:
            # in this case, we will print the current condition of our
            # stack
            if s.is_empty():
                print("Sorry, the stack is empty.")
            else:
                print("The current condition of our stack:", s.mystack)
        elif case == 5:
            # in this case, we will quit our script
            print("The script is gonna quit.")
            quit()
        else:
            print("Oops! Wrong Choice.")
            main()

if __name__ == "__main__":
    main()

প্রোগ্রামটা আর ব্যাখ্যা করলাম না। আশা করি, সবাই বুঝতে পেরেছি। আচ্ছা, বুঝলাম কিনা সেটা কিভাবে টেস্ট করে দেখা যায়? এক মগ কফি খেয়ে সবাই এখন হ্যাকারর‍্যাংক ও হ্যাকারআর্থের স্ট্যাক রিলেটেড প্রব্লেমগুলো সলভ করব। আর সলভ করার আগ পর্যন্ত কারো সাথে কোন কথা নাই।