ভূমিকা
দুটি কিউ ব্যবহার করে একটি স্ট্যাক ইমপ্লিমেন্ট করা যায়। একটি কিউ হол্ড করে সকল এলিমেন্ট, অন্যটি অস্থায়ীভাবে ব্যবহার হয় পপ অপারেশনের সময় অর্ডার মেইনটেইন করার জন্য।
উদাহরণ কোড
class Stack_structure:
def __init__(self):
self.queue_1 = Queue_structure()
self.queue_2 = Queue_structure()
def check_empty(self):
return self.queue_2.check_empty()
def push_val(self, data):
self.queue_1.enqueue_operation(data)
while not self.queue_2.check_empty():
x = self.queue_2.dequeue_operation()
self.queue_1.enqueue_operation(x)
self.queue_1, self.queue_2 = self.queue_2, self.queue_1
def pop_val(self):
return self.queue_2.dequeue_operation()
class Queue_structure:
def __init__(self):
self.items = []
self.size = 0
def check_empty(self):
return self.items == []
def enqueue_operation(self, data):
self.size += 1
self.items.append(data)
def dequeue_operation(self):
self.size -= 1
return self.items.pop(0)
def size_calculate(self):
return self.size
my_instance = Stack_structure()
print('Menu')
print('push ')
print('pop')
print('quit')
while True:
my_input = input('What operation would you like to perform ? ').split()
operation = my_input[0].strip().lower()
if operation == 'push':
my_instance.push_val(int(my_input[1]))
elif operation == 'pop':
if my_instance.check_empty():
print('Stack is empty.')
else:
print('The deleted value is:', my_instance.pop_val())
elif operation == 'quit':
break
আউটপুট
Menu pushpop quit What operation would you like to perform ? push 56 What operation would you like to perform ? push 34 What operation would you like to perform ? push 78 What operation would you like to perform ? push 90 What operation would you like to perform ? pop The deleted value is: 90 What operation would you like to perform ? quit
ব্যাখ্যা
push_val: নতুন এলিমেন্টqueue_1-এ এনকিউ করা হয়, তারপরqueue_2-এর সব এলিমেন্ট ডিকিউ করেqueue_1-এ এনকিউ করা হয় (তाकি নতুন এলিমেন্ট ফ্রন্টে চলে যায়)। এরপর দুটি কিউ সোয়াপ করা হয়। পশ O(n)।pop_val: শুধুqueue_2-এর ফ্রন্ট ডিকিউ করা হয়। পপ O(1)।Queue_structureলিস্ট এবং সাইজ কাউন্টার ব্যবহার করে ইমপ্লিমেন্ট করা হয়েছে।pop(0)O(n), কিন্তু ডেমোর জন্য chấp ন্যাবল।
বিকল্প পদ্ধতি (পশ O(1), পপ O(n))
পশে শুধু queue_1-এ এনকিউ করুন। পপের সময় queue_1-এর সব এলিমেন্ট ছাড়া লাস্টটি queue_2-এ ট্রান্সফার করুন, লাস্টটি রিটার্ন করুন, কিউগুলো সোয়াপ করুন।
