Queue, Deque আর PriorityQueue — কে আগে সেবা পাবে

১ · অবস্থান নয়, ক্রম — কে আগে সেবা পাবে

পর্ব ৩০-এ List দেখেছেন: প্রতিটি জিনিসের একটি index আছে, আর get(5) দিয়ে যেকোনো ঘরে সরাসরি যাওয়া যায়। পর্ব ৩১-এ Set আর Map দেখেছেন: সেখানে প্রশ্ন “এটা আছে কি না” বা “এই key-এর মান কী”. কিন্তু অনেক বাস্তব সমস্যায় এই দুই প্রশ্নের কোনোটিই জরুরি নয়। জরুরি শুধু একটি কথা — এরপর কাকে সেবা দেব?

তিনটি পরিচিত দৃশ্য ভাবুন:

তিনটিতেই কাজ দুটি মাত্র: একটি জিনিস ঢোকানো, আর “পরের জন”-কে বের করা। পার্থক্য শুধু “পরের জন” কে, সেই নিয়মে। এমন নিয়ম মেনে চলা collection-কে বলে queue (সাধারণ অর্থে), আর LIFO-নিয়মের রূপটিকে বলে stack. মনে রাখবেন, আগের পর্বগুলোতে (পর্ব ০৫, ১২) যে call stack দেখেছিলেন, সেটাও ঠিক এই LIFO নিয়মে চলে — শেষে ডাকা method আগে শেষ হয়।

Java এই তিন ধারণার প্রতিটির জন্য একটি করে interface আর বাস্তবায়ন দেয়:

পর্ব ২১-এর “interface-এর দিকে তাকিয়ে লিখুন” নীতিটি এখানেও খাটে: ভ্যারিয়েবলের টাইপ লিখুন Queue<String> বা Deque<String>, আর ডান দিকে বাস্তবায়ন — new ArrayDeque<>(). তাহলে কোড পড়েই বোঝা যায় আপনি কোন নিয়মে কাজ করছেন, আর পরে বাস্তবায়ন বদলালে বাকি কোড ছুঁতে হয় না।

২ · Queue interface — একই কাজের দুই পরিবারের method

একটি queue-এর তিনটি মৌলিক কাজ: শেষে ঢোকানো, সামনে থেকে বের করা, আর বের না করে সামনেরটা দেখা। Queue interface প্রতিটি কাজের জন্য দুটি method দেয়। পার্থক্য হলো, কাজটি সম্ভব না হলে — queue খালি, বা সীমিত আকারের queue ভরা — তারা কী করে:

খালি টোকেন কাউন্টারে নিজে চালিয়ে দেখা যায়:

import java.util.ArrayDeque;
import java.util.Queue;

class Main {
    public static void main(String[] args) {
        Queue<String> counter = new ArrayDeque<>();
        System.out.println(counter.poll());
        System.out.println(counter.peek());
        counter.remove();
    }
}

null
null
Exception in thread "main" java.util.NoSuchElementException
	at java.base/java.util.ArrayDeque.removeFirst(ArrayDeque.java:361)
	at java.base/java.util.ArrayDeque.remove(ArrayDeque.java:522)
	at Main.main(Main.java:9)

poll() আর peek() চুপচাপ null দিল; remove() লাইন ৯-এ NoSuchElementException ছুড়ল। Stack trace-এর প্রথম দুই লাইন JDK-র ভেতরের — ArrayDeque.remove আসলে removeFirst-কে ডাকে, আর সেখানেই exception তৈরি হয়। আপনার ভুলের ঠিকানা হলো শেষ লাইন, Main.java:9.

কোন পরিবার কখন

• খালি হওয়া স্বাভাবিক ঘটনা হলে — offer/poll/peek. কাজের লাইন শেষ হয়ে যাওয়া কোনো ভুল নয়; তাই while ((job = queue.poll()) != null) ধাঁচের লুপ পরিষ্কার।
• খালি থাকা মানে প্রোগ্রামের যুক্তিতে ভুল হলে — remove/element. যেমন আপনি নিশ্চিত যে এখানে অন্তত একটি জিনিস থাকবেই; না থাকলে সেখানেই থেমে যাওয়া ভালো (fail-fast নীতি)।
• সীমিত আকারের queue-এ (যেমন পরে দেখবেন ArrayBlockingQueue) offer ভরা থাকলে false দেয় আর add ছোড়ে IllegalStateException: Queue full — দুটিই যাচাই করা আউটপুট। ArrayDeque, PriorityQueue নিজে থেকে বড় হয়, তাই সেখানে offer সবসময় true.

৩ · ArrayDeque — গোল করে ঘোরানো একটি array

একটি queue বানাতে প্রথমে মনে হয় সাধারণ array বা ArrayList নিই: শেষে যোগ করি, আর remove(0) দিয়ে সামনের জনকে বের করি। সমস্যা হলো remove(0)-এর পর বাকি সবাইকে এক ঘর করে বাঁয়ে সরাতে হয় — দশ লাখ জিনিসের তালিকায় প্রতিটি বের করায় দশ লাখ কপি। এটা O(n), যেখানে আমরা চাই O(1).

এই কৌশলের নাম circular buffer (ring buffer). ArrayDeque ভেতরে ঠিক এটাই করে: একটি array আর দুটি index — head আর tail. index শেষ ঘর পেরোলে আবার ০-তে ফিরে আসে (গাণিতিকভাবে, array-এর দৈর্ঘ্য দিয়ে ভাগশেষ)। ধাপে ধাপে দেখুন (বোঝার সুবিধায় ৮ ঘরের array ধরে নিয়েছি; JDK-র আসল শুরুর আকার ও বাড়ার নিয়ম আলাদা):

1Deque<String> q = new ArrayDeque<>();2offer A, B, C, D, E3poll() × 3     // A, B, C বের4offer F, G, H5offer I, J6offer K        // array ভরে গেল

সামনের দিকে ঢোকানোও (addFirst) একই কৌশলে চলে: head এক ঘর পিছোয়, আর ০-এর আগে গেলে ঘুরে শেষ ঘরে চলে যায়। তাই দুই মাথাতেই ঢোকানো আর বের করা O(1).

কেন LinkedList নয়

LinkedList-ও Queue আর Deque মানে, আর পুরোনো বই ও AI-এর কোডে Queue<Integer> q = new LinkedList<>(); খুব দেখা যায়। কাজ করে, কিন্তু Java-র নিজের documentation-এ ArrayDeque সম্পর্কে লেখা: “This class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue.” কারণ তিনটি:

• প্রতিটি জিনিসের জন্য আলাদা node object. LinkedList-এ প্রতিটি উপাদান একটি node-এ থাকে, যার ভেতরে আগের ও পরের node-এর reference — প্রতিটি offer মানে নতুন object, আর garbage collector-এর জন্য বাড়তি কাজ।
• মেমরিতে ছড়ানো। Node-গুলো heap-এর যেখানে-সেখানে থাকে; array-এর ঘরগুলো পাশাপাশি। আধুনিক CPU-এর cache পাশাপাশি থাকা ডেটা অনেক দ্রুত পড়ে।
• null রাখা যায় — তাই অংশ ২-এর poll()-এর সংকেত অস্পষ্ট হয়ে যায়।

LinkedList-এর সত্যিকারের সুবিধা হলো iterator দিয়ে হাঁটার সময় মাঝখানে ঢোকানো-মোছা; queue বা stack-এ সেটা লাগে না। একটি ব্যতিক্রম মনে রাখুন: queue-তে যদি সত্যিই null রাখার দরকার হয় (খুব বিরল, আর সাধারণত নকশার দুর্বলতা), তখন ArrayDeque চলবে না।

৪ · Deque — দুই মাথার লাইন, আর stack হিসেবে ব্যবহার

Deque (উচ্চারণ “ডেক”, double-ended queue-এর সংক্ষেপ) এমন লাইন, যার সামনে আর পেছনে — দুই মাথাতেই ঢোকানো আর বের করা যায়। Queue-এর মতোই প্রতিটি কাজের দুই পরিবারের method আছে, এবার প্রতিটি মাথার জন্য আলাদা:

প্রতিটি ঘরে বাঁয়েরটি exception ছোড়ে, ডানেরটি false/null দেয়। Queue হিসেবে ব্যবহার করলে offer মানে offerLast আর poll মানে pollFirst — পেছনে ঢোকে, সামনে দিয়ে বের হয়।

Stack হিসেবে — push, pop, peek

একটি মাথা ব্যবহার না করলেই Deque হয়ে যায় stack. এর জন্য Deque-এ তিনটি পরিচিত নামের method আছে, যারা সবাই সামনের মাথায় কাজ করে:

• push(e) = addFirst(e) — ওপরে রাখা
• pop() = removeFirst() — ওপরেরটা তোলা; খালি হলে NoSuchElementException
• peek() = peekFirst() — ওপরেরটা দেখা; খালি হলে null

ফলে একটি ArrayDeque-এ ১, ২, ৩ push করে ছাপালে আসে [3, 2, 1] — ওপরের জিনিস প্রথমে। কথাটা মনে রাখুন; অংশ ৫-এ এটার সাথে পুরোনো Stack-এর আউটপুট মেলাব।

ব্রাউজারের Back আর Forward — দুটি stack

ব্রাউজার Back আর Forward দুটোই সামলায় দুটি stack দিয়ে। নতুন পাতায় গেলে বর্তমান পাতা back-এ push হয়, আর forward খালি হয়ে যায় (নতুন পথে গেলে পুরোনো “সামনের” ইতিহাস অর্থহীন)। Back চাপলে বর্তমান পাতা forward-এ push হয়, আর back থেকে pop করা পাতা হয় নতুন বর্তমান। Forward ঠিক উল্টো। google.com → abcltech.com → abcltech.com/java ঘুরে একবার Back চাপার পর যাচাই করা অবস্থা: বর্তমান abcltech.com, back = [google.com], forward = [abcltech.com/java]. টেক্সট এডিটরের Undo/Redo-ও হুবহু এই নকশা: প্রতিটি বদল undo-stack-এ যায়, Undo চাপলে সেটা redo-stack-এ সরে, আর নতুন কিছু লিখলে redo-stack খালি হয়।

বন্ধনী মেলানো — stack-এর ক্লাসিক সমস্যা

{[()]} ঠিক আছে, ([)] ভুল — কীভাবে যাচাই করবেন? নিয়মটা হলো: যে বন্ধনী সবশেষে খোলা হয়েছে, সেটাকেই সবার আগে বন্ধ করতে হবে। “সবশেষে এসেছে, সবার আগে যাবে” — হুবহু LIFO. খোলা বন্ধনী পেলে push; বন্ধ বন্ধনী পেলে pop করে মেলান। Compiler আর IDE আপনার কোডের বন্ধনী এভাবেই মেলায়। "{[()]}("-এর ওপর ধাপে ধাপে:

1for (char c : s.toCharArray())2    if (খোলা) stack.push(c);3    else if (stack.isEmpty()) return false;4    else if (pop() জোড়া নয়) return false;5return stack.isEmpty();

এবার চালিয়ে দেখুন — একই ArrayDeque class দিয়ে একটি টোকেন কাউন্টার (queue) আর বন্ধনী যাচাই (stack):

import java.util.*;

class Main {
    static boolean balanced(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        Map<Character, Character> pair = Map.of(')', '(', ']', '[', '}', '{');
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') stack.push(c);
            else if (pair.containsKey(c)) {
                if (stack.isEmpty()) return false;       // খোলার আগেই বন্ধ
                char open = stack.pop();
                if (open != pair.get(c)) return false;   // জোড়া মেলেনি
            }
        }
        return stack.isEmpty();                          // খোলা কিছু বাকি?
    }
    public static void main(String[] args) {
        Deque<String> counter = new ArrayDeque<>();      // টোকেন কাউন্টার — FIFO
        counter.offer("T-101"); counter.offer("T-102"); counter.offer("T-103");
        System.out.println("ডাক: " + counter.poll() + ", লাইনে বাকি " + counter);
        System.out.println("পরের জন: " + counter.peek());
        for (String s : new String[]{"{[()]}", "{[()]}(", "([)]", "())"})
            System.out.println(s + " -> " + balanced(s));
    }
}

৫ · java.util.Stack — কেন আর ব্যবহার করবেন না

Java-তে Stack নামে একটি class আছে ১৯৯৬ সাল থেকে, আর নাম দেখে সেটাই প্রথমে মনে আসে। সমস্যা হলো এর জন্ম: Stack হলো Vector-এর subclass. পর্ব ১৯-এ inheritance শেখার সময় যে সাবধানবাণী শুনেছিলেন — “is-a সত্যি না হলে extends নয়” — এটা তার পাঠ্যপুস্তকীয় উদাহরণ। একটি stack কি সত্যিই একটি vector (যেকোনো index-এ পড়া-লেখা যায় এমন তালিকা)? না। কিন্তু extends করায় Vector-এর সব public method Stack-এ চলে এসেছে:

Stack<Integer> st = new Stack<>();
st.push(1); st.push(2); st.push(3);
System.out.println(st + " peek=" + st.peek());       // [1, 2, 3] peek=3

st.add(0, 99);                                       // নিচে ঢুকিয়ে দেওয়া!
System.out.println(st + " get(1)=" + st.get(1));     // [99, 1, 2, 3] get(1)=1

Deque<Integer> ds = new ArrayDeque<>();
ds.push(1); ds.push(2); ds.push(3);
System.out.println(ds + " peek=" + ds.peek());       // [3, 2, 1] peek=3

মন্তব্যে লেখা আউটপুটগুলো চালিয়ে যাচাই করা। তিনটি সমস্যা দেখা যাচ্ছে:

1. LIFO নিয়ম ভাঙা যায়। add(0, 99) stack-এর একদম নিচে একটি জিনিস ঢুকিয়ে দিল, get(1) মাঝখান থেকে পড়ল। Stack-এর পুরো অর্থই হলো “শুধু ওপর দিয়ে” — সেই নিশ্চয়তা নেই। পর্ব ১৭-এর encapsulation-এর ভাষায়, ভেতরের গঠন বাইরে খুলে রাখা।
2. ছাপা ও লুপের ক্রম উল্টো। একই তিনটি push-এর পর Stack দেখায় [1, 2, 3] (নিচ থেকে ওপর), ArrayDeque দেখায় [3, 2, 1] (ওপর থেকে নিচ)। for-each লুপেও একই পার্থক্য। Stack থেকে Deque-এ কোড সরানোর সময় এটা নীরব bug-এর উৎস।
3. অকারণ synchronized. Vector-এর প্রায় সব method synchronized — একসাথে একাধিক thread যাতে না ঢোকে, তার জন্য প্রতিটি ডাকে একটি তালা (lock) নেওয়া হয়। এক thread-এর প্রোগ্রামে এটা শুধু খরচ। আর অনেক thread-এর জন্যও এটা যথেষ্ট নয়: “খালি কি না দেখে তারপর pop” — দুটি আলাদা ডাকের মাঝে অন্য thread ঢুকে পড়তে পারে। Thread-এর সমস্যা আর তার আসল সমাধান পর্ব ৪০-এ।

Java-র নিজের documentation-ও স্পষ্ট: Stack-এর পাতায় লেখা, “A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class.” Stack মুছে ফেলা হয়নি শুধু পুরোনো কোডের সামঞ্জস্যের জন্য। খালি Stack-এ pop() ছোড়ে আলাদা একটি exception, java.util.EmptyStackException — Deque-এর NoSuchElementException নয়। এটাও পুরোনো যুগের চিহ্ন।

৬ · PriorityQueue — সবচেয়ে জরুরি জন আগে, binary heap দিয়ে

জরুরি বিভাগের সমস্যায় ফিরি। প্রতিবার “সবচেয়ে গুরুতর রোগী কে” জানতে হবে, আর নতুন রোগী যেকোনো সময় আসতে পারেন। দুটি সহজ উপায় আর তাদের দাম:

• এলোমেলো তালিকা রাখুন: ঢোকানো O(1), কিন্তু প্রতিবার সবচেয়ে জরুরিকে খুঁজতে পুরো তালিকা দেখা — O(n).
• সবসময় সাজানো তালিকা রাখুন: বের করা O(1), কিন্তু প্রতিটি নতুন রোগীকে সঠিক জায়গায় বসাতে বাকিদের সরানো — O(n).

মাঝামাঝি একটি চমৎকার কাঠামো আছে, যা দুটি কাজই O(log n)-এ করে: binary heap. PriorityQueue ভেতরে এটাই। Heap হলো একটি গাছ (tree), যার দুটি নিয়ম:

1. আকৃতির নিয়ম: প্রতিটি স্তর বাঁ থেকে ডানে পুরো ভরা থাকে, শুধু শেষ স্তর আংশিক হতে পারে। তাই গাছটিকে কোনো pointer ছাড়াই একটি array-তে রাখা যায়: ঘর i-এর সন্তান 2i+1 আর 2i+2, আর অভিভাবক (i-1)/2.
2. ক্রমের নিয়ম: প্রতিটি অভিভাবক তার সন্তানদের চেয়ে ছোট বা সমান। ফলে সবচেয়ে ছোট জিনিস সবসময় শিকড়ে (root), অর্থাৎ ঘর ০-তে। এমন heap-কে বলে min-heap.

খেয়াল করুন, নিয়মটা শুধু অভিভাবক আর সন্তানের মধ্যে — দুই ভাইবোনের মধ্যে, বা গাছের বাঁ আর ডান অংশের মধ্যে কোনো ক্রম নেই। তাই heap “আংশিক সাজানো”: সবচেয়ে ছোটটা নিশ্চিতভাবে জানা, বাকিরা মোটামুটি এলোমেলো। ৮, ৫, ৩, ৯, ১ ঢুকিয়ে, তারপর একটি poll করে দেখুন — প্রতিটি ধাপের array চালিয়ে যাচাই করা:

    8          5 এল ঘর ১-এ, অভিভাবক 8
   /           5 < 8 → অদলবদল
  5                  5
                    /
                   8
array: [5, 8]

    5             3 এল ঘর ২-এ, অভিভাবক ঘর ০ (5)
   / \            3 < 5 → অদলবদল
  8   3                3
                      / \
                     8   5
array: [3, 8, 5]

      3           9 এল ঘর ৩-এ, অভিভাবক ঘর ১ (8)
     / \          9 > 8 → যেখানে আছে সেখানেই
    8   5
   /
  9
array: [3, 8, 5, 9]

      3             1 এল ঘর ৪-এ, অভিভাবক 8 → অদলবদল
     / \            এবার অভিভাবক 3 → আবার অদলবদল
    8   5                 1
   / \                   / \
  9   1                 3   5
                       / \
                      9   8
array: [1, 3, 5, 9, 8]

poll() ফেরত দেবে 1
শেষ ঘরের 8 উঠে এল শিকড়ে:
      8
     / \
    3   5
   /
  9
ক্রমের নিয়ম ভাঙা — 8 তার সন্তানদের চেয়ে বড়

8-এর সন্তান 3 আর 5 — ছোটটি 3 → অদলবদল
      3
     / \
    8   5
   /
  9
8-এর সন্তান এখন শুধু 9 → 8 < 9, থামো
array: [3, 8, 5, 9]

এখানে O(log n), O(n) — এই চিহ্নগুলো বলে তালিকা বড় হলে কাজের সময় কীভাবে বাড়ে; পর্ব ৫৪-এ অ্যালগরিদম বিশ্লেষণে এর বিস্তারিত।

ক্রম কে ঠিক করে — natural ordering বনাম Comparator

কিছু না বললে PriorityQueue জিনিসগুলোর natural ordering ব্যবহার করে — সংখ্যায় ছোট থেকে বড়, String-এ অভিধানের ক্রম। অর্থাৎ ডিফল্ট হলো min-heap: poll সবচেয়ে ছোটটি দেয়। সবচেয়ে বড়টি আগে চাইলে (max-heap) constructor-এ একটি Comparator দিন: new PriorityQueue<Integer>(Comparator.reverseOrder()). Comparator কীভাবে লেখে আর জোড়া দেয়, পুরো ছবি পর্ব ৩৩-এ।

নিজের তৈরি টাইপ — যেমন একটি Patient record — রাখতে চাইলে সাবধান। Record নিজে থেকে Comparable নয়, আর Comparator না দিলে প্রথম offer-এই প্রোগ্রাম ভাঙে:

import java.util.PriorityQueue;

record Patient(String name, int level) { }

class Main {
    public static void main(String[] args) {
        PriorityQueue<Patient> er = new PriorityQueue<>();
        er.offer(new Patient("Karim", 3));
    }
}

Exception in thread "main" java.lang.ClassCastException: class Patient cannot be cast to class java.lang.Comparable (Patient is in unnamed module of loader 'app'; java.lang.Comparable is in module java.base of loader 'bootstrap')
	at java.base/java.util.PriorityQueue.siftUpComparable(PriorityQueue.java:643)
	at java.base/java.util.PriorityQueue.siftUp(PriorityQueue.java:639)
	at java.base/java.util.PriorityQueue.offer(PriorityQueue.java:330)
	at Main.main(Main.java:8)

Code compile হলো, কারণ PriorityQueue<E>-এর type parameter-এ কোনো bound নেই (পর্ব ২৮) — Comparator দিলে যেকোনো টাইপই চলে, তাই compiler আগে থেকে আপত্তি করতে পারে না। চলার সময় Comparator না পেয়ে PriorityQueue জিনিসটিকে Comparable-এ cast করতে চেষ্টা করে, আর stack trace-এ সেই siftUpComparable দেখা যাচ্ছে। একটিমাত্র রোগী রাখতেও এটা ঘটে। সমাধান: Comparator দিন, অথবা record-কে Comparable<Patient> বানান।

সবচেয়ে বড় ফাঁদ — ছাপা বা লুপ চালালে সাজানো ক্রম নয়

৫, ১, ৪, ২, ৩ একটি PriorityQueue-এ offer করে System.out.println(pq) চালালে আসে [1, 2, 4, 5, 3]. for-each লুপ চালালেও ঠিক এই ক্রম। কিন্তু খালি না হওয়া পর্যন্ত বারবার poll() করলে আসে 1 2 3 4 5. তিনটিই চালিয়ে যাচাই করা।

কারণ toString() আর iterator শুধু ভেতরের array-টি ঘর ০ থেকে শেষ পর্যন্ত পড়ে — আর সেটা heap-এর ক্রম, সাজানো ক্রম নয়। একই offer-এর ক্রমে ফল প্রতিবার একই হয় (এলোমেলো নয়), কিন্তু সাজানো দেখালে সেটা কাকতালীয়। Java-র documentation সতর্ক করে যে PriorityQueue-এর iterator কোনো নির্দিষ্ট ক্রমের নিশ্চয়তা দেয় না, আর সাজানো ক্রমে হাঁটতে চাইলে Arrays.sort(pq.toArray()) ভাবতে বলে। নিয়ম মনে রাখুন: PriorityQueue থেকে সাজানো ক্রম পাওয়ার একমাত্র উপায় poll.

আরেকটি সূক্ষ্ম বিষয়: সমান priority-র দুজনের মধ্যে কে আগে আসবে, PriorityQueue তার নিশ্চয়তা দেয় না — যে আগে এসেছে সে আগে যাবে, এমন কোনো কথা নেই (heap “stable” নয়)। নির্দিষ্ট ক্রম চাইলে Comparator-এ দ্বিতীয় একটি মানদণ্ড যোগ করুন — নাম, বা আসার ক্রমিক নম্বর।

জরুরি বিভাগ আর শীর্ষ ৩ — একসাথে চালিয়ে দেখুন

নিচের প্রোগ্রামে দুটি ব্যবহার: জরুরি বিভাগের রোগী (level ১ সবচেয়ে জরুরি, সমান হলে নামের ক্রম), আর পরীক্ষার নম্বর থেকে শীর্ষ তিনজন বের করা। দ্বিতীয়টি একটি বিখ্যাত কৌশল — top-K: সবচেয়ে বড় K-টি চাইলে আকার K-এর একটি min-heap রাখুন। প্রতিটি নতুন সংখ্যা ঢোকান; আকার K ছাড়ালে সবচেয়ে ছোটটি (শিকড়) ফেলে দিন। শেষে heap-এ থাকে সবচেয়ে বড় K-টি।

import java.util.*;

record Patient(String name, int level) { }      // level 1 = সবচেয়ে জরুরি

class Main {
    public static void main(String[] args) {
        PriorityQueue<Patient> er = new PriorityQueue<>(
            Comparator.comparingInt(Patient::level).thenComparing(Patient::name));
        er.offer(new Patient("Karim", 3));
        er.offer(new Patient("Nusrat", 1));
        er.offer(new Patient("Rahim", 2));
        er.offer(new Patient("Ayesha", 1));
        while (!er.isEmpty()) System.out.println(er.poll());
        int[] scores = {72, 95, 61, 88, 79, 99, 54};
        PriorityQueue<Integer> top = new PriorityQueue<>();   // min-heap
        for (int s : scores) {
            top.offer(s);
            if (top.size() > 3) top.poll();                   // সবচেয়ে ছোটটি বাদ
        }
        System.out.println("heap-এর ভেতরের ক্রম: " + top);
        List<Integer> best = new ArrayList<>(top);
        best.sort(Comparator.reverseOrder());
        System.out.println("শীর্ষ ৩: " + best);
    }
}

৭ · ক্লাসিক অ্যালগরিদম — BFS, sliding window আর কাজের সূচি

BFS — গোলকধাঁধায় সবচেয়ে ছোট পথ

একটি গ্রিড ভাবুন: S থেকে G-তে যেতে হবে, # দেয়াল, প্রতি ধাপে ওপর-নিচ-ডান-বাঁ এক ঘর। সবচেয়ে কম ধাপ কত? BFS (Breadth-First Search) এর উত্তর দেয় একটি queue দিয়ে: শুরুর ঘর queue-তে রাখুন; তারপর বারবার সামনের ঘর বের করুন আর তার যে প্রতিবেশীদের এখনো দেখা হয়নি, তাদের দূরত্ব “আমার দূরত্ব + ১” লিখে queue-এর পেছনে রাখুন। FIFO-র কারণে দূরত্ব ১-এর সব ঘর দূরত্ব ২-এর আগে বের হয়, দূরত্ব ২-এর সব ঘর দূরত্ব ৩-এর আগে — পুকুরে ঢিল ছুড়লে যেমন ঢেউ স্তরে স্তরে ছড়ায়। তাই কোনো ঘরে প্রথমবার পৌঁছানো মানেই সবচেয়ে ছোট পথে পৌঁছানো।

0 . # .
. # . .
. . . #
# . . G
queue: [(0,0)]

0 1 # .
1 # . .
. . . #
# . . G
queue: [(1,0), (0,1)]

0 1 # .
1 # . .
2 3 . #
# . . G
(0,1)-এর ডানে-নিচে দেয়াল — সেখান থেকে কেউ যোগ হলো না
queue: [(2,1)]

0 1 # .
1 # . .
2 3 4 #
# 4 . G
queue: [(3,1), (2,2)]

0 1 # .
1 # 5 .
2 3 4 #
# 4 5 G
(3,2)-তে দুই দিক থেকেই পৌঁছানো যায়,
কিন্তু প্রথমবারই দূরত্ব লেখা হয় — দ্বিতীয়বার বাদ
queue: [(3,2), (1,2)]

0 1 # .
1 # 5 6
2 3 4 #
# 4 5 6
G পর্যন্ত সবচেয়ে ছোট পথ = 6 ধাপ

কোডের মূল অংশ (একটি record Cell(int r, int c) ধরে নিয়ে):

Deque<Cell> q = new ArrayDeque<>();
q.offer(start);
dist[start.r()][start.c()] = 0;                // বাকি সব ঘরে -1 (দেখা হয়নি)
while (!q.isEmpty()) {
    Cell cur = q.poll();
    if (cur.equals(goal)) return dist[cur.r()][cur.c()];
    for (int[] d : dirs) {                     // ওপর, নিচ, বাঁ, ডান
        int nr = cur.r() + d[0], nc = cur.c() + d[1];
        if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;
        if (g[nr][nc] == '#' || dist[nr][nc] != -1) continue;
        dist[nr][nc] = dist[cur.r()][cur.c()] + 1;
        q.offer(new Cell(nr, nc));
    }
}
return -1;                                     // পৌঁছানো যায় না

একই কৌশল সামাজিক নেটওয়ার্কে “কয়জন বন্ধুর মাধ্যমে পরিচয়”, মেট্রো রুটে সবচেয়ে কম স্টেশন বদল, বা ওয়েব crawler-এ লিংক ধরে ধরে পাতা খোঁজায় কাজে লাগে। Graph আর BFS-এর পুরো রূপ (আর queue-এর বদলে stack দিলে যে DFS হয়) পর্ব ৫৪-এ।

Sliding window — Deque-এর দুই মাথাই কাজে

একটি সংখ্যার তালিকায় প্রতিটি পরপর K-টি সংখ্যার “জানালা”-র সর্বোচ্চ মান চাই — যেমন প্রতি ৩ দিনের সর্বোচ্চ তাপমাত্রা। প্রতিটি জানালায় নতুন করে খুঁজলে O(n·K). একটি Deque দিয়ে O(n)-এ হয়: Deque-এ index রাখুন এমনভাবে যে তাদের মান সামনে থেকে পেছনে কমতে থাকে। নতুন সংখ্যা এলে পেছন থেকে তার চেয়ে ছোটদের ফেলে দিন (তারা আর কখনো সর্বোচ্চ হবে না), আর সামনের index জানালার বাইরে চলে গেলে সামনে থেকে ফেলুন। জানালার সর্বোচ্চ সবসময় সামনে।

Deque<Integer> dq = new ArrayDeque<>();       // index, মান কমতে থাকা ক্রমে
for (int i = 0; i < a.length; i++) {
    if (!dq.isEmpty() && dq.peekFirst() <= i - k) dq.pollFirst();     // জানালার বাইরে
    while (!dq.isEmpty() && a[dq.peekLast()] <= a[i]) dq.pollLast();  // অকেজো ছোটরা
    dq.offerLast(i);
    if (i >= k - 1) result.add(a[dq.peekFirst()]);
}

a = {3, 1, 4, 1, 5, 9, 2, 6}, k = 3 হলে result হয় [4, 4, 5, 9, 9, 9] (চালিয়ে যাচাই করা)। প্রতিটি index Deque-এ একবার ঢোকে আর একবারই বের হয়, তাই মোট কাজ O(n). এটা ইন্টারভিউর জনপ্রিয় প্রশ্ন; বিস্তারিত অনুশীলন পর্ব ৫৯-এ।

Priority অনুযায়ী কাজের সূচি

সার্ভারে রাতের কাজগুলো ভাবুন: ডেটাবেস ব্যাকআপ, রিপোর্ট পাঠানো, পুরোনো লগ মোছা। প্রতিটি কাজের একটি priority আর আসার সময় আছে। একটি PriorityQueue<Task>, যার Comparator আগে priority আর তারপর আসার ক্রমিক নম্বর দেখে — এটাই একটি ছোট task scheduler-এর হৃদয়। একই ধারণায় Java-র ScheduledThreadPoolExecutor ভেতরে “কোন কাজের সময় সবার আগে আসবে” সেই ক্রমে কাজ রাখে (একটি heap-ভিত্তিক queue-তে) — পর্ব ৪১-এ এর ব্যবহার দেখবেন।

এক নজরে: BlockingQueue আর producer-consumer

এ পর্যন্ত সব queue এক thread-এর জন্য। বাস্তবে প্রায়ই একদল thread কাজ তৈরি করে (যেমন ওয়েব থেকে আসা অর্ডার) আর আরেকদল সেগুলো সামলায় — এই নকশার নাম producer-consumer. মাঝখানের লাইনটি হতে হবে thread-safe, আর খালি থাকলে consumer-কে অপেক্ষা করাতে হবে, ভরা থাকলে producer-কে। java.util.concurrent-এর BlockingQueue (Java 5 থেকে) ঠিক এটাই দেয়: Queue-এর দুই পরিবারের সাথে তৃতীয় একটি — put (জায়গা না হওয়া পর্যন্ত অপেক্ষা) আর take (কিছু না আসা পর্যন্ত অপেক্ষা)। ArrayBlockingQueue, LinkedBlockingQueue, PriorityBlockingQueue এর বাস্তবায়ন। Thread কী, আর কেন সাধারণ ArrayDeque দুই thread-এর মাঝে রাখা বিপজ্জনক, সেটা পর্ব ৪০-এ; BlockingQueue দিয়ে আসল producer-consumer পর্ব ৪১-এ।

৮ · কোনটা কখন — সিদ্ধান্তের টেবিল

৯ · AI-এর যুগে — Stack, LinkedList আর “সাজানো” PriorityQueue

Queue আর stack-এর কোড AI খুব দ্রুত লেখে, আর প্রায়ই কাজও করে — ছোট পরীক্ষায়। সমস্যাগুলো লুকিয়ে থাকে পুরোনো অভ্যাসে, আর একটি ভুল ধারণায়: “PriorityQueue মানে সাজানো তালিকা।” নিচের কোডটি AI-এর সাধারণ ধাঁচের — compile হয়, প্রথম দেখায় ঠিকও মনে হয়:

Stack<String> history = new Stack<>();                 // ১
Queue<String> jobs = new LinkedList<>();               // ২
PriorityQueue<Integer> pq = new PriorityQueue<>(List.of(5, 1, 4, 2, 3));
for (int x : pq) System.out.print(x + " ");            // ৩ — "সাজানো" আশা
jobs.offer(next);
String j = jobs.remove();                              // ৪ — offer-এর সাথে remove

চারটি সমস্যা: (১) পুরোনো Stack, (২) queue হিসেবে LinkedList, (৩) PriorityQueue-এর ওপর লুপ — এটা heap-এর ক্রম ছাপে, সাজানো নয় (৫টি সংখ্যায় দেখতে প্রায় ঠিক লাগে বলে পরীক্ষায় ধরা পড়ে না), (৪) একই queue-তে null-পরিবার দিয়ে ঢোকানো আর exception-পরিবার দিয়ে বের করা — খালি হওয়ার পরিস্থিতি কেউ ভাবেনি।

AI-এর queue কোড হাতে পেলে — যাচাইয়ের চেকলিস্ট

• কোথাও Stack, Vector নেই; stack মানে Deque + ArrayDeque
• queue-এর ভ্যারিয়েবল টাইপ Queue/Deque, বাস্তবায়ন ArrayDeque (বা যুক্তিসহ অন্য কিছু)
• প্রতিটি queue-তে একটিই method-পরিবার, আর খালি অবস্থার আচরণ আমি জানি
• PriorityQueue-এর ওপর কোনো for-each/toString-এর ওপর সাজানো ক্রমের ভরসা নেই
• Comparator-এর দিক (min না max) আর tie-breaker নিজে একটি ছোট উদাহরণে যাচাই করেছি
• খালি queue আর একটিমাত্র জিনিস — এই দুই প্রান্তিক অবস্থায় চালিয়ে দেখেছি