স্ট্যাক কিঃ
স্ট্যাক / Stack হচ্ছে লিনিয়ার ডেটা স্ট্র্যাকচার। স্ট্যাক কিছুটা অ্যারের মতই। তবে এখানে LIFO স্ট্র্যাকচারে ডেটা গুলো রাখা হয়। LIFO এর পূর্ণরুপ হচ্ছে Last In First Out। যেমন ধরি প্লেটের স্ট্যাক। রান্না ঘরে সাধারণত প্লেট গুলো পরিষ্কার করার পর একটার উপর আরেকটা রাখা হয়। প্লেটের স্ট্যাকে যে প্লেটটা সবার শেষে রাখে, তাই তো সবার আগে নেওয়া হয়, তাই না? যেটা সবার আগে রাখা হয়, ঐটা সবার শেষে নিতে হয়। আরেকটা উদাহরণ হচ্ছে প্রিংগেলস বা লেইস এর স্ট্যাক চিপস গুলো। এগুলোর মধ্যে যে চিপটা সবার শেষে ঢুকানো হয়, সেই চিপচটাই আমরা সবার আগে বের করি।
দৈনন্দিন জীবনে অনেক ক্ষেত্রেই স্ট্যাকের ব্যবহার করে থাকি আমরা। যে ব্রাউজার ব্যবহার করি, তার হিস্ট্রি গুলো সাধারণ স্ট্যাক ডেটা স্ট্যাকচারে রাখা হয়। সর্বশেষ যে সাইটই ব্রাউজ করা হয়, তাই সবার শেষে থাকে। আবার ফোনের যে কল হিস্ট্রি, তাও স্ট্যাক ডেটা স্ট্রাকচারের একটা উদাহরণ। সর্বশেষ যে কলটি করা হয়, তাই সবার শেষে থাকে।
স্ট্যাকের ব্যাসিক অপারেশন গুলোঃ
Push: স্ট্যাকে নতুন আইটেম যুক্ত করা (সর্বশেষ আইটেমের উপরে)। – Time Complexity: O(1)
Pop: স্ট্যাকের সবার উপরের আইটেমটি বের করা। – Time Complexity: O(1)
IsEmpty: স্ট্যাকটি খালি কিনা, তা চেক করা। – Time Complexity: O(1)
Size: স্ট্যাকের সাইজ বের করা। – Time Complexity: O(1)
Peek: স্ট্যাকের সর্বশেষ আইটেম বা উপরের আইটেমটি দেখা। – Time Complexity: O(1)
স্ট্যাকের বিভিন্ন অপারেশনের টাইম কমপ্লেক্সিটি হচ্ছে O(1)।
উপরের ছবিটি দেখি। এখানে সবার প্রথমের স্ট্যাকে কোন আইটেম নেই। এরপর আমরা একটা একটা করে মোট তিনটে আইটেম যোগ বা পুশ করেছি। পপ করা মানে হচ্ছে স্ট্যাক থেকে আইটেমটি বের করে ফেলা। তো যখন স্ট্যাক থেকে কোন আইটেম বের করি, তখন ঐ আইটেমের জায়গা খালি হয়ে যায়। যেখানে নতুন আইটেম রাখা হয়। এখন যদি আমরা আরেকটা আইটেম পুশ করি, তাহলে স্ট্যাকের দ্বিতীয় ইনডেক্সে (3 এর উপরে) আইটেমটি রাখবে।
পাইথন ইমপ্লিমেন্টেশনঃ
পাইথনে সাধারণত লিস্ট ব্যবহার করে স্ট্যাক ইমপ্লিমেন্ট করা যায়। খুব সিম্পল ভাবে যদি লিখি, তাহলে পাইথনে এভাবে স্ট্যাক ইমপ্লিমেন্ট করতে পারিঃ
# Creating an empty stack
stack = []
# append() function to push
stack.append(1)
stack.append(3)
stack.append(5)
stack.append(7)
print("Items in the stack: " + str(stack))
# pop() function to pop
print("Popped item: " + str(stack.pop()))
print("stack after popping an item" + str(stack))
এই প্রোগ্রামটা রান করলে আউটপুট পাবোঃ
Items in the stack: [1, 3, 5, 7] Popped item: 7 stack after popping an item[1, 3, 5]
আবার আমরা চাইলে পাইথনে অবজেক্ট ওরিয়েন্টেড প্রোগ্রামিং ব্যবহার করেও ইমপ্লিমেন্ট করতে পারি।
class Stack:
def __init__(self):
self.items = []
# method for counting items
def __len__(self):
return len(self.items)
# method for printing items
def __str__(self):
return str(self.items)
# Push method
def push(self, item):
self.items.append(item)
# Pop method
def pop(self):
if len(self) == 0:
return "stack is empty"
return self.items.pop()
# Peek method
def peek(self):
return self.items[-1]
# Checking is empty
def is_empty(self):
return len(self) == 0
# Get size
def size(self):
return len(self)
stack = Stack()
# printing empty stack
print(stack)
# adding items
stack.push(1)
stack.push(3)
stack.push(5)
stack.push(7)
print(stack)
print(stack.pop())
# stack after popped an item
print(stack)
print("Size of the stack is: " + str(size(stack)))
print("Last item of the stack: " + str(stack.peek()))
এই প্রোগ্রামটা রান করলে আউটপুট পাবোঃ
[] [1, 3, 5, 7] 7 [1, 3, 5] [1, 3, 5] Size of the stack is: 3 Last item of the stack: 5
অ্যালগরিদম নিয়ে আরো কিছু লেখা।
পাইথন প্রোগ্রামিং শিখতে চাইলে।