ডাটা স্ট্রাকচার : ডেক

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

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

অপারেশন Link to heading

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

add_front(item) Link to heading

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

add_rear(item) Link to heading

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

remove_front() Link to heading

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

remove_rear() Link to heading

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

is_empty() Link to heading

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

size() Link to heading

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

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

ইমপ্লিমেন্টেশন Link to heading

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

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

অ্যাপ্লিকেশন Link to heading

একটা ওয়ার্ড প্যালিনড্রোম (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()))

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

comments powered by Disqus