স্ট্যাক (Stack) হলো একটি লিনিয়ার ডেটা স্ট্রাকচার যা Last In First Out মেকানিজম (LIFO) অনুসরণ করে। যা এলিমেন্ট প্রথমে স্ট্যাকে প্রবেশ করে, সেটিই শেষে প্রসেস হয়।
উদাহরণ
স্ট্যাক ডেটা স্ট্রাকচার বুঝা যাবে ডিশের স্ট্যাক (stack of dishes) উদাহরণ দিয়ে।
ডিশগুলো একে অপরের ওপর পাইল আপ করা থাকে। প্রথম প্লেট বা ডিশ পাইলের নিচে থাকে এবং শেষে রাখা ডিশ পাইলের বা স্ট্যাকের শীর্ষে থাকে। যখনই আমাদের একটি প্লেট দরকার হয়, আমরা স্ট্যাকের শীর্ষের প্লেটটি নেবা যা সবশেষে ইনসার্ট বা রাখা হয়েছিল। যে প্লেটটি প্রথমে রাখা হয়েছিল সেটিই শেষে নেওয়া হবে। এভাবে LAST IN FIRST OUT মেকানিজম অনুসরণ করা হয়।
পাইথনে স্ট্যাক ইমপ্লিমেন্টেশন
পাইথনে স্ট্যাক বিভিন্নভাবে ইমপ্লিমেন্ট করা যায় অন্য লিনিয়ার ডেটা স্ট্রাকচার বা পাইথন লাইব্রেরির বিল্ট-ইন মডিউল ব্যবহার করে।
পদ্ধতি ১ - লিস্ট ব্যবহার করে ইমপ্লিমেন্ট করা
পাইথনে স্ট্যাক লিস্ট ব্যবহার করে ইমপ্লিমেন্ট করা যায়। কিন্তু লিস্ট ব্যবহার করে স্ট্যাক ইমপ্লিমেন্ট করা তত দক্ষ নয় এবং তাই সুপারিশ করা হয় না।
অপারেশনগুলো
append() − এই ফাংশন স্ট্যাকের শেষে একটি এলিমেন্ট যোগ করে।
pop() − এই ফাংশন স্ট্যাকের শেষ বা শীর্ষ এলিমেন্ট রিমুভ করে এবং রিটার্ন করে। এই ফাংশন LIFO অর্ডারে এলিমেন্ট পপ করে।
উদাহরণ
stack = []
stack.append(1)
stack.append(2)
stack.append(3)
print("Initial Stack", stack)
print("Element popped from the stack")
print(stack.pop())
print(stack.pop())
print("Stack after popping some elements", stack)
আউটপুট
Initial Stack [1, 2, 3] Element popped from the stack 3 2 Stack after popping some elements [1]
স্ট্যাক খালি হয়ে গেলে আরও এলিমেন্ট রিমুভ করা যাবে না। এতে এক্সেপশন হবে।
stack.pop() IndexError: pop from empty list
পদ্ধতি ২ - queue.LifoQueue ব্যবহার করে ইমপ্লিমেন্ট করা
এটি পাইথনের বিল্ট-ইন মডিউল ব্যবহার করে স্ট্যাক ইমপ্লিমেন্ট করার পদ্ধতি। queue- থেকে LifoQueue ইম্পোর্ট করতে হবে। আমরা নির্দিষ্ট সাইজের LifoQueue বা স্ট্যাক ইনিশিয়ালাইজ করতে পারি। সাইজ শূন্য মানে অনন্ত স্ট্যাক।
অপারেশনগুলো
maxsize − স্ট্যাকে অনুমোদিত সর্বোচ্চ এলিমেন্ট সংখ্যা
get() − স্ট্যাক থেকে শেষ বা শীর্ষ এলিমেন্ট রিমুভ করে এবং রিটার্ন করে। যদি স্ট্যাক খালি থাকে, তবে স্ট্যাকে কমপক্ষে একটি এলিমেন্ট আসা পর্যন্ত অপেক্ষা করে।
get_nowait() − স্ট্যাক থেকে শেষ এলিমেন্ট রিমুভ করে এবং রিটার্ন করে। যদি স্ট্যাক খালি থাকে, তবে এক্সেপশন উত্থাপন করে।
put(item) − স্ট্যাকের শেষে একটি এলিমেন্ট অ্যাপেন্ড করে। যদি স্ট্যাক ফুল থাকে, তবে ফ্রি স্লট উপলব্ধ হওয়া পর্যন্ত অপেক্ষা করে।
put_nowait(item) − স্ট্যাকের শেষে একটি এলিমেন্ট অ্যাপেন্ড করে। যদি স্ট্যাক ফুল থাকে, তবে এক্সেপশন উত্থাপন করে।
full() − স্ট্যাক ফুল হলে True রিটার্ন করে, অন্যথায় False।
empty() − স্ট্যাক খালি হলে True রিটার্ন করে, অন্যথায় False।
qsize() − স্ট্যাকে উপস্থিত এলিমেন্টের সংখ্যা রিটার্ন করে।
উদাহরণ
from queue import LifoQueue
s = LifoQueue(maxsize=3)
s.put(1)
s.put(2)
s.put(3)
print("Is stack full", s.full())
print("Element popped from the stack")
print(s.get())
print(s.get())
print("Number of elements in stack", s.qsize())
print("Is stack empty", s.empty())
আউটপুট
Is stack full True Element popped from the stack 3 2 Number of elements in stack 1 Is stack empty False
পদ্ধতি ৩: collections.deque ব্যবহার করে ইমপ্লিমেন্ট করা
এটি পাইথনে স্ট্যাক ইমপ্লিমেন্ট করার আরেকটি পদ্ধতি। collections মডিউল থেকে deque ইম্পোর্ট করতে হবে।
অপারেশনগুলো
append() − এই ফাংশন স্ট্যাকের শেষে একটি এলিমেন্ট যোগ করে।
pop() − এই ফাংশন স্ট্যাকের শেষ এলিমেন্ট O(1) টাইম কমপ্লেক্সিটিতে রিমুভ করে এবং রিটার্ন করে।
উদাহরণ
from collections import deque
stack = deque()
stack.append(1)
stack.append(2)
stack.append(3)
print("Initial stack: ", stack)
print("Element popped from the stack")
print(stack.pop())
print(stack.pop())
print("Stack after popping some elements: ", stack)
আউটপুট
Initial stack: deque([1, 2, 3]) Element popped from the stack 3 2 Stack after popping some elements: deque([1])
খালি deque-এ pop() ফাংশন ব্যবহার করলে এক্সেপশন হবে।
