26. Queue - Problems

কিউ (Queue) ডেটা স্ট্রাকচার ব্যবহার করে অনেক বাস্তবসম্মত সমস্যা সমাধান করা যায়। এখানে ইন্টারভিউতে আসা জনপ্রিয় কিছু প্রবলেম এবং তাদের লজিক আলোচনা করা হলো।

---

1. কিউ দিয়ে স্ট্যাক ইমপ্লিমেন্ট (Implement Stack using Queues)

কিউ-এর মাধ্যমে LIFO (Last In First Out) মেকানিজম তৈরি করা।

🛠 কর্মপদ্ধতি (Step-by-Step Logic) - Two Queues Approach

1. দুটি কিউ নিন: q1 এবং q2।
2. Push Operation: নতুন এলিমেন্ট q2-তে এঙ্কু (Enqueue) করুন। এবার q1-এর সব এলিমেন্ট এক এক করে q2-তে নিয়ে আসুন। সবশেষে q1 এবং q2 এর নাম অদলবদল (Swap) করুন।
3. এতে করে q1-এর সামনে সবসময় লেটেস্ট এলিমেন্টটি থাকবে।

Implementation (Push Efficient)

// Java Stack using Queues
class MyStack {
    Queue<Integer> q1 = new LinkedList<>(), q2 = new LinkedList<>();
    void push(int x) {
        q2.add(x);
        while (!q1.isEmpty()) q2.add(q1.remove());
        Queue<Integer> temp = q1; q1 = q2; q2 = temp;
    }
    int pop() { return q1.remove(); }
}

# Python Stack using Queues
from collections import deque
class MyStack:
    def __init__(self):
        self.q1, self.q2 = deque(), deque()
    def push(self, x):
        self.q2.append(x)
        while self.q1: self.q2.append(self.q1.popleft())
        self.q1, self.q2 = self.q2, self.q1
    def pop(self):
        return self.q1.popleft()

Broadway

2. ফার্স্ট নন-রিপিটিং ক্যারেক্টার (First Non-repeating Character)

একটি ক্যারেক্টার স্ট্রিমে (Stream) প্রতিটি ধাপে প্রথম যে ক্যারেক্টারটি মাত্র একবার এসেছে সেটি খুঁজে বের করা।

🛠 কর্মপদ্ধতি (Step-by-Step Logic)

1. একটি কিউ এবং একটি ফ্রিকুয়েন্সি অ্যারে (Hash Map) ব্যবহার করুন।
2. নতুন ক্যারেক্টার আসলে তার ফ্রিকুয়েন্সি বাড়িয়ে কিউ-তে যোগ করুন।
3. কিউ-এর সামনের ক্যারেক্টারটি চেক করুন। যদি তার ফ্রিকুয়েন্সি ১-এর বেশি হয়, তবে সেটি পপ (Dequeue) করে দিন।
4. কিউ-এর সামনের এলিমেন্টটিই হবে ফার্স্ট নন-রিপিটিং ক্যারেক্টার।

---

3. ১ থেকে N পর্যন্ত বাইনারি নাম্বার জেনারেশন (Generate Binary Numbers)

🛠 কর্মপদ্ধতি (Step-by-Step Logic)

1. কিউ-তে "1" এঙ্কু করুন।
2. N সংখ্যক বার লুপ চালান:
   • কিউ থেকে মেম্বার পপ করুন এবং প্রিন্ট করুন।
   • পপ করা মেম্বারের সাথে "0" এবং "1" যোগ করে পুনরায় কিউ-তে এঙ্কু করুন।

Implementation

// Java Binary Number Generation
public void generateBinary(int n) {
    Queue<String> q = new LinkedList<>();
    q.add("1");
    while (n-- > 0) {
        String s1 = q.remove();
        System.out.println(s1);
        q.add(s1 + "0");
        q.add(s1 + "1");
    }
}

# Python Binary Number Generation
from collections import deque
def generate_binary(n):
    q = deque(["1"])
    for _ in range(n):
        s1 = q.popleft()
        print(s1)
        q.append(s1 + "0")
        q.append(s1 + "1")

Broadway

4. লেভেল অর্ডার ট্রাভার্সাল (Level Order Traversal - Intro)

একটি বাইনারি ট্রির প্রতিটি লেভেল এক এক করে ট্রাভার্স করা।

🛠 কর্মপদ্ধতি (Step-by-Step Logic)

1. কিউ-তে রুট (Root) নোডটি পুশ করুন।
2. যতক্ষণ কিউ খালি না হয়:
   • একটি নোড পপ করুন এবং তার ভ্যালু প্রিন্ট করুন।
   • যদি নোডটির বাম (Left) বা ডান (Right) চাইল্ড থাকে, তবে তাদের কিউ-তে পুশ করুন।

Implementation

// Java Level Order Traversal
public void levelOrder(Node root) {
    if (root == null) return;
    Queue<Node> q = new LinkedList<>();
    q.add(root);
    while (!q.isEmpty()) {
        Node curr = q.remove();
        System.out.print(curr.data + " ");
        if (curr.left != null) q.add(curr.left);
        if (curr.right != null) q.add(curr.right);
    }
}

# Python Level Order Traversal
from collections import deque
def level_order(root):
    if not root: return
    q = deque([root])
    while q:
        curr = q.popleft()
        print(curr.data, end=" ")
        if curr.left: q.append(curr.left)
        if curr.right: q.append(curr.right)

Broadway

5. স্লাইডিং উইন্ডো ম্যাক্সিমাম (Sliding Window Maximum)

একটি উইন্ডোর সাইজ K হলে, প্রতিবার উইন্ডো সরানোর সাথে সাথে ম্যাক্সিমাম এলিমেন্টটি বের করা।

🛠 কর্মপদ্ধতি (Step-by-Step Logic)

• Deque (Double Ended Queue) ব্যবহার করা সবচেয়ে কার্যকর। ডিকের সামনে সবসময় ম্যাক্সিমাম এলিমেন্টের ইনডেক্স থাকে এবং নতুন ছোট এলিমেন্ট আসলে পেছন থেকে রিমুভ করা হয়।

---

6. সার্কুলার ট্যুর (Circular Tour / Petrol Pump Problem)

এমন একটি পেট্রোল পাম্প খুঁজে বের করা যেখান থেকে শুরু করলে আপনি পুরো সার্কুলার পথটি ভ্রমণ করতে পারবেন।

🛠 কর্মপদ্ধতি (Step-by-Step Logic)

1. প্রতিটি পাম্পে পেট্রোল এবং দূরত্বের হিসাব রাখুন।
2. একটি পাম্প থেকে যাত্রা শুরু করে যদি পেট্রোল শেষ হয়ে যায়, তবে পরের পাম্প থেকে পুনরায় নতুন করে হিসাব শুরু করুন।
3. টোটাল পেট্রোল যদি টোটাল ডিস্টেন্সের সমান বা বেশি হয়, তবেই যাত্রা সম্ভব।

---

📊 কমপ্লেক্সিটি অ্যানালাইসিস (Complexity Analysis)

Problem	Time Complexity	Space Complexity
Generate Binary Numbers	O(n)	O(n)
Level Order Traversal	O(n)	O(w) [w=width]
Sliding Window Max	O(n)	O(k)
Circular Tour	O(n)	O(1)

---

IMPORTANT

কিউ-এর সমস্যাগুলো মূলত সিকোয়েন্স ম্যানেজমেন্ট এবং লেভেল-বাই-লেভেল প্রসেসিং এর ওপর ভিত্তি করে তৈরি।

---

TIP

Deque ব্যবহার করলে স্লাইডিং উইন্ডো সংক্রান্ত জটিল সমস্যাগুলো অনেক সহজে সমাধান করা যায়।