স্ট্যাক (Stack)

বিয়ের দাওয়াত বা বুফেতে সাজিয়ে রাখা প্লেটের স্তূপের কথা চিন্তা করুন। আপনি একটা প্লেট রাখলেন, তার ওপর একটা, তার ওপর আরেকটা। যখন কারো প্লেট দরকার পড়বে, সে কিন্তু সবার ওপরের প্লেটটাই তুলবে — একদম নিচেরটা ধরে টান দেবে না।

এটাই হলো স্ট্যাক (Stack)। এর একটাই সুপার সিম্পল নিয়ম: লাস্ট ইন, ফার্স্ট আউট (Last In, First Out) — সংক্ষেপে যাকে বলা হয় LIFO।

পুশ (Push) এবং পপ (Pop)

স্ট্যাক নিয়ে কাজ মূলত দুটোই:

• পুশ (Push) — স্তূপের একদম ওপরে একটা নতুন জিনিস রাখা
• পপ (Pop) — স্তূপের একদম ওপরের জিনিসটা তুলে নেওয়া

আপনি চাইলে পিক (Peek)-ও করতে পারেন — মানে না তুলেই জাস্ট উঁকি দিয়ে দেখা একদম ওপরে কী আছে।

কোথায় কোথায় স্ট্যাক থাকে?

আমাদের চারপাশে সব জায়গায়! আপনার ব্রাউজারের 'Back' বাটন স্ট্যাক ব্যবহার করে। যখন আপনি কম্পিউটারে কোনো ভুল করে Ctrl+Z চেপে আনডু (Undo) করেন, সেটাও একটা স্ট্যাক। অ্যালগরিদমে ডেপথ-ফার্স্ট সার্চ (DFS) পাথ খুঁজতে স্ট্যাক ব্যবহার করে। এমনকী আপনার লেখা কোডও একটা কল স্ট্যাক (Call Stack)-এর ওপর চলে — যখনই একটা ফাংশন আরেকটা ফাংশনকে ডাকে, সেটা স্ট্যাকের ওপরে পুশ হয়, আর কাজ শেষ হলে পপ হয়ে যায়।

পুশ আর পপ কেন O(1) হয়?

স্ট্যাক সবসময় জানে তার একদম ওপর বা 'টপ' কোথায় আছে। ওপরে নতুন কিছু রাখা বা ওপর থেকে কিছু সরিয়ে নেওয়ার জন্য খোঁজাখুঁজির কোনো দরকার পড়ে না — একটাই সোজা স্টেপ। স্তূপ যত বড়ই হোক না কেন, এই কাজটা একদম চোখের পলকেই হয়ে যায়।

খোঁজা বা সার্চ কেন O(n) হয়?

যদি স্তূপের একদম মাঝামাঝি বা নিচে চাপা পড়ে থাকা কোনো নির্দিষ্ট জিনিস আপনাকে খুঁজতে হয়, তবে আপনাকে ওপর থেকে একটা একটা করে জিনিস পপ করে সরাতে হবে। সবচেয়ে খারাপ অবস্থায় (Worst Case), আপনাকে হয়তো পুরো স্ট্যাকটাই খালি করে ফেলার পর কাঙ্ক্ষিত জিনিসটা পেতে হবে।

কল স্ট্যাক (The Call Stack)

আপনার কোড যখন রান করে, তখন প্রতিটা ফাংশন কল একটা 'কল স্ট্যাক'-এ পুশ হয়। ফাংশনটার কাজ শেষ হলে সেটা পপ হয়ে বের হয়ে যায়। যদি কোনো ফাংশন কাজ শেষ না করে শুধু আরেকটাকে ডাকতেই থাকে ডাকতেই থাকে, তখন একটা সময় স্ট্যাকের জায়গা শেষ হয়ে যায়, আর তখনই দেখা দেয় সেই বিখ্যাত স্ট্যাক ওভারফ্লো (Stack Overflow) এরর!