জাভাস্ক্রিপ্টে সার্কুলার কিউ রিং বাফার ইমপ্লিমেন্টেশন

সার্কুলার কিউ

সার্কুলার কিউ একটি লিনিয়ার ডেটা স্ট্রাকচার যেখানে অপারেশনগুলো FIFO (First In First Out) নীতিতে করা হয় এবং শেষ পজিশন প্রথম পজিশনের সাথে সংযুক্ত থাকে একটি বৃত্ত বানাতে। এটিকে "Ring Buffer" ও বলা হয়।

সার্কুলার কিউর একটি সুবিধা হল আমরা কিউর সামনের খালি জায়গাগুলো ব্যবহার করতে পারি। একটি সাধারণ কিউতে, একবার কিউ ফুল হলে আমরা পরবর্তী উপাদান যোগ করতে পারি না যদি সামনে জায়গা থাকে। কিন্তু সার্কুলার কিউ ব্যবহার করে আমরা সেসব জায়গায় নতুন মান সংরক্ষণ করতে পারি।

সমস্যা

আমাদের জাভাস্ক্রিপ্টে সার্কুলার কিউর আমাদের নিজস্ব ইমপ্লিমেন্টেশন ডিজাইন করতে হবে যা নিচের অপারেশনগুলো সাপোর্ট করবে –

• MyCircularQueue(k) – কনস্ট্রাক্টর, কিউর সাইজ k সেট করবে।
• Front() – কিউর ফ্রন্ট আইটেম পাবে। যদি কিউ খালি হয়, -1 ফেরত দেবে।
• Rear() – কিউর লাস্ট আইটেম পাবে। যদি কিউ খালি হয়, -1 ফেরত দেবে।
• enQueue(value) – সার্কুলার কিউতে একটি উপাদান যোগ করবে। অপারেশন সফল হলে true ফেরত দেবে।
• deQueue() – সার্কুলার কিউ থেকে একটি উপাদান মুছে দেবে। অপারেশন সফল হলে true ফেরত দেবে।
• 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