Reading Time: 2 minutes

ধর তোমার প্রাইমারি স্কুলের টিচার ক্লাসওয়ার্ক চেক করছেন উনার টেবিলে বসে বসে। তার কাছে এখন অনেক গুলো খাতা আছে-একটার উপর আরেকটা সাজানো। এখন তিনি খাতা কাটা শুরু করলে কোনটি থেকে শুরু করবেন? অবশ্যই সবার উপরে যেটা আছে সেটা থেকে।

এখন কেউ যদি তার কাছে আরেকটি খাতা নিয়ে যায়, তাহলে সেটি তিনি কোথায় রাখবেন? সবগুলো খাতার উপর।

এই পুরো ব্যাপারটাকেই সিমুলেট করে স্ট্যাক ডাটা স্ট্রাকচার দিয়ে। স্ট্যাকের মূল ধারণা হল, যখনই নতুন কোনো ডাটা দেওয়া হবে, সেটি স্ট্যাকে সবার উপরে গিয়ে জমা হবে। আবার স্ট্যাকে প্রসেসিং-ও চলবে সবার উপরের ডাটাটা  দিয়ে। অর্থাৎ, স্ট্যাকে সবার শেষে যেটা আসছে, তার কাজ হচ্ছে সবার আগে। এটাকে বলে “Last In First Out.” আহা আমাদের লাইনে দাঁড়ানোর সময় ব্যাপারটা এমন হলে কত ভাল হত!

 

আমাদের স্ট্যাক ডাটা স্ট্রাকচার নিয়ে অনেক কাজই করতে হয়। এ ডাটা স্ট্রাকচারে মূলত নিচের অপারেশনগুলো রাখতে হয়ঃ

  • push() – স্ট্যাকে একটি নতুন উপাদান যোগ করা
  • pop() – স্ট্যাক থেকে একটি উপাদান সরিয়ে দেওয়া
  • top() – স্ট্যাকের সবার উপরের উপাদানটা রিটার্ন করা
  • isEmpty() – স্ট্যাকটা খালি কি না চেক করা
  • isFull() – স্ট্যাকটা পরিপুর্ণ কি না চেক করা
  • size() – স্ট্যাকে উপাদান সংখ্যা রিটার্ন করা

আমরা প্রথমে অ্যারে ব্যবহার করে স্ট্যাক তৈরি করবো, কারণ এটা তুলনামূলকভাবে সহজ! এজন্য আমরা প্রথমে একটি অ্যারে ডিক্লেয়ার করে ফেলি।

 

এটা আমাদের কোডের কাঠামো।

  • menu() ফাংশনটির কাজ একবার পড়লেই বুঝতে পারার কথা। তবে এটা নিয়ে আপাতত বেশী মাথা ঘামানোর দরকার নেই!
  • count নামের একটা ভ্যারিয়েবল আছে। এই ভ্যারিয়েবলে স্ট্যাকে কতটি উপাদান আছে, সেটি সেভ করা থাকবে।
  • আর display() নামে একটি ফাংশন আমি রেখেছি। এটা রাখা হয়েছে প্রতিবার push, pop ইত্যাদি করার পর সব ঠিক থাকে নাকি সেটা চেক করার সুবিধার জন্য। তাহলে এই display() ফাংশন দিয়েই শুরু করা যাক।

 

display()

এই ফাংশনের কাজ হবে স্ট্যাকের শুরু থেকে শেষ পর্যন্ত সব উপাদান প্রিন্ট করা। কাজটা খুবই সহজ। একটা লুপ চালিয়ে দিলেই তো হয়!

isEmpty()

এই ফাংশনটি 1 রিটার্ন করবে, যদি স্ট্যাকে কিছু না থাকে। অন্যান্য ক্ষেত্রে এটি রিটার্ন করবে 0।

isFull()

এই ফাংশন 1 রিটার্ন করবে, যদি স্ট্যাকটি পরিপূর্ণ থাকে। অন্যান্য ক্ষেত্রে এটি রিটার্ন করবে 0। যেহেতু আমরা ১০০০০০ সংখ্যক উপাদানের অ্যারে ডিক্লেয়ার করেছিলাম, তাহলে এত সংখ্যক উপাদান থাকলেই আমাদের 1 রিটার্ন করতে হবে!

top()

এই ফাংশনটি স্ট্যাকের সবার উপরের উপাদানটি রিটার্ন করবে। সবার উপরের উপাদান বললে কনফিউশন তৈরি হতে পারে, এটা মানে হল অ্যারের শেষ উপাদানটি। কারণ আগেই বলেছি স্ট্যাক মানে হল লাস্ট ইন, ফার্স্ট আউট। অর্থাৎ, যে সবার পরে এসেছে, সে বের হবে সবার আগে!

push()

খুবই সহজ কাজ, আমরা জানি স্ট্যাকে নতুন উপাদান এসে যুক্ত হয় সবার শেষে। তাহলে পুশ করার জন্য আমরা অ্যারের শেষে একটা নতুন উপাদান রাখবো। এরপর count-এর মান বাড়িয়ে দিব! প্যারামিটার হিসেবে আমাদের ওই নতুন উপাদানটা নিতে হবে।

pop()

এটা আরও সহজ। যেহেতু শেষ উপাদানটাই সরাতে হবে, সেহেতু count-এর মান এক কমিয়ে দিলেই হয়ে যায়। :p তবে খেয়াল রাখতে হবে, সেটা যেন আগে থেকে empty stack না হয়। এছাড়াও যে সংখ্যাটা pop  করা হচ্ছে, সেটা রিটার্ন করা যেতে পারে (পরে অন্য কোনো এক ক্ষেত্রে এটা কাজে লাগতে পারে)।

size()

রিটার্ন করতে হবে count ভ্যারিয়েবলের মান। এ আর এমন কী? :p

আমার পুরো কোড আছে এই লিংকে

এখন প্রশ্ন উঠতেই পারে, এত সহজ কেন এটা। প্রশ্ন উঠাটাই স্বাভাবিক! 😛 এখানে আমি কিছু বাজে কাজ করেছি, তা হল গ্লোবাল অ্যারে নিয়ে কাজ করেছি। তোমার কাজ হবে, অ্যারেটা লোকালভাবে ডিক্লেয়ার করে ফাংশনগুলোতে অ্যারের অ্যাড্রেস প্যারামিটার হিসেবে পাঠিয়ে কাজগুলো করা। একজন প্রোগ্রামার সবসময় চেষ্টা করে গ্লোবাল ভ্যারিয়েবলের সংখ্যা যথাসম্ভব কম রাখতে। 🙂

অ্যারে দিয়ে স্ট্যাক ইমপ্লিমেন্ট করা খুব সহজ হলেও এতে আসলে খুব বেশী লাভ নেই। কারণ এখানে মেমরি লিমিটেড হয়ে যায়। আমাদের কাজটা মূলত করতে হবে লিংকড লিস্ট দিয়ে। এটি নিয়েই হবে আমাদের পরের পর্ব। 😀

Muntasir Wahed

Muntasir Wahed

System Administrator at স্বশিক্ষা.com
Jack of all trades, master of none.
Muntasir Wahed
Muntasir Wahed