কিউঃ
স্ট্যাকের মত আরেকটা লিনিয়ার ডেটা স্ট্যাকচার হচ্ছে কিউ। কিউ FIFO রুল ফলো করে ডেটা রাখা হয়। FIFO এর পূর্ণরুপ হচ্ছে First In First Out। মানে যে আইটেমটা সবার আগে রাখব, তাই সবার আগে বের করতে হবে। সৎ ডেটা স্ট্র্যাকচার! ঘুষের কারবার নেই! দৈনন্দিন জীবনে প্রায় প্রতিদিনই আমাদের অজান্তেই কিউ ডেটা স্ট্র্যাকচার ব্যবহার করছি। পিজ্জা অর্ডার দিব? কিউতে দাঁড়াও। যে সবার আগে দাঁড়াবে, সেই সবার আগে অর্ডার দিতে পারবে।
কিউ এর ব্যাসিক অপারেশন গুলোঃ
Enqueue: নতুন আরেকটা আইটেম কিউ এর শেষে যুক্ত করা।
Dequeue: কিউ এর প্রথম থেকে একটা আইটেম রিমুভ করা।
IsEmpty: কিউ খালি কিনা, তা চেক করা।
Peek: কিউ এর সামনে বা প্রথমে কোন আইটেম আছে, তা দেখা।
Size: কিউ এর সাইজ বের করা।
উপরের ছবিটি দেখি। এখানে সবার প্রথমের কিউতে কোন আইটেম নেই। এরপর আমরা একটা একটা করে মোট তিনটে আইটেম যোগ বা Enqueue করেছি। Dequeue করা মানে হচ্ছে কিউর প্রথম দিক থেকে একটা আইটেম বের করে ফেলা। তো যখন কিউ থেকে কোন আইটেম বের করি, তখন ঐ আইটেমের জায়গা খালি হয়ে যায়। এখানে দেখি, স্ট্যাক থেকে একটি আইটেম Dequeue করার পর প্রথম আইটেমের ইনডেক্স খালি হয়ে গিয়েছে। এখন যদি আমরা নতুন আরেকটা আইটেম পুশ করি, তাহলে কিউ এর শেসে যুক্ত হবে। মানে 8 এর পর।
পাইথনে ইমপ্লিমেন্টেশনঃ
পাইথনে সাধারণত লিস্ট ব্যবহার করে কিউ ইমপ্লিমেন্ট করা যায়। খুব সিম্পল ভাবে যদি লিখি, তাহলে পাইথনে এভাবে কিউ ইমপ্লিমেন্ট করতে পারিঃ
# Initializing a empty queue
queue = []
# append() function to enqueue
queue.append(2)
queue.append(4)
queue.append(6)
queue.append(8)
print("Items in the queue: " + str(queue))
# pop() function to dequeue
print("Dequeued item: " +str(queue.pop(0)))
print("Queue after dequeue an imte: " + str(queue))
এই প্রোগ্রামটা রান করলে আউটপুট পাবোঃ
Items in the queue: [2, 4, 6, 8] Dequeued item: 2 Queue after dequeue an imte: [4, 6, 8]
আবার আমরা চাইলে পাইথনে অবজেক্ট ওরিয়েন্টেড প্রোগ্রামিং ব্যবহার করেও ইমপ্লিমেন্ট করতে পারি।
from collections import deque
class Queue:
def __init__(self):
self.items = deque()
# Enqueue method
def enqueue(self, item):
self.items.append(item)
# Dequeue method
def dequeue(self):
return self.items.popleft()
# Peek method
def peek(self):
return self.items[0]
# Method for checking is_empty
def is_empty(self):
return len(self.items) == 0
# Method for getting the size of the queue
def size(self):
return len(self.items)
# __str__() for using print
def __str__(self):
return str(self.items)
queue = Queue()
print(queue)
queue.enqueue(2)
queue.enqueue(4)
queue.enqueue(6)
queue.enqueue(8)
print("Current items in the queue: " + str(queue))
print("size of the queue: ", queue.size())
queue.dequeue()
print("Items in the queue after dequeue: " + str(queue))
print("Front item in the queue:", queue.peek())
print(queue.is_empty())
এই প্রোগ্রামটা রান করলে আউটপুট পাবোঃ
deque([]) Current items in the queue: deque([2, 4, 6, 8]) size of the queue: 4 Items in the queue after dequeue: deque([4, 6, 8]) Front item in the queue: 4 False
প্রশ্ন আসতে পারে আমরা কেউ deque ডেটাটাইপ ব্যবহার করে কিউ ইমপ্লিমেন্ট করেছি যেখানে স্ট্যাক ইমপ্লিমেন্ট করতে সাধারণ লিস্ট ব্যবহার করেছি। এর প্রধান কারণ হচ্ছে লিস্টের শেষে ডেটা যোগ করা বা ডেটা রিমুভ করা সহজ। লিস্টের শুরুর দিক থেকে আইটেম রিমুভ করা স্লো, বেশি কম্পিউটার ইন্সট্রাকশনের দরকার হয়। এই জন্য আমরা deque ডেটাটাইপ ব্যবহার করেছি। আপনি চাইলে লিস্ট ব্যবহার করেও কিউ ইমপ্লিমেন্ট করতে পারেন। নিজে নিজে চেষ্টা করে দেখুন।