Queue data structure in javascript

 

কম্পিউটার সাইন্সে আরও একটি কমন এবং বহুল ব্যবহৃত ডাটা-স্ট্রাকচার হলো Queue । আমরা আজকে এই ডাটা-স্ট্রাকচার সমন্ধে শিখতে যাচ্ছি, তবে আশা করি যে আপনি Stack ডাটা-স্ট্রাকচার সম্পর্কে জানেন।

যদি নাহ যেনে থাকেন তাহলে এখানে পড়ুন ।

- Queue কি ?

Queue একটি লিনিয়ার(Linear) ডাটা-স্ট্রাকচার যা FIFO প্যাঁরাডাইম(paradigm) মেনে চলে । FIFO এর পূর্ণরূপ হইলো - First In First Out অর্থাৎ Queue এ কোনো একটা ভ্যালু প্রথমে সংযোজন করা হইলে তা প্রথমেই বিয়োজন হবে। এখন একটু রিয়েল লাইফ উদাহরণ দেওয়া যাক -

- রিয়েল লাইফ উদাহরণ -

গত ব্লগে আপনার মামার মেয়ের তো বিয়ে হয়ে গেলো কিন্তু সেই বিয়েতে আপনি থালা বিতরন ছাড়া আর কিছুই করতে পারলেন নাহ । কিন্তু আপনি কি হাল ছেড়ে দেওয়ার মতো মানুষ ? নাহ অবশ্যই নাহ ।

হ্যাঁ আপনি আপনার মামাতো বোন কে পান নাই তাতে কি হয়েছে পৃথিবীতে কি মেয়ের অভাব নাকি ? তাই আপনিও আপনার মামার মেয়ের মতো বিয়ে করে ফেললেন । এখন আপনার মামাতো বোন কে তো দেখাতে হবে নাকি ? তাই আপনি প্ল্যান করলেন যে, হানিমুনে যাবেন দেশের কোথাও।

এই সুবাধে আপনি আগামিকালের টিকিট আজকেই বুক করতে গেলেন কিন্তু ওমা এ কি!

টিকিট কাউন্টারে তো অনেক লোক লাইন হয়ে দাঁড়িয়ে আছে । এবং তারা সিরিয়াল মোতাবেক একজনের পর একজন টিকিট নিচ্ছে । এখন আপনার সিরিয়াল ধরেন ১৮ নম্বর। তাহলে যখন আপনার সিরিয়াল আসবে তখনই আপনি টিকিট নিতে পারবেন ।

এখন আপনি মনে মনে ভাবতেছেন যে, ইস! যদি খানিকটা আগে আসতে পারতাম তাহলে আগেই যাইতাম । আসলেই, আগে আসলে আগেই যাইতে পারতেন । কিন্তু কি আর করার ।

 

আশা করি আপনি এখানে Queue ডাটা-স্ট্রাকচারের আচরণ ধরতে পারছেন । যদি এখনও আপনার খাটাস ব্রেইনে কিছু নাহ ঢুকে থাকে তাহলে চলেন আরেকটু বোঝা-বুঝি সেরে ফেলা যাক -

উপরের ছবিটি লক্ষ করুন, সেখানে ৬ জন মানুষ এক টিকিট কাউন্টারে টিকিট নেওয়ার জন্য সারিবদ্ধভাবে দাড়িয়ে আছে। এখন সর্বপ্রথম যে, লোকটাকে দেখা যাচ্ছে উনি সবার আগে এসেছে, তাই সবার আগেই টিকিট নিয়ে চলে যাবে ।

এভাবে পর পর ৬ জন মানুষ তাদের সিরিয়াল মেইন্টেইন করে টিকিট নিয়ে সেখান থেকে চলে যাবে। তাহলে বিষয়টা দাড়ালো যে, প্রথম যে মানুষটা লাইনে ইন হইলো সেই মানুষটাই প্রথমেই টিকিট নিয়ে লাইন থেকে আউট হয়ে গেলো । তাহলে কিন্তু এখানেও FIFO প্যাঁরাডাইম(paradigm) মেনে চললো অর্থাৎ - First In First Out।

- Common operations on Queue -

যে কোনো ল্যাংগুয়েজেই হোক নাহ কেনো Queue ইমপ্লিমেন্ট(implement) করার সময় মাস্ট(must) আমাদেরকে দুইটা মেথড তৈরি করতেই হবে-

1. enqueue - Queue এ আইটেম সংযোজন ।
2. dequeue - Queue থেকে আইটেম বিয়োজন ।

এইখানে মেথডস নেইম যে enqueue এবং dequeue ই হবে সেরকম বাধা-ধরা কোনো নিয়ম নেই । আপনি চাইলে add , remove বা আপনার সুবিধা-মতো যেকোনো নেইম দিতে পারেন । তবে এই দুইটা মেথড ছাড়াও Queue এ আমাদের প্রয়োজন মতো অনেক মেথডস তৈরি করতে পারি ।

- Queue এ আমরা যে মেথডস গুলো তৈরি করতে যাচ্ছি -

1. enqueue() - Queue এ আইটেম সংযোজন ।

2. dequeue() - Queue থেকে আইটেম বিয়োজন ।

3. size() - Queue এ আইটেম কতগুলো আছে তা জানতে।

4. isEmpty() - Queue খালি কি নাহ তা জানতে।

- Implementing a queue in JavaScript -

Queue ইমপ্লিমেন্ট(implement) করতে আমি নেটিভ অ্যারে(array) এবং ক্লাস(class) কে বেছে নিবো । তবে লিঙ্কড-লিস্ট(linked-list) এবং ফাংশন(function) দিয়েও চাইলে করতে পারেন ।

- ক্লাস(class) ডিফাইন -

class Queue{
    // code here
}

- কন্সট্রাক্টর(constructor) তৈরি -

constructor(){
    this.queue = [];
}

এখানে একটি constructor ফাংশন নিয়েছি এবং this.queue নামে একটা প্রোপার্টি নিয়েছি যা মুলত একটা অ্যারেকে হোল্ড করে । এই অ্যারেই মুলত Queue এর আইটেমগুলো কে কনট্রোল করবে ।

- enqueue() method -

এই মেথডের সাহায্যে কোনো আইটেম Queue এর প্রথমে সংযোজন করা যাবে ।

enqueue(element) {
    this.queue.unshift(element)
  }

অ্যারের unshift মেথডের সাহায্য নেওয়া হয়েছে যা এলিমেন্টকে খুব সহজেই Queue এর প্রথমে যুক্ত করে দিবে ।

- dequeue() method -

  dequeue() {
    if (this.queue.length) {
      return this.queue.pop();
    } else {
      return "(dequeue failed), No item in queue!";
    }
  }

এখানে বলা হয়েছে যে যদি Queue এর লেন্থ শুন্য(0) থেকে বড় হয় তাহলে Queue থেকে শেষের এলিমেন্টকে ডিলিট করে দিবে। শেষের এলিমেন্ট সেইটাই যেইটা Queue এ প্রথমে এড করা হবে । আর বুঝতেই পারছি যে, শুন্য(0) থেকে বড় মানে Queue এ এলিমেন্ট আছে।

আর যদি Queue এ এলিমেন্ট নাহ থাকে তাহলে (dequeue failed), No item in queue! রিটার্ন করবে ।

- size method -

Queue এ কতোগুলো আইটেম আছে তা এই সাইজ(size) মেথড রিটার্ন করবে ।

size() {
    return this.queue.length;
  }

- isEmty method -

Queue খালি কি নাহ তা জানা যাবে isEmty() মেথডের এর সাহায্যে । যদি Queue এ আইটেম থাকে তাহলে false আইটেম নাহ থাকলে true রিটার্ন করবে।

isEmpty() {
  return this.queue.length === 0;
}

- Final Queue -

// implement queue
class Queue {
  constructor() {
    this.queue = [];
  }

  // add item in first position
  enqueue(element) {
    this.queue.unshift(element)
  }

  // remove last item which is the first item
  dequeue() {
    if (this.queue.length) {
      return this.queue.pop();
    } else {
      return "(dequeue failed), No item in queue!";
    }
  }

  // length of queue
  size() {
    return this.queue.length;
  }

  // check if queue is empty
  isEmpty() {
    return this.queue.length === 0;
  }

}

আপনি চাইলে Queue এ প্রয়োজন মতো আরও অনেক মেথড যুক্ত করতে পারেন । এখন আমাদের তৈরি করা Queue টেস্ট করে দেখবো যে সব কিছু ঠিকমতো কাজ করছে কি নাহ ।

- Create a Queue -

// create a queue
const queue = new Queue();

- Add Item To Queue -

queue.enqueue("shakil");
queue.enqueue("torikus");
queue.enqueue("morshed");
queue.enqueue("afifa");

// queue
[ 'afifa', 'morshed', 'torikus', 'shakil' ]

যেহেতু queue এ সর্বপ্রথমে shakil কে সংযোজন করা হয়েছে এখন যদি বিয়োজন করি তাহলে -

- Remove last item which is the first item -

console.log(queue.dequeue()); // shakil

console.log(queue);
// [ 'afifa', 'morshed', 'torikus' ]

যেহেতু queue এ সর্বপ্রথম shakil কে সংযোজন করা হয়েছে তাই dequeue() করার পর shakil কেই প্রথম বিয়োজন করে ফেলছে ।

- Length in Queue -

console.log(queue.size());
// 3

আমরা দেখতে পাইতেছি যে, queue এ তিনটি আইটেম আছে তাই আউটপুট হিসেবে 3 কেই রিটার্ন করা হয়েছে।

- Check if queue is empty -

console.log(queue.isEmty());
// false

যেহেতু, queue এ আইটেম আছে তাই আউটপুট হিসেবে false কেই রিটার্ন করা হয়েছে যদি আইটেম নাহ থাকতো তাহলে true রিটার্ন করতো। আমাদের queue ঠিক-ঠাক মতো কাজ করতেছে।

- শেষের কথা -

কোনো একটি বিষয় একবারে নাহ বুঝলে বার বার চেষ্টা করতে হয় । আপনারা যদি কোথাও বুঝতে নাহ পারেন তাহলে আরেকবার দেখতে পারেন । এতে অনেক কিছুই পরিস্কার হয়ে যাবে।

যদি এই আর্টিকেলে কোনো প্রকার ভূল পেয়ে থাকেন তাহলে আমাকে জানাতে ভূলবেন নাহ প্লিজ । আমরা শিখতে চাই সেটা ভূল থেকে হলেও ।

ধন্যবাদ।