ভূমিকা
একটি সিঙ্গল কিউ ব্যবহার করেও স্ট্যাক ইমপ্লিমেন্ট করা যায়। পপ অপারেশনের সময় কিউর সাইজ-১ বার রোটেট (ডিকিউ→এনকিউ) করা হয় যাতে লাস্ট এলিমেন্ট ফ্রন্টে চলে আসে।
উদাহরণ কোড
class Stack_structure:
def __init__(self):
self.q = Queue_structure()
def check_empty(self):
return self.q.check_empty()
def push_val(self, data):
self.q.enqueue_operation(data)
def pop_val(self):
for _ in range(self.q.size_calculate() - 1):
dequeued = self.q.dequeue_operation()
self.q.enqueue_operation(dequeued)
return self.q.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('The 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 89 What operation would you like to perform ? push 43 What operation would you like to perform ? push 76 What operation would you like to perform ? push 56 What operation would you like to perform ? pop The deleted value is: 56 What operation would you like to perform ? quit
ব্যাখ্যা
push_val: শুধু কিউর রিয়ারে এনকিউ। O(1)।pop_val: কিউর সাইজ-১ বার ফ্রন্ট এলিমেন্ট ডিকিউ করে রিয়ারে এনকিউ (রোটেট)। লাস্ট এলিমেন্ট ফ্রন্টে এসে ডিকিউ হয়। O(n)।দুটি কিউ ব্যবহার করে পশ O(n), পপ O(1) করা যায় (পূর্বের নিবন্ধ)। এক কিউয়ের সাথে পশ O(1), পপ O(n)। ট্রেড-অফ।
