ভূমিকা
দুটি স্ট্যাক (Stack) ব্যবহার করে একটি কিউ (Queue) ইমপ্লিমেন্ট করা একটি ক্লাসিক ডেটা স্ট্রাকচার এক্সারসাইজ। একটি স্ট্যাক ইনপুট용 (enqueue), অন্যটি আউটপুট용 (dequeue) হিসেবে কাজ করে।
উদাহরণ কোড
class Queue_structure:
def __init__(self):
self.in_val = Stack_structure()
self.out_val = Stack_structure()
def check_empty(self):
return (self.in_val.check_empty() and self.out_val.check_empty())
def enqueue_operation(self, data):
self.in_val.push_operation(data)
def dequeue_operation(self):
if self.out_val.check_empty():
while not self.in_val.check_empty():
deleted_val = self.in_val.pop_operation()
self.out_val.push_operation(deleted_val)
return self.out_val.pop_operation()
class Stack_structure:
def __init__(self):
self.items = []
def check_empty(self):
return self.items == []
def push_operation(self, data):
self.items.append(data)
def pop_operation(self):
return self.items.pop()
my_instance = Queue_structure()
while True:
print('enqueue ')
print('dequeue')
print('quit')
my_input = input('What operation would you like to perform ?').split()
operation = my_input[0].strip().lower()
if operation == 'enqueue':
my_instance.enqueue_operation(int(my_input[1]))
elif operation == 'dequeue':
if my_instance.check_empty():
print('The queue is empty')
else:
deleted_elem = my_instance.dequeue_operation()
print('The deleted element is :', int(deleted_elem))
elif operation == 'quit':
break
আউটপুট
enqueuedequeue quit What operation would you like to perform ?enqueue 45 enqueue dequeue quit What operation would you like to perform ?enqueue 23 enqueue dequeue quit What operation would you like to perform ?enqueue 78 enqueue dequeue quit What operation would you like to perform ?dequeue The deleted element is : 45 enqueue dequeue quit What operation would you like to perform ?quit
ব্যাখ্যা
Queue_structureদুটি স্ট্যাক মেইন্টেইন করে:in_val(পুশ용) এবংout_val(পপ용)।enqueue: শুধুin_val-এ পুশ করে। O(1)।dequeue: যদিout_valখালি থাকে, তবেin_val-এর সব এলিমেন্ট পপ করেout_val-এ পুশ করে (রিভার্স করে)। তারপরout_val-এর টপ পপ করে। আমор্টাইজড O(1)।Stack_structureপাইথন লিস্ট ব্যবহার করে ইমপ্লিমেন্ট করা হয়েছে (append/pop)।ইন্টারঅ্যাক্টিভ মেনু দিয়ে 엔কিউ/ডিকিউ অপারেশন টেস্ট করা হয়েছে।
বাস্তব ব্যবহার
প্রোডাকশন কোডে পাইথনের বিল্ট-ইন collections.deque ব্যবহার করুন যা O(1) এনকিউ/ডিকিউ দেয় এবং থ্রেড-সেফ।
