Saturday 29 January 2022

Stack data structure in javascript

 

baburjhuli

হে সুন্দর মানুষজন আসসালামু-আলাইকুম সবাইকে,

কম্পিউটার সাইন্সে কমন এবং বহুল ব্যবহৃত ডাটা-স্ট্রাকচার গুলোর মাঝে Stack একটি । আমরা আজকে এই ডাটা-স্ট্রাকচার সমন্ধে শিখতে যাচ্ছি, Stack কি তা জানার আগে একটু বোঝার চেষ্টা করি যে লিনিয়ার(Linear) ডাটা-স্ট্রাকচার কি ?

- লিনিয়ার(Linear) ডাটা-স্ট্রাকচার কি ?

যেসব ডাটা-স্ট্রাকচারে ডাটা গুলো একটি নির্দিষ্ট সিকুয়েন্সিয়াল(sequential) অর্ডারে(order) থাকে অর্থাৎ ডাটা সমূহ নির্দিষ্ট ভাবে সাজানো গোছানো অবস্থায় রাখা হয় । যেখানে ডাটা সমূহ একটি আরেকটির সাথে কানেক্টেড থাকে এবং খুব দ্রুত বিভিন্ন অপারেশনসমূহ সম্পন্ন করা হয় যেমন - ট্রাভারসিং(Traversing), সার্চিং(Searching) , মারজিং(Merging) ইত্যাদি তাদেরকেই লিনিয়ার(Linear) ডাটা-স্ট্রাকচার বলা হয়।

- Stack কি ?

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

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

অনেক স্বপ্ন ছিলো আপনার মামার মেয়েকে বিয়ে করবেন কিন্তু আজ সেই মেয়ের বিয়ে। আমি খুবই দুঃখিত যে বরটা আপনাকে বানাতে পারলাম নাহ । তবে আপনি সেই বিয়েতে একজন ওয়ার্কার যে কিনা মেহমানদের মাঝে থালা(Plate) সার্ভ করার দায়িত্ব পালন করবেন ।

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

এইখানে একটা জিনিস খেয়াল করেছেন ? এই যে আপনি বেসিন থেকে থালা একটি একটি করে হাতে নিচ্ছেন এবং তা আবার একটি একটি করে মেহমানদের মাঝে সার্ভ করতেছেন ।

ধরি যে, এইবার আপনি ৮টি থালা বেসিন থেকে হাতে নিয়েছেন । যখন ৮টি থালার ১ম টি হাতে নিয়েছেন তখন আপনার হাতে থালা একটি । তারপর যখন ২ নাম্বার থালা হাতে নিলেন তখন আপনার হাতে থালা দুইটি এবং প্রথম যে থালাটা হাতে নিয়েছেন সেইটা কিন্তু এখন ২য় থালার নিচে। এভাবে পর্যায়ক্রমে আপনি ৮ টি থালা হাতে নিয়েছেন ।

তাহলে সবশেষে যে থালাটা হাতে নিলেন অর্থাৎ ৮ নাম্বার থালা সেইটা কিন্তু এখন সবার ওপরে । এবং প্রথমে যে থালাটা নিয়েছিলেন সেইটা কিন্তু এখন সবার শেষে । তাই নাহ ?


 

এখন আপনি ৮টি থালা মেহমানদের দিতে গেলেন এবং উপরের থালাটা একজনকে দিলেন । আপনি কিন্তু উপরের থালাটা অর্থাৎ ৮ নাম্বার থালাটা একজনকে দিয়ে দিলেন। তার মানে কি ? আপনি সবশেষে যে থালাটা আপনার হাতে নিয়েছিলেন সেই থালাটাই আপনি সর্বপ্রথম একজনকে দিয়ে দিলেন। এইভাবে পর্যায়ক্রমে আপনি সব থালায় মেহমানদের দিয়ে দিলেন ।

তাহলে সারমর্ম এই যে, বেসিন থেকে সর্বশেষে যে থালাটা আপনি হাতে নিয়েছিলেন তা সর্বপ্রথম হাত থেকে সরিয়ে ফেললেন । এবং সর্বপ্রথম যে থালাটা হাতে নিয়েছিলেন তা সর্বশেষে হাত থেকে সরিয়ে ফেললেন।

এখানেও কিন্তু LIFO প্যাঁরাডাইম(paradigm) মেনে চললো অর্থাৎ - Last In First Out , শেষে যে থালাটা হাতে ইন করলেন প্রথেমেই সেইটাকে আউট করে দিলেন । আশা করি এখন আপনি Stack সম্পর্কে Theoretical একটা ধারণা পেলেন।

আপনার মনের কোথাও যদি সুর-সুরি দিয়ে উঠে যে, Stack জাভাস্ক্রিপ্টে বিল্ট-ইন ডাটা-স্ট্রাকচার কি না ? তাহলে উত্তর হবে - নাহ । এটি অ্যারে, অব্জেক্ট বা অন্য ডাটা-স্ট্রাকচারের মতো বিল্ট-ইন নাহ ।

যেহেতু আমরা মোটামোটি বুঝি যে, Stack ডাটা-স্ট্রাকচার কি তাহলে চলুন এখন আমরা খুব সহজেই এইটা কে ইমপ্লিমেন্ট(implement) অর্থাৎ তৈরি করে ফেলি ।

- Stack  ডাটা-স্ট্রাকচার ইমপ্লিমেন্ট(implement) করার আগে -

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

১। push - stack এ আইটেম সংযোজন ।

২। pop - stack থেকে আইটেম বিয়োজন ।

এইখানে মেথডস নেইম যে push এবং pop ই হবে সেরকম বাধা-ধরা কোনো নিয়ম নেই । আপনি চাইলে add , remove বা আপনার সুবিধা-মতো যেকোনো নেইম দিতে পারেন ।

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

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

1। push - stack এ আইটেম সংযোজন ।

2। pop - stack থেকে আইটেম বিয়োজন ।

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

4। isEmpty - stack খালি কি নাহ তা জানতে।

- Stack  ইমপ্লিমেন্ট(implement) -

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

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

class Stack{
    // code here
}
 

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

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

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

- push method -

 push(element) {
    this.stack.push(element)
  }

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

- pop method -

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

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

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

- size method -

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

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

- isEmty method -

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

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

- Final Stack -

class Stack {
  constructor() {
    this.stack = [];
  }

  // push item to stack
  push(item) {
    this.stack.push(item);
  }

  // remove last item
  pop() {
    if (this.stack.length) {
      return this.stack.pop();
    } else {
      return "(pop failed), No item in stack!";
    }
  }

  // get stack length
  size() {
    return this.stack.length;
  }

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

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

- Create a Stack -

const stack = new Stack();

- Add Item To Stack -

stack.push('torikus');
stack.push('fahim');
stack.push('afifa');

// ['torikus', 'fahim', 'afifa']

stack এ সবশেষে afifa কে সংযোজন করা হয়েছে এখন যদি বিয়োজন করি তাহলে -

- Remove Last Item To Stack -

console.log(stack.pop()); // 'afifa'
// [ 'torikus', 'fahim' ]

যেহেতু stack এ সবশেষে afifa কে সংযোজন করা হয়েছে তাই pop() করার পর afifa কেই প্রথম বিয়োজন করে ফেলছে ।

- Length In Stack -

console.log(stack.size()); // 2

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

- Check If Stack Is Empty -

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

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

আমাদের stack ঠিক-ঠাক মতো কাজ করতেছে। আশা করি আপনি পুরো আর্টিকেল বুঝতে পেরেছেন ।

- শেষের কথা -

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

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

 

Share:

1 comment: