কিউ #

স্ট্যাকের মতই আরেকটি লিনিয়ার (Linear) ডাটা স্ট্রাকচার হল কিউ (Queue)। লিনিয়ার ডাটা স্ট্রাকচার বলতে বুঝায় যেখানে আইটেমগুলো ধারাবাহিকভাবে রয়েছে, যেমন: স্ট্যাক, কিউ, লিংকড (Linked) লিস্ট। বাংলায় কিউকে আমরা সারি বলতে পারি। তবে বুঝানোর সুবিধার্থে আমরা কিউ বলেই আপাতত চালিয়ে নেব।

কিউ হল কতগুলো আইটেমের এমন এক ধারাবাহিক সংগ্রহশালা (কালেকশন - collection) যেখানে নতুন আইটেমের সংযোজন (এনকিউ - enqueue) সংগ্রহশালার এক প্রান্তে আর পুরনো আইটেমের অপসারণ (ডিকিউ - dequeue) ঠিক তার বিপরীত প্রান্তে হয়। বোঝার সুবিধার্থে, যে প্রান্তে নতুন আইটেমের সংযোজন হয় সে প্রান্তকে আমরা পিছনের অংশ বা রিয়ার (rear) অথবা টেইল (tail - লেজ) বলতে পারি। আর যে প্রান্তে পুরনো আইটেমের অপসারণ হয় সে প্রান্তকে আমরা সামনের অংশ বা ফ্রন্ট (front) অথবা হেড (head - মাথা) বলতে পারি। বেশ গোলমেলে ব্যাপার-স্যাপার, তাই না? দুশ্চিন্তা করার কোন কারণ নেই। একটা গল্প বললেই বিষয়টা পরিষ্কার হয়ে যাবে।

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

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

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

অপারেশন #

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

enqueue(item) #

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

dequeue() #

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

is_empty() #

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

size() #

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

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

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

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

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

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

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

    def size(self):
        # returns the size of the queue
        return len(self.myqueue)

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

    def enqueue(self, item):
        # enqueue a item to the defined queue
        # insert(0, item) will insert "item" to the 0th position of the defined
        # list
        return self.myqueue.append(item)

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


def main():
    # defining the main function for the queue
    q = Queue()
    # q is an object of Queue class
    while True:
        print("1. Enqueue \n2. Dequeue \n3. Show \n4. 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 enqueue method
            print("Input item, you wanna enqueue:")
            item = input()
            q.enqueue(item)
            print("Congrats!", item, "has been enqueued.")
        elif case == 2:
            # in this case, we will call our dequeue method
            if q.is_empty():
                print("Sorry, the queue is empty.")
            else:
                print(q.dequeue(), "has been dequeued.")
        elif case == 3:
            # in this case, we will print the current condition of our queue
            if q.is_empty():
                print("Sorry, the queue is empty.")
            else:
                print("The current condition of our queue:",
                      q.myqueue)
        elif case == 4:
            # 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()

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