স্ট্যাক বেসিক ডাটা স্ট্রাকচার

ডাটা স্ট্রাকচার কি জিনিশ ?

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

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

ডাটা স্ট্রাকচার অনেক অ্যালগোরিদম কে সুন্দর ভাবে এবং আরও দক্ষ ভাবে প্রকাশ করতে সাহায্য করে।

স্ট্যাক

একটু আগে আমরা দেখলাম, মাহমুদ একটার উপর আরেকটা রেখে বই গুলো গুছাচ্ছিল । এখন মাহমুদ কে কোন বই নিতে হলে , অই বই এর উপরের সব গুলো বই কে সরাতে হবে [ যদি উপরে আরও বই থাকে ]। আবার কোন নতুন বই রাখতে হলে তাকে সব গুলো বই এর উপরে রাখতে হবে।  তাহলে মাহমুদ কে যদি জিজ্ঞাসা করা হয়, ভাই তুমি সবার শেষে কোন বইটা রাখস ? আমাকে দাও। মাহমুদ এর কোন কষ্টই হবে না বের করতে, কারন সে জানে সবার উপরে যে বই টা আসে সেইটাই সে সবার শেষে রাখসিল। হুম, বুঝা গেলো মাহমুদ কি করেছে ? যদি বুঝা যায়, তাহলে এখন আমরা আবার বই গুলো কে ডাটা ধরি, তাহলে ব্যাপার টা কি দাঁড়াচ্ছে , আমাদের কাছে এক গাদা ডাটা আছে, আমরা সে গুলো একটার উপর আরেকটা রাখতে চাই।

  • নতুন কোন ডাটা রাখতে হলে, সবার উপরে রাখতে হবে। তাতে কষ্ট কম হবে।
  • কোন ডাটা কে নিতে চাইলে, তার উপরের সব গুলো ডাটাকে কে সরাতে হবে। মানে যাকে সবার শেষে রাখা হয়েছে, তাকে সবার আগে বের করে নিতে হবে । এটাকে বলে LIFO [Last in First Out ].
  • খুব সহজেই বলতে পারবো যে কোন ডাটা টি সবার শেষে নেয়া হয়েছে।

এই ভাবে আমরা যদি ডাটা উপস্থাপন করি , তাহলে তাকে বলে স্ট্যাক।

books-stack

এখন স্ট্যাক এর দুইটি অপারেশন বা প্রক্রিয়া আছে-

১। Push

২। Pop

Push হচ্ছে আমরা যে নতুন ডাটা পেলে তা একদম উপরে রাখছি, এটাই ।

আবার Pop হচ্ছে স্ট্যাক থেকে ডাটা নিতে হলে সবার উপর থেকে নিচ্ছি এই প্রক্রিয়া টিই।

তাহলে এবার আমরা হাতে হাতে করে দেখি স্ট্যাক এ কোন অপারেশন এর জন্য কি হয়।

১। Push(1) : প্রথমে স্ট্যাক টি খালি ছিল, তাহলে স্ট্যাক এ ১ ঢুকাই।

স্ট্যাক : 1

২। Pop(): স্ট্যাক এর সব চেয়ে উপরের সংখ্যা টি বের করে ফেলতে হবে । আর কোন সংখ্যা স্ট্যাক এ নাই বলে স্ট্যাক টি আবার খালি হয়ে যাবে

স্ট্যাক:

৩। Push(2): স্ট্যাক টি এখন খালি বিধায়ে ২ স্ট্যাক এ ঢুকাই।

স্ট্যাক: 2

৪। Push(3): 3 স্ট্যাক এ ঢুকাই। তাহলে স্ট্যাক টির অবস্থা দাঁড়াচ্ছে

স্ট্যাক: 2 3

৫। Push(4): 4 স্ট্যাক এ ঢুকাই। স্ট্যাক টির বর্তমান অবস্থা –

স্ট্যাক: 2 3 4

৬। Pop(): স্ট্যাক এর সবচেয়ে উপরের সংখ্যা টি বের করে ফেলতে হবে , তাহলে বের হবে 4. স্ট্যাক টির অবস্থা দাঁড়াচ্ছে

স্ট্যাক: 2 3

৭। Pop(): আবারো স্ট্যাক এর সবচেয়ে উপরের সংখ্যা টি বের করে ফেলতে হবে , তাহলে বের হবে 3. স্ট্যাক টির অবস্থা দাঁড়াচ্ছে

স্ট্যাক: 2

৮। Push(5): 5 স্ট্যাক এ ঢুকাই।

স্ট্যাক: 2 5

৯। Push(1): এটা নিজে করে দেখো,এবং আমার সাথে উত্তর মিলাও

স্ট্যাক: 2 5 1

১০। Pop():এটা নিজে করে দেখো,এবং আমার সাথে উত্তর মিলাও

স্ট্যাক: 2 5

অ্যালগোরিদম এনালাইসিস

প্রতি Push বা Pop করতে O(1) সময়ে লাগে

স্ট্যাক এর ব্যবহার

স্ট্যাক অনেক দরকারি এবং খুবি সোজা একটি ডাটা স্ট্রাকচার। এটি ব্যবহার করে Depth First Search (Graph Algorithm) কাজ করে। স্ট্যাক দিয়ে expression evaluation(postfix-infix) করা যায় । এছাড়া Compiler বানাতে স্ট্যাক অত্যাবশ্যক একটি ডাটা স্ট্রাকচার।