স্ট্যাক - The Journey of Undo

 লিনিয়র ডেটাস্ট্রাকচারের দুনিয়ায় সবচেয়ে গুরুত্বপূর্ণ ডেটা স্ট্রাকচারদের একটা হিসেবে ধরা যেতে পারে স্ট্যাককে। একে কেউ ডাকে কনটেইনার কেউ ডাকে কালেকশন কিন্তু আমি ডাকি বিস্কুটের ডিব্বা বলে। সবার শেষে যেগ্লা ঢুকাইছি সেটাই সবার আগে বের করে খাওয়ার ফিচার দেয় এই জিনিষটা তাই। জ্বি স্ট্যাকও তেমন। এর ভেতর যে এলিমেন্টটা সবার শেষে ঢোকে সেই সবার আগে বের হয়। তাই একে LIFO স্ট্রাকচারও বলে কেউ কেউ মানে Last In Frist Out স্ট্রাকচার। 

এটা মূলত ছোটখাটো কিছু কাজে ব্যাবহার হয় যেমন টেক্সট এডিটরে আনডু করতে চাইলে সেটার কাজে লাগে।

এর মাধ্যমে কয়েকধরণের কাজ করা যায় তার মধ্যে অন্যতম তথ্য রাখা বা ডিলিট করা। তথ্য জমা রাখাকে বলে Push এবং সেই তথ্য মুছে ফেলার নাম POP 

তার আগে জেনে নেই স্ট্যাকের সবার উপরে মানে সবার শেষে যে ভদ্রলোক ঢোকে তাকে বলে টপ এলিমেন্ট। তাইলে মামা যে স্ট্যাকে কিচ্ছুই নাই তার কি টপ ইনডেক্স নাই। আছে মামা আছে। হাইপোথেটিকালি সেটাকে -1 ইনডেক্সে ধরে নেয়া হয়।

পুস করতে গেলে ছোট খাটো কিছু জিনিষ মাথায় রাখতে হবে

১. প্রথমে জেনে নিতে হবে আমার স্ট্যাকের সাইজ কত।

২. এখন টপ মামার ইনডেক্স যদি স্ট্যাকের সাইজের চেয়ে এক কম হয় তাহলে সেটায় আর তুমি তথ্য রাখতে পারবা না।[স্ট্যাক এরের মত] এটাকে বলে ওভার ফ্লো মানে উতলে গেছে।

৩. এখন দেখলাম না মামা টপ এখনো সেই পরিমাণ বড় হয় নাই যে ওভার ফ্লো ঘটাবে। তাহলে তথ্য জমা করতে কি করতে হবে। প্রথম কাজ করতে হবে যেটা হলো টপ মামাকে এক ইনডেক্স আগায় নিতে হবে। পরে কি করবা? এবার টপ মামার এই ইনডেক্সে তোমার এলিমেন্ট এসাইন করবা।

এখন ধরো তুমি পপ করবা

১. আবার পুরান হিসাব। স্ট্যাক খালি কিনা চেক করি চলো। খালি হইলে এটাকে কয় আন্ডারফ্লো। 

২. দেখলাম না স্ট্যাক খালি না ভেতরে মাল আছে। তাইলে কি করা যায়। আগে স্ট্যাককে মাইর হবে বেশি বাড়ছে। এক কমাও ওর ইনডেক্স। সাথে সাথেই ওর ভেতরে থাকা ডাটাও ডিলেট হয়ে যাবে অটো।

কি বুঝলা সোজা না ব্যাপারটা।

টাইম কমপ্লেক্সিসিটি গুলোতেও চোখ বোলানো যাক

১. ট্রাভার্সিং - O(1)

২. পুস - O(1)

৩. পপ - O(1)

৪. সার্চিং - O(n)

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

এই বিষয়ে যে কোন প্রশ্নে মেইল করতে পারেন joybaust50@gmail com এ।