কম্পিউটার সাইন্স/এপ্লিকেশনে এ Queue হল ভীষণ গুরুত্বপূর্ণ একটি ডেটা স্ট্রাকচার। আজকে আমরা এই পোস্টে আলোচনা করব Array ব্যাবহার করে কিভাবে একটি Circular Queue তৈরি করব এবং Circular Queue এর বিভিন্ন অপারেশন।
Table of Contents
What is Queue in Data-structure
Queue হলো একটি linear ডেটা স্ট্রাকচার কারণ Queue এ এলিমেন্ট গুলি একটি নির্দিষ্ট sequence গঠন করে ।
Queue ডেটা স্ট্রাকচার সম্পর্কে আরো বিস্তারিত জানতে এই পোস্টটি দেখুন 👇।
Also Read :- Implement Queue In Python Using Array | Learn in Easy Bengali 2024
যেহেতু Queue তে এলিমেন্ট insertion অপারেশন সবসময় Queue এর শেষেই হয় এবং deletion অপারেশন সবসময় Queue র শুরুতে হয় সেই কারণে Queue ফার্স্ট-ইন-ফার্স্ট-আউট(First In First Out) বা FIFO অর্ডার ফলো করে।
Why Circular Queue is Required ?
Linear Queue তে একটা সময় যখন rear ভেরিয়েবেলটি Queue এর শেষতম ইনডেক্সে পৌছায় কিন্তু Queue টি এখনো ভর্তি(full) নয় এমন অবস্থায় নতুন এলিমেন্ট টিকে জায়গা দেওয়ার জন্য আমাদের Queue এর প্রতিটি এলিমেন্টকে শিফট করাতে হবে। তবে এই পদ্ধতিটি বড় Queue এর জন্য যথেষ্ট সময় সাপেক্ষ ঠিক সেই কারণে আমাদের Circular Queue প্রয়োজন।
নিচের ছবিটিকে ভালোভাবে দেখুন 👇
Linear Queue এর এই সমস্যাটির আমরা একটি Circular Queue এর সাহায্যে সমাধান করতে পারি। Circular Queue এর প্রধান advantage হল যখন Queue টি সম্পূর্ণ ভর্তি(full) নয় , তখন আমাদের Enqueue করার জন্য এলিমেন্টকে শিফট করার প্রয়োজন নেই। কিন্তু যখন rear ভেরিয়েবেলটি Queue এর শেষতম ইনডেক্সে (Array size – 1) পৌছায় , তখন নতুন এলিমেন্টটিকে আমাদের 0 নম্বর ইনডেক্সে Enqueue করতে হবে।
ঠিক একইভাবে , যখন front ভেরিয়েবেলটি Queue এর শেষতম ইনডেক্সে (Array size – 1) পৌছায় , তখন front ভেরিয়েবেলটি Queue এর 0 নম্বর ইনডেক্স কে পয়েন্ট করবে।
নিচের ছবিটিকে ভালোভাবে দেখুন 👇
Operation associated with Circular Queue
Circular Queue এর বেসিক অপারেশন গুলি আমরা নীচে আলোচনা করেছি।
- Enqueue – Circular queue এ একটি এলিমেন্টকে insert করা।
- Dequeue – Circular queue থেকে একটি এলিমেন্টকে delete করা।
- Peek – Circular queue এর শুরুর এলিমেন্টকে দেখানো।
- Isempty – এই মেথডটি ব্যবহৃত হয় Circular queue টি খালি কিনা চেক করার জন্য।
- Isfull – এই মেথডটি ব্যবহৃত হয় Circular queue টি ভর্তি কিনা চেক করার জন্য।
Two Important Situations On Queue
Queue Overflow
যখন আমরা কোন এলিমেন্টকে queue এ enqueue করব তখন আমাদের অবশ্যই চেক করা প্রয়োজন queue টি ভর্তি(full ) কিনা। যদি queue টি সম্পূর্ণরূপে ভর্তি হয়, তখন আমরা নতুন কোন এলিমেন্টকে queue এ enqueue করতে পারব না। এই সিচুয়েশনটিকেই বলা হয় Queue Overflow।
তবে এটি fixed সাইজ Queue এর ক্ষেত্রেই প্রযোজ্য।
Queue Underflow
যখন আমরা কোন এলিমেন্টকে queue থেকে peek বা dequeue করব তখন আমাদের অবশ্যই চেক করা প্রয়োজন queue টি খালি(empty ) কিনা। যদি queue টি সম্পূর্ণরূপে খালি(empty ) হয়, তখন আমরা কোন এলিমেন্টকে queue থেকে peek বা dequeue করতে পারব না। এই খালি(empty ) সিচুয়েশনটিকেই বলা হয় Queue Underflow।
Circular Queue representation
এখন আমরা দেখব , আমরা কিভাবে উপরের অপারেশন গুলির জন্য পাইথনে ফাংশন লিখব এবং সর্বশেষে , তৈরি করা ফাংশন গুলিকে ব্যবহার করে কিভাবে একটি ক্লাস(class) তৈরী করব।
কম্পিউটার মেমরিতে array ব্যবহার করে Circular Queue তৈরি করার জন্য , array এর প্রথম এবং সর্বশেষ পজিশন স্টোর করার জন্য আমাদের অতিরিক্ত দুটি ভ্যারিয়েবল তথা , front এবং rear এর সাহায্য নিতে হবে। তাহলে প্রথমেই আমরা myqueue নামে একটা fixed সাইজ array তৈরি করব, পাইথনের array নামক মডিউল ব্যাবহার করে এবং array টির প্রত্যেকটি index এ ভ্যালু হিসাবে 0 দিয়ে ইনিশিয়ালাইজ করে রাখবো এবং সাথে আরও উপরের দুটি ভেরিয়েবল কে -1 দিয়ে ইনিশিয়ালাইজ করে রাখব।
Why we require two variable name front and rear ? ( কেনো আমদের front এবং rear নামক দুটি ভ্যারিয়েবলের প্রয়োজন?)
front এবং rear দুটি মূলত integer ভ্যারিয়েবল , যার মধ্যে আমরা array পজিশন store করে রাখি Queue এ অপারেশনের জন্য।
- front ভেরিয়েবল কে কাজে লাগিয়ে আমরা dequeue অপারেশন করি।
- rear ভেরিয়েবল কে কাজে লাগিয়ে আমরা enqueue অপারেশন করি।
front এবং rear এর ভ্যালু -1 নির্দেশ করে Queue টি খালি (empty ) এবং front এর ভ্যালু 0 এবং rear এর ভ্যালু ( array সাইজ – 1 ) queue টি পরিপূর্ণ(full) ।
Operations on a Circular Queue
তবে class এর মধ্যে আমাদের “init_()” মেথডেই উপরের সমস্ত কাজগুলি করতে হবে।
Enqueue ( ) operation
Circular Queue এ এলিমেন্ট insert করতে Enqueue ( ) মেথড ব্যাবহার করা হয়।
যেহেতু আমরা একটি এলিমেন্ট insert করব সেই জন্য ফাংশনে আমরা data নামক একটি প্যারামিটার নেব।
Step – 1
চেক করব , যদি(if condition i) rear এর ভ্যালুটি -1 হয় , অর্থাৎ Queue টি খালি(Empty) , তাই আমরা front এবং rare দুটি ভেরিয়েবল এ 0 সেট করব।
Step – 2
চেক করব যদি (if condition ii) rear এর ভ্যালুটি ( array সাইজ – 1 ) হয় তাহলে rear কে 0 সেট করব।
অন্যথায়
অন্যথায়(else condition ) rear এর ভ্যালু এক বাড়াবো ( +1 ) ।
Step – 3
Array এর rear পজিশনে data কে রাখবো।
def enqueue(self,data):
if self.rear==-1:
self.rear=self.front=0
elif self.rear==self.size-1:
self.rear=0
else:
self.rear+=1
self.arr[self.rear]=dataDequeue ( ) operation
Circular Queue থেকে এলিমেন্ট delete করতে Dequeue ( ) মেথড ব্যাবহার করা হয়।
Step – 1
প্রথমে array এর front পজিশনে যে ভ্যালুটি আছে সেটিকে আমরা temp নামক একটি ভ্যারিয়েবল এ স্টোর করব।
Step – 2
যদি(if condition ) front এবং rear পজিশনের ভ্যালু সমান হয় অর্থাৎ queue তে একটাই মাত্র এলিমেন্ট আছে তাহলে আমরা front এবং rear পজিশনের ভ্যালু -1 সেট করবো।
Step – 3
যদি(if condition ii ) front পজিশনের ভ্যালু (Array Size – 1) এর সাথে সমান হয় তাহলে আমরা front পজিশনের ভ্যালু 0 সেট করবো।
Step – 4
অন্যথায়(else condition ) front এর ভ্যালু এক বাড়াবো ( +1 ) ।
Step – 5
temp এর ভ্যালুটিকে return করব।
def dequeue(self):
temp_data=self.arr[self.front]
if self.front==self.rear:
self.front=self.rear=-1
elif self.front==self.size-1:
self.front=0
else:
self.front+=1
return temp_dataPeek ( ) operation
একটি Queue এর প্রথম এলিমেন্টকে দেখানোর জন্যে peek ( ) মেথড ব্যাবহার করা হয়।return স্টেটমেন্ট ব্যবহার করে, array এর front পজিশনের ভ্যালুটিকে return করব।
def peek(self):
return self.arr[self.front]isempty ( )
এই মেথডটি ব্যবহৃত হয় Circular Queue টি খালি(Empty) কিনা চেক করার জন্য।
যদি front এর ভ্যালু – 1 হয় তাহলে queue টি খালি (empty) ।
def isempty(self):
return self.front==-1isfull ( )
এই মেথডটি ব্যবহৃত হয় Circular Queue টি ভর্তি কিনা চেক করার জন্য।
যদি front এর ভ্যালু 0 এবং rear এর ভ্যালু ( Array Size – 1 ) হয় অথবা front = rear + 1 হয় তাহলে queue টি ভর্তি(full) ।
def isfull(self):
return (self.front==0 and self.rear==self.size-1) or (self.front==self.rear+1)Circular Queue Representation Using Array
এখন আমরা দেখব কিভাবে circular_queue নামের একটি class তৈরি করে ওপরের ফাংশন গুলির কিছু syntax পরিবর্তন করে আমরা একটি Circular Queue তৈরি করতে পারি।
প্রথমে আমরা ,আমাদের কম্পিউটারে data structure বা অন্য যে কোনো নামে একটা ফোল্ডার তৈরি করব। সেই ফোল্ডারে circularqueue.py নামে একটা পাইথন ফাইল তৈরি করব। এরপর সেখানে আমরা নিম্নলিখিত কোডটিকে paste করব।
Write a program for a circular queue in Python.
# circular queue
import array as arr
class circular_queue:
def __init__(self,size): # here __init__() is a special method called constructor.
self.arr=arr.array('i',[0]*size)
self.size=size
self.front=self.rear=-1
# here, self is a keyword refers to the instance of the class
def enqueue(self,data): # enqueue method
if self.rear==-1:
self.rear=self.front=0
elif self.rear==self.size-1:
self.rear=0
else:
self.rear+=1
self.arr[self.rear]=data
def dequeue(self): # dequeue method
temp_data=self.arr[self.front]
if self.front==self.rear:
self.front=self.rear=-1
elif self.front==self.size-1:
self.front=0
else:
self.front+=1
return temp_data
def isempty(self): # isempty method
return self.front==-1 and self.rear==-1
def isfull(self): # isfull method
return (self.front==0 and self.rear==self.size-1) or (self.front==self.rear+1)
def peek(self): # peek method
return self.arr[self.front]
def display(self): # display method
if self.rear >= self.front:
for i in range(self.front,self.rear+1):
print(f" | {self.arr[i]} |",end=" ")
else:
for i in range(self.front,self.size):
print(f" | {self.arr[i]} |",end=" ")
for i in range(0,self.rear+1):
print(f" | {self.arr[i]} |",end=" ")
এখানে আমরা display নামক একটি অতিরিক্ত মেথড ব্যবহার করেছি যেটির কাজ হল Queue এর এলিমেন্ট গুলিকে ডিসপ্লে করানো।
এবার আমরা আমাদের বানানো queue.py মডিউলটিকে আমাদের অন্য আরেকটি ফাইলে import করব। এবং একটি menu-driven প্রোগ্রাম লিখে Queue এর ব্যবহার দেখব।
from circular_queue import circular_queue
size=int(input("enter the queue size: "))
qu=circular_queue(size)
while(True):
print("\n---------------\n1.for enqueue")
print("2.for dequeue")
print("3.for peek")
print("4.for display")
print("5.for exit")
choice=int(input("enter the choice: "))
match(choice):
case 1:
if qu.isfull():
print("queue overflow")
else:
data=int(input("enter the data: "))
qu.enqueue(data)
case 2:
if qu.isempty():
print("queue underflow")
else:
print(f"dequeue element : {qu.dequeue()}")
case 3:
if qu.isempty():
print("queue underflow")
else:
print(f"peek element : {qu.peek()}")
case 4:
if qu.isempty():
print("queue underflow")
else:
qu.display()
case 5:
exit(0)
case _:
print("plaese...enter the value between 1 to 5.")
Output
enter the queue size: 3
---------------
1.for enqueue
2.for dequeue
3.for peek
4.for display
5.for exit
enter the choice: 1
enter the data: 5
---------------
1.for enqueue
2.for dequeue
3.for peek
4.for display
5.for exit
enter the choice: 1
enter the data: 10
---------------
1.for enqueue
2.for dequeue
3.for peek
4.for display
5.for exit
enter the choice: 1
enter the data: 15
---------------
1.for enqueue
2.for dequeue
3.for peek
4.for display
5.for exit
enter the choice: 4
| 5 | | 10 | | 15 |
---------------
1.for enqueue
2.for dequeue
3.for peek
4.for display
5.for exit
enter the choice: 3
peek element : 5
---------------
1.for enqueue
2.for dequeue
3.for peek
4.for display
5.for exit
enter the choice: 2
dequeue element : 5
---------------
1.for enqueue
2.for dequeue
3.for peek
4.for display
5.for exit
enter the choice: 2
dequeue element : 10
---------------
1.for enqueue
2.for dequeue
3.for peek
4.for display
5.for exit
enter the choice: 4
| 15 |
---------------
1.for enqueue
2.for dequeue
3.for peek
4.for display
5.for exit
enter the choice: 2
dequeue element : 15
---------------
1.for enqueue
2.for dequeue
3.for peek
4.for display
5.for exit
enter the choice: 4
queue underflow
---------------
1.for enqueue
2.for dequeue
3.for peek
4.for display
5.for exit
enter the choice: 3
queue underflow
---------------
1.for enqueue
2.for dequeue
3.for peek
4.for display
5.for exit
enter the choice: 5