স্ট্যাক - পর্ব ১ (থিয়ুরী)

আজকে আমরা আরেকটি লিনিয়ার ডাটা স্ট্রাকচার স্ট্যাক নিয়ে আলোচনা করবো। স্ট্যাক দেখতে অ্যারের মতোই কারন স্ট্যাকে ডাটা গুলো লিনিয়ারিটি মেইনটেইন করে থাকে। স্ট্যাকের ইনপুট প্রসেস অ্যারের মতোই ; ইনডেক্সিং করে থাকে। কিন্তু স্ট্যাকের মূল বৈশিষ্ট্য হলো স্ট্যাক LIFO ধর্ম মেনে চলে। LIFO-> Last In Fast Out. অর্থাৎ যে ডাটাটি স্ট্যাকে সবার শেষে আসবে তার উপর প্রথমে অপারেশন চালানো হবে।

Stack

  

চিত্রে দেখা যাচ্ছে একটি ৫ সাইজের( Stack[5] ) স্ট্যাক আছে। যার ইনডেক্সিং শুরু হয়েছে শূন্য থেকে এবং শেষ হয়েছে N-1 এ । এছাড়াও স্ট্যাকটাই ৪টা ডাটা আছে ৷ সবচেয়ে উপরের ডাটা বা শেষ ডাটাটিকে পয়েন্ট করে থাকে Top Pointer । স্ট্যাক লিস্টের বর্তমানে কি পরিমান ডাটা আছে তা বুঝার জন্যে এই পয়েন্টার ব্যবহার করা হয়। এর মধ্যে চলুন স্ট্যাকের কিছু টার্মিনোলজির সাথে পরিচিত হয়ে আসি। 

১.  PUSH: 

স্ট্যাকে কোনো ডাটা ইনপুট করাকে PUSH বলে। সাধারন অ্যারের ইনপুটের নিয়ম অনুসারে স্ট্যাকে পুস করতে হয়৷ 

২. POP:

স্ট্যাক থেকে কোনো ডাটা ডিলিট করাকে POP বলা হয়৷ সাধারনত স্ট্যাকে যে ডাটাটি সবার শেষে আসে সেটাকেই শুধুমাত্র POP বা ডিলিট করা হয়। অর্থাৎ শেষ ইনপুট হওয়া ডাটাটির উপর অপারেশন চালাতে হয়।

চিত্রঃ PUSH, POP

৩. Top Pointer:

Top পয়েন্টার এখানে কাউন্টের কাজ করে। স্ট্যাক এর মেমোরিতে কতটি ডাটা পুস (PUSH) হলো সেই হিসাব রাখে TOP। কোনো ডাটা পুস হলেই আমরা সাথে সাথে Top র মান এক বাড়িয়ে দিবো।

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

এছাড়াও Top দিয়ে আমরা ওভারফ্লো এবং আন্ডারফ্লো চেক করতে পারি। (নিচে ওভারফ্লো এবং আন্ডারফ্লো টপিকগুলো আলোচনা করেছি) 

৪. Stack Overflow:

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

আলোচনার সুবিধার্থে ধরি আমরা স্ট্যাটিক ভাবে স্ট্যাকে ৫০ টি ডাটা রাখতে পারবো। 

এখন স্ট্যাকে ডাটা পুস করার আগে সব সময় আমরা প্রতিবার চেক করবো যে Top এর ভ্যালু ৫০ হয়ে গিয়েছে কিনা৷ যদি ৫০ হয়ে যায় তখন আমরা  show করাই দিবো Stackoverflow হয়ে যাচ্ছে৷ অর্থাৎ আর ডাটা পুস করা সম্ভব না ৷ 

যদি আমরা ডায়নামিক মেমোরি এলোকেশন করি সেক্ষেত্রে Stackoverflow ঘটার সম্ভবনা নাই৷ কারন এটা নির্ভর করবে র‍্যামের উপর। আর বর্তমানের র‍্যামের At a time huge dataset নিয়ে কাজ করতে পারে। 

৫. Stack Underflow:

স্ট্যাকে যখন আমরা ডাটা POP করতে যাবো তখন আমাদের প্রথমে চেক করতে হবে স্ট্যাকে ইতিমধ্যে কোনো ডাটা আছে কিনা। যদি ডাটা না থাকে তাহলে আমরা ডিলিট করতে পারবো না বা POP অপারেশন চালাতে পারবো না এবং সাথে সাথে শো করে দিবো স্ট্যাক আন্ডারফ্লো। তাহলে বলুন তো কম্পিউটার কে কিভাবে বুঝবে স্ট্যাকে ডাটা শেষ হয়ে গেছে কিনা? ( ১ মিনিট ভাবুন; কারন উপরে এটা বলে এসেছি )

.

.

.

.

.

সোজা হিসাব। TOP নাল কিনা চেক করবো। অর্থাৎ TOP = -1 কিনা। যদি TOP র ভ্যালু -1 র বেশি হয় তাহলে POP করা যাবে। অর্থাৎ আন্ডারফ্লো হওয়ার মতো পরিস্থিতি এখনো তৈরী হয়নি। 

আজকে এই পর্যন্ত রাখছি। পরবর্তী পর্বে এর কোডিং ইমপ্লিমেন্টেশন নিয়ে আলোচনা করবো। ধন্যবাদ।