কিউ (Queue) হলো একটি লিনিয়ার ডেটা স্ট্রাকচার যা First In First Out মেকানিজম (FIFO) অনুসরণ করে।
যে এলিমেন্ট প্রথমে কিউতে প্রবেশ করে, সেটিই প্রথমে প্রসেস হয়।
উদাহরণ
কিউ ডেটা স্ট্রাকচার বুঝা যাবে বাস স্ট্যান্ডের কিউ (queue at a bus stand) উদাহরণ দিয়ে।
যে ব্যক্তি প্রথমে বাস স্ট্যান্ডে পৌঁছায়, সে কিউতে প্রথম ব্যক্তি এবং বাকی লোকজন তার পেছনে দাঁড়ায় যতক্ষণ না বাস স্ট্যান্ডে পৌঁছান। যখন বাস আসে, প্রথমে পৌঁছানো ব্যক্তি প্রথমে বাসে চড়বে এবং বাকিরা বাস স্ট্যান্ডে পৌঁছানোর ক্রম অনুযায়ী চড়বে। এভাবে FIRST IN FIRST OUT মেকানিজম অনুসরণ করা হয়।
পাইথনে কিউ ইমপ্লিমেন্টেশন
পাইথনে কিউ বিভিন্নভাবে ইমপ্লিমেন্ট করা যায় অন্য লিনিয়ার ডেটা স্ট্রাকচার বা পাইথন লাইব্রেরির বিল্ট-ইন মডিউল ব্যবহার করে।
পদ্ধতি ১ - লিস্ট ব্যবহার করে ইমপ্লিমেন্ট করা
পাইথনে কিউ লিস্ট ব্যবহার করে ইমপ্লিমেন্ট করা যায়। এটি খুব দক্ষ নয় কারণ লিস্টের শুরুতে এলিমেন্ট ইনসার্ট বা ডিলিট করলে O(n) টাইম লাগে যা অন্যান্য পদ্ধতির চেয়ে ধীর।
অপারেশনগুলো
append() − এই ফাংশন কিউর শেষে একটি এলিমেন্ট যোগ করে।
pop(0) − এই ফাংশন কিউর প্রথম এলিমেন্ট রিমুভ করে এবং রিটার্ন করে।
উদাহরণ
queue = []
queue.append(1)
queue.append(2)
queue.append(3)
print("Initial queue", queue)
print("Element popped from the queue")
print(queue.pop(0))
print(queue.pop(0))
print("Queue after popping some elements", queue)
আউটপুট
Initial queue [1, 2, 3] Element popped from the queue 1 2 Queue after popping some elements [3]
কিউ খালি হয়ে গেলে আরও এলিমেন্ট রিমুভ করা যাবে না। এতে এক্সেপশন হবে।
queue.pop(0) IndexError: pop from empty list
পদ্ধতি ২ - queue.Queue ব্যবহার করে ইমপ্লিমেন্ট করা
এটি পাইথনের বিল্ট-ইন মডিউল ব্যবহার করে কিউ ইমপ্লিমেন্ট করার পদ্ধতি। queue- থেকে Queue ইম্পোর্ট করতে হবে। আমরা নির্দিষ্ট সাইজের কিউ ইনিশিয়ালাইজ করতে পারি। সাইজ শূন্য মানে অনন্ত কিউ।
অপারেশনগুলো
maxsize − কিউতে অনুমোদিত সর্বোচ্চ এলিমেন্ট সংখ্যা
get() − কিউ থেকে প্রথম এলিমেন্ট রিমুভ করে এবং রিটার্ন করে। যদি কিউ খালি থাকে, তবে কিউতে কমপক্ষে একটি এলিমেন্ট আসা পর্যন্ত অপেক্ষা করে।
get_nowait() − কিউ থেকে প্রথম এলিমেন্ট রিমুভ করে এবং রিটার্ন করে। যদি কিউ খালি থাকে, তবে এক্সেপশন উত্থাপন করে।
put(item) − কিউর শেষে একটি এলিমেন্ট অ্যাপেন্ড করে। যদি কিউ ফুল থাকে, তবে ফ্রি স্লট উপলব্ধ হওয়া পর্যন্ত অপেক্ষা করে।
put_nowait(item) − কিউর শেষে একটি এলিমেন্ট অ্যাপেন্ড করে। যদি কিউ ফুল থাকে, তবে এক্সেপশন উত্থাপন করে।
full() − কিউ ফুল হলে True রিটার্ন করে, অন্যথায় False।
empty() − কিউ খালি হলে True রিটার্ন করে, অন্যথায় False।
qsize() − কিউতে উপস্থিত এলিমেন্টের সংখ্যা রিটার্ন করে।
উদাহরণ
from queue import Queue
q = Queue(maxsize=3)
q.put(1)
q.put(2)
q.put(3)
print("Is queue full", q.full())
print("Element popped from the queue")
print(q.get())
print(q.get())
print("Number of elements in queue", q.qsize())
print("Is queue empty", q.empty())
আউটপুট
Is queue full True Element popped from the queue 1 2 Number of elements in queue 1 Is queue empty False
পদ্ধতি ৩ - collections.deque ব্যবহার করে ইমপ্লিমেন্ট করা
এটি পাইথনে কিউ ইমপ্লিমেন্ট করার আরেকটি পদ্ধতি। collections মডিউল থেকে deque ইম্পোর্ট করতে হবে।
অপারেশনগুলো
append() − এই ফাংশন কিউর শেষে একটি এলিমেন্ট যোগ করে।
popleft() − এই ফাংশন কিউর প্রথম এলিমেন্ট O(1) টাইম কমপ্লেক্সিটিতে রিমুভ করে এবং রিটার্ন করে।
উদাহরণ
from collections import deque
queue = deque()
queue.append(1)
queue.append(2)
queue.append(3)
print("Initial queue: ", queue)
print("Element popped from the queue")
print(queue.popleft())
print(queue.popleft())
print("Queue after popping some elements: ", queue)
আউটপুট
Initial queue: deque([1, 2, 3]) Element popped from the queue 1 2 Queue after popping some elements: deque([3])
খালি deque-এ popleft() ফাংশন ব্যবহার করলে এক্সেপশন হবে।
