ডেক

ডেক #

ইতিমধ্যে আমরা স্ট্যাককিউ সম্পর্কে জেনেছি। এগুলো হল লিনিয়ার ডাটা স্ট্রাকচার ও একমুখো সাপ। একমুখো সাপ বললাম কারণ, স্টাক ও কিউতে আইটেম একটিমাত্র প্রান্তে ঢুকতে পারে ও একটিমাত্র প্রান্ত থেকে বের হতে পারে। আরেকটু পরিষ্কার করে বললে, স্ট্যাকের ক্ষেত্রে যে প্রান্তে আইটেম ঢুকবে সেই প্রান্ত দিয়েই বের হবে আর কিউয়ের ক্ষেত্রে ঢুকবে এক প্রান্ত দিয়ে কিন্তু বের হবে অন্য প্রান্ত দিয়ে। লক্ষণীয় বিষয় হল, দুই ক্ষেত্রেই ঢোকার বা বের হবার রাস্তা কেবলমাত্র একটি। কিন্তু ডেক (Deque) হল একটি দুমুখো সাপ। এর দুই মুখেই আইটেম ঢুকতে পারে অথবা দুই মুখ থেকেই আইটেম বের হতে পারে।

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

অপারেশন #

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

add_front(item) #

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

add_rear(item) #

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

remove_front() #

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

remove_rear() #

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

is_empty() #

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

size() #

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

একেবারে স্ট্যাক ও কিউয়ের অপারেশনগুলোর মিশেল তাই না? ওহ! সাবধান! এই মিশেল কিন্তু আবার মিশেল ওবামা না।

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

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

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

class Deque():
    """
    @description: This class defines several methods for deque.
    """

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

    def size(self):
        # returns the size of deque
        return len(self.mydeque)

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

    def add_front(self, item):
        # adds an item at the rear of defined deque
        return self.mydeque.insert(0, item)

    def add_rear(self, item):
        # adds an item at the front of defined deque
        return self.mydeque.append(item)

    def remove_front(self):
        # pop an item from defined deque
        if self.is_empty():
            print("Sorry, the deque is empty.")
        else:
            return self.mydeque.pop(0)

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


def main():
    # defining the main function for the deque
    d = Deque()
    # d is an object of Deque class
    while 1:
        print("1. Add at front \n2. Add at rear \n3. Remove from front \n4. Remove from rear \n5. Show \n6. 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 add_front function
            print("Input item, you wanna add at front :")
            item = input()
            d.add_front(item)
            print("Congrats!", item, "has been added at front.")
        elif case == 2:
            # in this case, we will call our add_rear function
            print("Input item, you wanna add at rear :")
            item = input()
            d.add_rear(item)
            print("Congrats!", item, "has been added at rear.")
        elif case == 3:
            # in this case, we will call our remove_front function
            if d.is_empty() == True:
                print("Sorry, the deque is empty.")
            else:
                print(d.remove_front())
        elif case == 4:
            # in this case, we will call our remove_rear function
            if d.is_empty() == True:
                print("Sorry, the deque is empty.")
            else:
                print(d.remove_rear())
        elif case == 5:
            # in this case, we will print the current condition of our deque
            if d.is_empty() == True:
                print("Sorry, the deque is empty.")
            else:
                print("The current condition of our deque:", d.mydeque)
        elif case == 6:
            # 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()

অ্যাপ্লিকেশন #

একটা ওয়ার্ড প্যালিনড্রোম (palindrome) কিনা তা চেক করে দেখার জন্য ডেক ব্যবহার করা যায়। কিছু কিছু শব্দ আছে যেগুলোকে আমরা উল্টে-পাল্টে যেভাবেই পড়িনা কেন, শব্দটা বদলায় না। যেমন: civic, level, madam। এগুলোকে প্যালিন্ড্রোম বলে। যাহক, যে শব্দটা চেক করব সেটা একটা ডেকের ভিতর রেখে ডেকের ফ্রন্ট ও রিয়ার থেকে একটা একটা করে স্ট্রিং নিয়ে চেক করে দেখা যেতে পারে ঐ দুটি স্ট্রিং একই কিনা। এভাবে পর্যায়ক্রমে সবগুলো চেক করে দেখা যেতে পারে। তারপরে সিদ্ধান্ত নেয়া যায় - শব্দটি প্যালিন্ড্রোম? নাকি নয়?

from Deque import Deque
# Deque is already defined in Deque.py

def is_pallindrome(word):
    d = Deque()

    if len(word) > 1:
        for char in word:
            d.add_rear(char)

        equal = True
        while d.size() > 1 and equal:
            first_char = d.remove_front()
            last_char = d.remove_rear()
            if first_char == last_char:
                equal = True
            else:
                return False

        return True
    else:
        return 'The word should consist of at least two chars.'

if __name__ == '__main__':
    while True:
        print('Please, input the word to check:')
        print(is_pallindrome(input()))

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

মন্তব্য করুন