স্ট্যাক ও কিউপড়তে ৪ মিনিট লাগবে

কিউ (Queue)

লাইনে দাঁড়িয়ে অপেক্ষা — যে আগে আসবে, সে আগে পাবে

enqueue: O(1)dequeue: O(1)peek: O(1)search: O(n)space: O(n)

ধরুন আপনি কমলাপুর স্টেশনে ট্রেনের টিকিট কাটার জন্য লাইনে দাঁড়িয়ে আছেন। যে লোকটা সবার আগে এসে লাইনে দাঁড়িয়েছে, সে সবার আগে টিকিট পাবে। এখানে কেউ মাঝখান দিয়ে লাইন ভেঙে আগে যেতে পারবে না। সবাইকে নিজের সিরিয়ালের জন্য অপেক্ষা করতে হবে।

এটাই হলো কিউ (Queue)। এর একটাই সোজা নিয়ম: ফার্স্ট ইন, ফার্স্ট আউট (First In, First Out) — সংক্ষেপে যাকে বলা হয় FIFO।

এনকিউ (Enqueue) এবং ডিকিউ (Dequeue)

এখানে মূল কাজ মূলত দুটো:

এনকিউ (Enqueue) — লাইনের একদম পেছনে গিয়ে দাঁড়ানো (নতুন কাউকে লাইনে যোগ করা)
ডিকিউ (Dequeue) — লাইনের একদম সামনের জনকে সার্ভিস দেওয়া (লাইন থেকে বের করে দেওয়া)

এছাড়াও আপনি পিক (Peek) করতে পারেন — মানে লাইনের একদম সামনে কে আছে তাকে জাস্ট উঁকি দিয়ে দেখা, কিন্তু বের না করা।

কোথায় কোথায় এই কিউ ব্যবহার করা হয়?

যেখানেই সিরিয়াল বা ফেয়ার ওয়েটিং দরকার, সেখানেই কিউ লাগে! যেমন, প্রিন্টারে একসাথে অনেকগুলো প্রিন্ট দিলে সেগুলো একটা কিউতে জমা হয়। ওয়েবসাইটে অনেক রিকোয়েস্ট একসাথে এলে সেগুলো সিরিয়ালে প্রসেস হয়। আর অ্যালগরিদমের দুনিয়ায় BFS (Breadth-First Search) নামের খুব বিখ্যাত একটা টেকনিক এই কিউ ব্যবহার করে গ্রাফের লেভেল বাই লেভেল স্ক্যান করে।

◈ লাইনে দাঁড়ান এবং সার্ভিস নিন!

← → অ্যারো কি (arrow key) ব্যবহার করুন · উপাদানগুলোতে ক্লিক করুন

কিউ-এর অপারেশনগুলো (Queue Operations)

from collections import deque

queue = deque()
queue.append(10)   # enqueue
queue.append(20)
queue.append(30)
print('Front:', queue[0])         # peek
print('Size:', len(queue))
val = queue.popleft()             # dequeue
print('Dequeued:', val)
print('Current queue:', list(queue))

Output

Front: 10
Size: 3
Dequeued: 10
Current queue: [20, 30]

দ্রষ্টব্য: কিউ জিনিসটা খুবই ফেয়ার বা ইনসাফওয়ালা — যে লাইনে সবচেয়ে বেশি সময় ধরে দাঁড়িয়ে আছে, সে-ই আগে সার্ভিস পাবে। একদম আমাদের বাস্তব জীবনের মতো!

এনকিউ আর ডিকিউ কেন O(1) হয়?

একটা কিউ সাধারণত দুটো পয়েন্টার বা ট্যাগ নজর রাখে: সামনে (front) আর পেছনে (back)। পেছনে কাউকে যোগ করতে মাত্র একটা স্টেপ লাগে। — এবং দক্ষ কিউ প্রায়ই একটা ডাবলি লিংকড লিস্ট বা সার্কুলার বাফার দিয়ে তৈরি করা হয়। আবার সামনে থেকে কাউকে বের করতেও ওই একটা স্টেপই। বাকি কাউকে এদিক-সেদিক ঠেলে সরাতে হয় না। এইজন্য এই দুটো কাজই একদম চোখের পলকে, মানে ইনস্ট্যান্ট হয়।

BFS-এর ভেতর কিউ

Breadth-First Search-এ আপনি একটা গ্রাফকে ঢেউয়ের মতো স্ক্যান করেন — প্রথমে ১ দূরত্বে থাকা সব প্রতিবেশী, এরপর ২ দূরত্বে থাকা, এইরকম। এই কাজটায় কিউ একদম খাপে খাপ মিলে যায়: নতুন যে পড়শিকে খুঁজে পাবেন তাকে লাইনের পেছনে এনকিউ করবেন, আর সামনে থেকে ডিকিউ করে তাকে এক্সপ্লোর করবেন। এতে সিরিয়াল একদম পারফেক্ট থাকে।

কিউ বনাম স্ট্যাক (Queue vs Stack)

মূল পার্থক্যটা হলো সিরিয়ালে। স্ট্যাক হলো LIFO (Last In First Out) — অর্থাৎ সবার শেষে যে আসবে সে সবার আগে যাবে, যেমন বিয়ের দাওয়াতের প্লেটের স্তূপ। আর কিউ হলো FIFO — যে আগে থেকে আছে সে আগে যাবে, যেমন ব্যাংকের লাইন। আপনার কী ধরনের কাজ দরকার, তার ওপর ভিত্তি করে দুটোই সুপার দরকারী।

Complexity

Enqueue (যোগ করা)

এক পলকে লাইনের পেছনে যোগ

সাথে সাথে O(1)

Dequeue (বের করা)

এক পলকে লাইনের সামনে থেকে বের করা

সাথে সাথে O(1)

Peek (উঁকি দিয়ে দেখা)

বের না করেই সামনে কে আছে দেখা

সাথে সাথে O(1)

Search (খোঁজা)

পুরো লাইন খুঁজে দেখতে হয়

স্লো O(n)

Space (জায়গা)

লাইনের প্রতিটা জিনিসের জন্য একটা স্লট

n-এর সাথে বাড়ে O(n)

কিউ দিয়ে BFS (Breadth-First Search)

from collections import deque

def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for nb in graph[node]:
            if nb not in visited:
                visited.add(nb)
                queue.append(nb)
    return order

graph = {0: [1, 2], 1: [3], 2: [3], 3: []}
print(bfs(graph, 0))