Circular Queue Queue এর একটি ধরন। আমরা আগে General Queue নিয়ে আলোচনা করেছিলাম। সেখানে দেখেছি Queue তে rear থেকে data / element / item insert হয় এবং front থেকে data / element / item delete হয়। General Queue। Front থেকে ডাটা ডিলিট করার পর সেই জায়গায় আবার ডাটা ইন্সার্ট করা যেতো না। যার কারনে মেমরি লস হতো। সেই সমস্যা সমাধান হিসেবে এসেছে Circular Queu

Circular Queue তে rear সবসময় front এর সাথে কানেক্টেড থাকে। অর্থাৎ , rear ইন্ডেক্স যখনই ম্যাক্সিমাম ইন্ডেক্সে আসে তখন ডাটা ইন্সার্ট করার পর আবার front ইন্ডেক্স এ গিয়ে দেখে সেখানে জায়গা আছে কিনা। যদি থাকে তাহলে ডাটা ইন্সার্ট করতে পারবে পরবর্তিতে।

***কেও General Queue কিউ না বুঝে থাকলে এই আর্টিকেল পড়ার আগে General Queue এর আর্টিকেল পড়ে আসা উচিৎ

General Structure of CQueue

class CQueue:
    def __init__(self , size):
        self.queue = [None]*size
        self.front = -1
        self.rear = -1
        self.max_index= size - 1
    def isFull(self):
        return (self.front == 0 and self.rear == self.max_index) or (self.front == self.rear+1)
    def enQueue(self , data):
        pass
    def deQueue(self):
        pass
    def display():
        pass

isFull() method

→ isFull() method এর সাহায্যে জানতে পারবো CQueue ফুল কিনা। CQueue ফুল কিনা সেটা চেক করতে দুইটি কন্ডিশন চেক করতে হবে। এই দুইটির মধ্যে একটিও যদি True হয় তাহলে বুঝতে হবে জায়গা নেই।
কন্ডিশন - ১) front == 0 এবং rear == maximum index হয়

102030 (front = 0 ) index - 0	202020 index - 1	151515 index - 2	141414 index - 3	151515 index - 4	161616 index - 5	171717 (rear = 6 ) index - 6

এখানে একটি Array নেয়া হয়েছে। যেখানে Maximum Index হচ্ছে 6। দেখতে পাচ্ছি উপরে front == 0 এবং সর্বশেষ যে ইন্ডেক্সে এলিমেন্ট অ্যাড করা হয়েছে তার ইন্ডেক্স ৬। অর্থাৎ , rear == 6 এবং 6 হচ্ছে আমাদের Array এর ম্যামক্সিমাম ইন্ডেক্স। এরপর আর কোন জায়গা নেই এলিমেন্ট অ্যাড করার জন্য। সুতারাং , Array is full

কন্ডিশন - ২) front == rear + 1 হয় তাহলে বুঝতে হবে জায়গা নেই। এখন আমরা উপরের Arra থেকে প্রথম ৩ টি ইন্ডেক্স থেকে ডাটা ডিলিট করে দিই। সেক্ষেত্রে , আমাদের front হবে 4 এবং rear হবে 6 ( যেহেতু Queue তে ডাটা সামনে থেকে ডিলিট হয় সেহেতু শুধুমাত্র front পরিবর্তন হবে। rear পরিবর্তন হবে না। )

index = 0	index = 1	index = 2	index = 3	151515 (front = 4 ) index = 4	161616 index = 5	171717 (rear = 6 ) index = 6

এখন আমরা যদি কিউতে ডাটা যোগ করতে চাই তাহলে দেখতে হবে জায়গা খালি আছে কিনা। সো , যদি isFull() মেথড কল দিই তাহলে আমাদেরকে false return করবে। কারন , দুইটি কন্ডিশনের মধ্যে একটি কন্ডিশন ও ম্যাচ করেনি।
→ প্রথম কন্ডিশন (front == 0 and rear == max_index ) এটি ম্যাচ করেনি। আমাদের বর্তমান Array তে front == 4 and rear == 6 also size == 6
→ দ্বিতীয় কন্ডিশন অনুযায়ী ( front == rear + 1 ) ও ম্যাচ করেনি। কারন ,
আমাদের বর্তমান Array তে front = 4 and rear = 6
so , 4 =! 6 + 1

enQueue operation

General Queue এর enQueue operation এর মতো CQueue এর enQueue operation ও প্রায় একই। তবে একটু ভিন্নতা আছে। যেহেতু এটি সার্কুলার কিউ সেহেতু rear এর মান যখন max_index এ চলে আসবে তখন rear = 0 করে দিতে হবে এবং বাকি সবকিছুই General Queue এর মতো।

def enQueue(self , item):
    if self.isFull():
        raise ValueError("The Queue is full")
    elif self.front == -1:
        self.front = self.rear = 0
    elif self.rear == self.max_index: #Circular condition
        self.rear = 0
    else:
        self.rear += 1
    self.queue[self.rear] = item

deQueue operation

General Queue এর deQueue operation এবং Circular Queue এর deQueue operation এর মধ্যে মূল পার্থক্য হচ্ছে ডাটা ডিলিট করতে করতে যখন front == max_index হয়ে যায় তখন front কে আবার 0 তে সেট করতে হয়।

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

display / traversing operaiotn

→ প্রথমে দেখতে হবে Queue খালি কিনা। যদি খালি হয় তবে Underflow কন্ডিশন হবে
→ একটি ভ্যারিয়েবলের ( i )মধ্যে front এর মান সেট করে rear পর্যন্ত ট্রাভার্স করতে হবে (লুপ এর মাধ্যমে)। যদি i এর মান rear এর সমান হয় তবে লুপ থেকে বের হয়ে যেতে হবে। এবং যদি i == max_index হয় তবে i == 0 সেট করতে হবে আর নাহলে i এর মান ১ করে বাড়াতে হবে

def traverse(self):
    if self.front == -1:
        print("The Queue is empty")
        return
    else:
        i = self.front
        while True:
            print(self.queue[i])
            if i == self.rear:
                break
            elif i == self.max_index:
                i = 0
            else:
                i += 1