কিউ(Queue) ডাটা-স্ট্রাকচার ইন পাইথন

 

কম্পিউটার সাইন্সে আরও একটি কমন এবং বহুল ব্যবহৃত ডাটা-স্ট্রাকচার হলো Queue । আমরা আজকে এই ডাটা-স্ট্রাকচার সমন্ধে শিখতে যাচ্ছি, তবে আশা করি যে আপনি Stack ডাটা-স্ট্রাকচার সম্পর্কে জানেন।

যদি নাহ যেনে থাকেন তাহলে এখানে পড়ুন ।

- Queue কি ?

Queue একটি লিনিয়ার(Linear) ডাটা-স্ট্রাকচার যা FIFO প্যাঁরাডাইম(paradigm) মেনে চলে । FIFO এর পূর্ণরূপ হইলো - First In First Out অর্থাৎ Queue এ কোনো একটা ভ্যালু প্রথমে সংযোজন করা হইলে তা প্রথমেই বিয়োজন হবে। এখন একটু রিয়েল লাইফ উদাহরণ দেওয়া যাক -

- রিয়েল লাইফ উদাহরণ -

গত ব্লগে আপনার মামার মেয়ের তো বিয়ে হয়ে গেলো কিন্তু সেই বিয়েতে আপনি থালা বিতরন ছাড়া আর কিছুই করতে পারলেন নাহ । কিন্তু আপনি কি হাল ছেড়ে দেওয়ার মতো মানুষ ? নাহ অবশ্যই নাহ ।

হ্যাঁ আপনি আপনার মামাতো বোন কে পান নাই তাতে কি হয়েছে পৃথিবীতে কি মেয়ের অভাব নাকি ? তাই আপনিও আপনার মামার মেয়ের মতো বিয়ে করে ফেললেন । এখন আপনার মামাতো বোন কে তো দেখাতে হবে নাকি ? তাই আপনি প্ল্যান করলেন যে, হানিমুনে যাবেন দেশের কোথাও।

এই সুবাধে আপনি আগামিকালের টিকিট আজকেই বুক করতে গেলেন কিন্তু ওমা এ কি!

টিকিট কাউন্টারে তো অনেক লোক লাইন হয়ে দাঁড়িয়ে আছে । এবং তারা সিরিয়াল মোতাবেক একজনের পর একজন টিকিট নিচ্ছে । এখন আপনার সিরিয়াল ধরেন ১৮ নম্বর। তাহলে যখন আপনার সিরিয়াল আসবে তখনই আপনি টিকিট নিতে পারবেন ।

এখন আপনি মনে মনে ভাবতেছেন যে, ইস! যদি খানিকটা আগে আসতে পারতাম তাহলে আগেই যাইতাম । আসলেই, আগে আসলে আগেই যাইতে পারতেন । কিন্তু কি আর করার ।

 

আশা করি আপনি এখানে Queue ডাটা-স্ট্রাকচারের আচরণ ধরতে পেরেছেন । যদি এখনও আপনার খাটাস ব্রেইনে কিছু নাহ ঢুকে থাকে তাহলে চলেন আরেকটু বোঝা-বুঝি সেরে ফেলা যাক -

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

এভাবে পর পর ৬ জন মানুষ তাদের সিরিয়াল মেইন্টেইন করে টিকিট নিয়ে সেখান থেকে চলে যাবে। তাহলে বিষয়টা দাড়ালো যে, প্রথম যে মানুষটা লাইনে ইন হইলো সেই মানুষটাই প্রথমেই টিকিট নিয়ে লাইন থেকে আউট হয়ে গেলো । তাহলে কিন্তু এখানেও FIFO প্যাঁরাডাইম(paradigm) মেনে চললো অর্থাৎ - First In First Out।

- Common operations on Queue -

যে কোনো ল্যাংগুয়েজেই হোক নাহ কেনো Queue ইমপ্লিমেন্ট(implement) করার সময় মাস্ট(must) আমাদেরকে দুইটা মেথড তৈরি করতেই হবে-

1. enqueue - Queue এ আইটেম সংযোজন ।
2. dequeue - Queue থেকে আইটেম বিয়োজন ।

এইখানে মেথডস নেইম যে enqueue এবং dequeue ই হবে সেরকম বাধা-ধরা কোনো নিয়ম নেই । আপনি চাইলে add , remove বা আপনার সুবিধা-মতো যেকোনো নেইম দিতে পারেন । তবে এই দুইটা মেথড ছাড়াও Queue এ আমাদের প্রয়োজন মতো অনেক মেথডস তৈরি করতে পারি ।

- Queue এ আমরা যে মেথডস গুলো তৈরি করতে যাচ্ছি -

1. enqueue() - Queue এ আইটেম সংযোজন ।

2. dequeue() - Queue থেকে আইটেম বিয়োজন ।

3. size() - Queue এ আইটেম কতগুলো আছে তা জানতে।

4. isEmpty() - Queue খালি কি নাহ তা জানতে।

5। topElement() - Queue থেকে প্রথম আইটেম নেওয়া যাবে ।

6। tailElement() - Queue থেকে শেষ আইটেম নেওয়া যাবে ।

- Implementing a queue -

Queue ইমপ্লিমেন্ট(implement) করতে আমি লিস্ট(list) এবং ক্লাস(class) কে বেছে নিবো । তবে লিঙ্কড-লিস্ট(linked-list) দিয়েও চাইলে করতে পারেন । তবে, সামনের কোনোদিন সময় করে লিঙ্কড-লিস্ট(linked-list) দিয়ে কিভাবে Queue ইমপ্লিমেন্ট(implement) করতে হয় তা নিয়ে একটি Article লিখার চেষ্টা করবো ।

- ক্লাস(class) ডিফাইন -

class Queue :
    # code here

- কন্সট্রাক্টর(constructor) তৈরি -

def __init__(self) :
    self.data = []

এখানে একটি constructor ফাংশন নিয়েছি এবং data নামে একটা প্রোপার্টি নিয়েছি যা মুলত একটা লিস্টকে হোল্ড করে । এই লিস্টই মুলত Queue এর আইটেমগুলো কে কনট্রোল করবে ।

- enqueue() method -

এই মেথডের সাহায্যে কোনো আইটেমকে Queue এর প্রথমে সংযোজন করা যাবে ।

def enqueue(self, item):
    self.data.append(item)

লিস্টের append মেথডের সাহায্য নেওয়া হয়েছে যা এলিমেন্টকে খুব সহজেই Queue এ যুক্ত করে দিবে ।

- dequeue() method -

def dequeue(self):
    if len(self.data):
        return self.data.pop(0)
    else:
        return "dequeue failed!"

এখানে বলা হয়েছে যে যদি Queue এর লেন্থ শুন্য(0) থেকে বড় হয় তাহলে Queue থেকে শেষের এলিমেন্টকে ডিলিট করে দিবে। শেষের এলিমেন্ট সেইটাই যেইটা Queue এ প্রথমে এড করা হবে । আর বুঝতেই পারছি যে, শুন্য(0) থেকে বড় মানে Queue এ এলিমেন্ট আছে।

আর যদি Queue এ এলিমেন্ট নাহ থাকে তাহলে dequeue failed! রিটার্ন করবে ।

- size method -

Queue এ কতোগুলো আইটেম আছে তা এই সাইজ(size) মেথড রিটার্ন করবে ।

def size(self) :
    return len(self.data);

- isEmty method -

Queue খালি কি নাহ তা জানা যাবে isEmty() মেথডের এর সাহায্যে । যদি Queue এ আইটেম থাকে তাহলে false আইটেম নাহ থাকলে true রিটার্ন করবে।

def isEmpty(self):
    return len(self.data) == 0

- topElement method -

def topElement(self):
    if(len(self.data)):
        return self.data[0]
    else:
        return "queue is empty!"

Queue থেকে প্রথম এলিমেন্ট নেওয়া যাবে topElement মেথডের সাহায্যে ।

- tailElement method -

def tailElement(self):
    if(len(self.data)):
        return self.data[-1]
    else:
        return "queue is empty!"

Queue থেকে শেষ এলিমেন্ট নেওয়া যাবে tailElement মেথডের সাহায্যে ।

- Final Queue -

class Queue:
    # constructor
    def __init__(self):
        self.data = []

    # enqueue method
    def enqueue(self, item):
        self.data.append(item)

    # dequeue method
    def dequeue(self):
        if len(self.data):
            return self.data.pop(0)
        else:
            return "dequeue failed!"

    # size method
    def size(self):
        return len(self.data)

    # isEmpty method
    def isEmpty(self):
        return len(self.data) == 0

    # topElement method
    def topElement(self):
        if(len(self.data)):
            return self.data[0]
        else:
            return "queue is empty!"

    # tailElement
    def tailElement(self):
        if(len(self.data)):
            return self.data[-1]
        else:
            return "queue is empty!"

আপনি চাইলে Queue এ প্রয়োজন মতো আরও অনেক মেথড যুক্ত করতে পারেন । এখন আমাদের তৈরি করা Queue টেস্ট করে দেখবো যে সব কিছু ঠিকমতো কাজ করছে কি নাহ ।

- Create a Queue -

# create a queue
queue = Queue();

- Add Item To Queue -

queue.enqueue("shakil");
queue.enqueue("torikus");
queue.enqueue("morshed");
queue.enqueue("afifa");

# queue
[ 'afifa', 'morshed', 'torikus', 'shakil' ]

যেহেতু queue এ সর্বপ্রথমে shakil কে সংযোজন করা হয়েছে এখন যদি বিয়োজন করি তাহলে -

- Remove last item which is the first item -

print(queue.dequeue()); # shakil

# [ 'afifa', 'morshed', 'torikus' ]

যেহেতু queue এ সর্বপ্রথম shakil কে সংযোজন করা হয়েছে তাই dequeue() করার পর shakil কেই প্রথম বিয়োজন করে ফেলছে ।

- Length in Queue -

print(queue.size());
# 3

আমরা দেখতে পাইতেছি যে, queue এ তিনটি আইটেম আছে তাই আউটপুট হিসেবে 3 কেই রিটার্ন করা হয়েছে।

- Check if queue is empty -

print(queue.isEmty());
# false

যেহেতু, queue এ আইটেম আছে তাই আউটপুট হিসেবে false কেই রিটার্ন করা হয়েছে যদি আইটেম নাহ থাকতো তাহলে true রিটার্ন করতো। আমাদের queue ঠিক-ঠাক মতো কাজ করতেছে।

- শেষের কথা -

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

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