বৃত্তাকার সারি
বৃত্তাকার সারি হল একটি রৈখিক ডেটা স্ট্রাকচার যেখানে FIFO (ফার্স্ট ইন ফার্স্ট আউট) নীতির উপর ভিত্তি করে ক্রিয়াকলাপগুলি সঞ্চালিত হয় এবং একটি বৃত্ত তৈরি করার জন্য শেষ অবস্থানটি প্রথম অবস্থানের সাথে সংযুক্ত থাকে। একে "রিং বাফার"ও বলা হয়।
বৃত্তাকার সারির একটি সুবিধা হল যে আমরা সারির সামনের স্থানগুলি ব্যবহার করতে পারি। একটি সাধারণ সারিতে, একবার সারিটি পূর্ণ হয়ে গেলে, সারির সামনে একটি স্থান থাকলেও আমরা পরবর্তী উপাদানটি সন্নিবেশ করতে পারি না। কিন্তু বৃত্তাকার সারি ব্যবহার করে, আমরা নতুন মান সংরক্ষণ করতে স্থান ব্যবহার করতে পারি।
সমস্যা
আমাদের জাভাস্ক্রিপ্টে বৃত্তাকার সারির বাস্তবায়ন ডিজাইন করতে হবে যা নিম্নলিখিত ক্রিয়াকলাপগুলিকে সমর্থন করতে পারে -
-
MyCircularQueue(k) − কন্সট্রাক্টর, সারির আকার k হতে সেট করুন।
-
Front() - সারি থেকে সামনের আইটেমটি পান। সারি খালি থাকলে, -1 ফেরত দিন।
-
রিয়ার() - সারি থেকে শেষ আইটেমটি পান। সারি খালি থাকলে, -1 ফেরত দিন।
-
enQueue(value) - বৃত্তাকার সারিতে একটি উপাদান সন্নিবেশ করান। অপারেশন সফল হলে সত্যে ফিরে আসুন।
-
deQueue() - বৃত্তাকার সারি থেকে একটি উপাদান মুছুন। অপারেশন সফল হলে সত্যে ফিরে আসুন।
-
isEmpty() - বৃত্তাকার সারি খালি কিনা তা পরীক্ষা করে।
-
isFull() - বৃত্তাকার সারি পূর্ণ কিনা তা পরীক্ষা করে।
উদাহরণ
নিম্নলিখিত কোড -
const CircularQueue = function(k) {
this.size = k
this.queue = []
this.start1 = 0
this.end1 = 0
this.start2 = 0
this.end2 = 0
}
CircularQueue.prototype.enQueue = function(value) {
if(this.isFull()) {
return false
}
if(this.end2 <= this.size - 1) {
this.queue[this.end2++] = value
} else {
this.queue[this.end1++] = value
}
return true
}
CircularQueue.prototype.deQueue = function() {
if(this.isEmpty()) {
return false
}
if(this.queue[this.start2] !== undefined) {
this.queue[this.start2++] = undefined
} else {
this.queue[this.start1++] = undefined
}
return true
}
CircularQueue.prototype.Front = function() {
if(this.isEmpty()) {
return -1
}
return this.queue[this.start2] === undefined ? this.queue[this.start1] : this.queue[this.start2]
}
CircularQueue.prototype.Rear = function() {
if(this.isEmpty()) {
return -1
}
return this.queue[this.end1 - 1] === undefined ? this.queue[this.end2 - 1] : this.queue[this.end1 - 1]
}
CircularQueue.prototype.isEmpty = function() {
if(this.end2 - this.start2 + this.end1 - this.start1 <= 0) {
return true
}
return false
}
CircularQueue.prototype.isFull = function() {
if(this.end2 - this.start2 + this.end1 - this.start1 >= this.size) {
return true
}
return false
}
const queue = new CircularQueue(2);
console.log(queue.enQueue(1));
console.log(queue.enQueue(2));
console.log(queue.enQueue(3));
console.log(queue.Rear());
console.log(queue.isFull());
console.log(queue.deQueue());
console.log(queue.enQueue(3));
console.log(queue.Rear()); আউটপুট
true true false 2 true true true 3
