ভূমিকা
একটি স্ট্যাকের এলিমেন্টগুলো রিকার্শন ব্যবহার করে রিভার্স করা (বটমটি টপে, টপটি বটоме) একটি ক্লাসিক সমস্যা। এর জন্য দুটি হেল্পার ফাংশন দরকার: একটি বটоме এলিমেন্ট ইনসার্ট করার জন্য, আর একটি পুরো স্ট্যাক রিভার্স করার জন্য।
উদাহরণ কোড
class Stack_structure:
def __init__(self):
self.items = []
def check_empty(self):
return self.items == []
def push_val(self, data):
self.items.append(data)
def pop_val(self):
return self.items.pop()
def print_it(self):
for data in reversed(self.items):
print(data)
def insert_bottom(instance, data):
if instance.check_empty():
instance.push_val(data)
else:
deleted_elem = instance.pop_val()
insert_bottom(instance, data)
instance.push_val(deleted_elem)
def stack_reverse(instance):
if not instance.check_empty():
deleted_elem = instance.pop_val()
stack_reverse(instance)
insert_bottom(instance, deleted_elem)
my_instance = Stack_structure()
data_list = input('Enter the elements to add to the stack: ').split()
for data in data_list:
my_instance.push_val(int(data))
print('The reversed stack is:')
my_instance.print_it()
stack_reverse(my_instance)
print('The stack is:')
my_instance.print_it()
আউটপুট
Enter the elements to add to the stack: 23 56 73 81 8 9 0 The reversed stack is: 0 9 8 81 73 56 23 The stack is: 23 56 73 81 8 9 0
ব্যাখ্যা
print_it: স্ট্যাকের টপ থেকে বটোম প্রিন্ট করে (reversed লিস্ট ব্যবহার করে)।insert_bottom(instance, data): স্ট্যাক খালি হলে পুশ করে। নহলে টপ পপ করে, রিকার্সিভলি বটোমে ইনসার্ট করে, পপ করা এলিমেন্ট আবার পুশ করে।stack_reverse(instance): স্ট্যাক খালি না হলে টপ পপ করে, বাকি স্ট্যাক রিকার্সিভলি রিভার্স করে, পপ করা এলিমেন্ট বটোমে ইনসার্ট করে।টাইম কমপ্লেক্সিটি: O(n²) (প্রতিটি ইনসার্ট বটোম O(n), n বার কল হয়)। স্পেস কমপ্লেক্সিটি: O(n) রিকার্শন স্ট্যাকের জন্য।
ইটারেটিভ বিকল্প
def reverse_stack_iterative(stack):
temp = []
while not stack.check_empty():
temp.append(stack.pop_val())
for item in temp:
stack.push_val(item)
এটি O(n) টাইম এবং O(n) এক্সট্রা স্পেস।
