লিনিয়ার ডাটা স্ট্রাকচারের মধ্যে অন্যতম ডাটা স্ট্রাকচার হচ্ছে কিউ। আমরা এর আগে Stack DS নিয়ে জেনেছিলাম। Stack DS LIFO প্রিন্সিপাল ফলো করে। অর্থাৎ , Stack এ যে ডাটা শেষে ইন্সার্ট হয় সেটি সবার আগে ডিলিট হয়। তবে Queue FIFO প্রিন্সিপাল ফলো করে। FIFO হলো First In First Out

FIFO এর সাথে টিকিট কাউন্টারের তুলনা দেয়া যেতে পারে। টিকিট কাউন্টারে টিকিট কাট্রা জন্য যে আগে লাইনে দাঁড়ায় সেই আগে লাইন থেকে বের হয়। Queue অ সেম। যে ডাটা আগে ইন্সার্ট হবে সেটি আগে ডিলিট হবে।

Queue এর কয়েকটি ধরন আছে । ১) General Queue ২) Circular Queue ৩) DeQueue
তবে এই আর্টিকেলে আমরা General Queue এর Insertion(enQueue) / Deletion(deQueue) / Traversing নিয়ে আলোচনা করবো। আগে কোড লিখবো এবং পরে কোডের প্রতিটা লাইন ব্যাখ্যা

EnQueue : কিউতে ডাটা ইন্সার্ট করাকে EnQueue বলে। কিউতে ডাটা ইন্সার্ট হয় rear থেকে
DeQueue : কিউ থেকে ডাটা ডিলিট করাকে DeQueue বলে। কিউতে ডাটা ডিলিট হয় front থেকে

Structure of a Queue class

class Queue:
    def __init__(self , size):
        self.queue = [None]*size
        self.rear = -1
        self.front = -1
    def isFull(self):
        return self.rear == len(self.queue) - 1
    def isEmpty(self):
        return self.front == -1 and self.rear == -1
    def enQueue(self):
        pass
    def deQueue(self):
        pass
    def traverse(self):
        pass

init() method

→ অবজেক্ট তৈরি হওয়ার সময় এই মেথড কল হয়। যেহেতু এটি Array ভিত্তিক Queue সেহেতু Array এর একটি সাইজ নির্ধারন করে দিতে হবে আমাদেরকে। তারপর সেই সাইজের একটি Array ইনিশিয়ালাইজ করা হয়েছে। আপাদত সবগুলো ইন্ডেক্সে ভ্যালু হিসেবে None থাকবে। সাথে self.rear এবং self.front নামে দুইটি ইন্সট্যান্স ভ্যারিয়েবল ইনিশিয়ালাইজ করা হয়েছে। self.rear সর্বশেষ ডাটার ইন্ডেক্স স্টোর করে এবং self.front সবার সামনে থাকা ডাটার ইন্ডেক্স স্টোর করে।

isFull() method

→ Queue তে সবগুলো জায়গা ভরাট আছে নাকি সেটা চেক করে রিটার্ন করা এই মেথডের কাজ। আমরা একটি ইন্সট্যান্স ভ্যারিয়েবল ইনিশিয়ালাইজ করেছিলাম self.rear নামে , সেই self.rear যদি Queue এর ম্যাক্সিমাম ইন্ডেক্স এর সমান হয় তাহলে বুঝতে হবে এখানে জায়গা খালি নেই। ম্যাক্সিমাম ইন্ডেক্স হবে Size of array - 1

isEmpty() method

→ Queue খালি কিনা সেটা চেক করে রিটার্ন করা এি মেথডের কাজ। যদি Queue এর front এবং rear = -1 হয় তাহলে বুঝতে হবে কিউতে কিছু নেই। যেহেতু Array এর ইন্ডেক্সিং শুরু হয় ০ থেকে সেই জন্য আমরা -১ ব্যাবহার করেছি।

EnQueue Operation

def enQueue(self , data):
    if self.isFull():
        raise ValueError("The Queue is full")
    elif self.isEmpty():
        self.front += 1
        self.rear += 1
        self.queue[self.rear] = data
    else:
        self.rear += 1
        self.queue[self.rear] = data

Explanation / Algorithm
→ সবার আগে চেক করা হয়েছে কিউতে জায়গা ফুল কিনা ! যদি ফুল হয় তাহলে ডাটা ইন্সার্ট করা যাবে না।
→ পরে চেক করা হয়েছে কিউ একদম খালি কিনা ! যদি খালি হয় তাহলে rear এবং front এর মান ১ বাড়াতে হবে এবং rear index এ ডাটা ইন্সার্ট করতে হবে। কারন , Queue তে ডাটা ইন্সার্ট হয় rear থেকে। যদি এই কন্ডিশন ট্রু না হয় তবে পরের স্টেপে যেতে হবে।
→ কিউ একদম খালি না হলে শুধুমাত্র rear এর মান এক বাড়াতে হবে এবং rear ইন্ডেক্সে ডাটা ইন্সার্ট করতে হবে।

DeQueue Operation

def deQueue(self):
    if self.isEmpty():
        raise ValueError("The Queue is empty")
    elif self.front == self.rear:
        data = self.queue[self.front]
        self.front = -1
        self.rear = -1
        return data
    else:
        data = self.queue[self.front]
        self.queue[self.front] = None
        self.front += 1
        return data

Explanation / Algorithm
→ সবার আগে চেক করতে হবে কিউ খালি কিনা ! যদি খালি হয় তাহলে এরর শো করতে হবে।
→ যদি কিউ খালি না হয় তাহলে দেখতে হবে rear এবং front এর মান সেম কিনা। যদি সেম হয় তাহলে বুঝতে হবে Queue তে শুধুমাত্র একটি ডাটা আছে। সেক্ষেত্রে সেই একটি ডাটাকে কোন ভ্যারিয়েবলে স্টোর করে rear এবং front এর মান -১ করে দিতে হবে। নাহলে নিচের স্টেপ ফলো করতে হবে
→ যদি rear == front না হয় তাহলে বুঝতে হবে কিউতে এখনোএকধিক ডাটা আছে। সেক্ষেত্রে সবচেয়ে প্রথমে থাকা ডাটা কে কোন ভ্যারিয়েবলে স্টোর করে সেই জায়গাতে None সেট করতে হবে এবং front এর মান ১ বাড়াতে হবে।

Traversal Operation

def traverse(self):
    if self.isEmpty():
        raise ValueError("The Queue is empty")
    else:
        for i in range(self.front , self.rear + 1):
            print(self.queue[i] , end = ' ')

Explanation / Algorithm
→ আগে চেক করতে হবে কিউ খালি কিনা। যদি খালি হয় তাহলে এরর দেখাতে হবে
→ যদি খালি না হয় তাহলে queue এর front থেকে rear + 1 পর্যন্ত লুপ চালিয়ে ডাটা প্রিন্ট করতে হবে।