Priority Queue এবং Deque (Double-Ended Queue) হল এমন দুটি ডাটা স্ট্রাকচার, যা কিছু বিশেষ ধরনের ডেটা অপারেশন পরিচালনার জন্য ব্যবহৃত হয়। Priority Queue সাধারণত Queue ডাটা স্ট্রাকচারের একটি বিশেষ রূপ যেখানে উপাদানগুলো তাদের প্রাধান্য অনুসারে সাজানো থাকে, এবং Deque হল এমন একটি Queue যা দুই প্রান্ত থেকে উপাদান যোগ বা মুছতে সক্ষম।
এখানে আমরা Priority Queue এবং Deque এর ধারণা, তাদের ব্যবহার, এবং তাদের Java তে কিভাবে ব্যবহার করা যায় তা আলোচনা করব।
1. Priority Queue
Priority Queue হল একটি বিশেষ ধরনের কিউ ডাটা স্ট্রাকচার, যেখানে প্রতিটি উপাদান একটি নির্দিষ্ট প্রাধান্য বা প্রাধান্য মানের ভিত্তিতে রাখা হয়। কিউতে উপাদান যোগ করার সময়, তাদের প্রাধান্য অনুযায়ী তাদের অবস্থান ঠিক করা হয়, এবং সাধারণত min-heap বা max-heap ব্যবহার করে এই প্রাধান্য সিস্টেমটি কার্যকর করা হয়।
1.1. Priority Queue এর বৈশিষ্ট্য
- Priority-based ordering: উপাদানগুলির একটি নির্দিষ্ট প্রাধান্য থাকে এবং কিউতে সর্বোচ্চ বা সর্বনিম্ন প্রাধান্যযুক্ত উপাদান আগে বের করা হয়।
- Min-heap বা Max-heap এর মাধ্যমে এর কার্যকারিতা নিশ্চিত করা হয়। Min-heap ব্যবহার করলে সর্বনিম্ন প্রাধান্য উপাদান বের হবে, আর Max-heap ব্যবহার করলে সর্বোচ্চ প্রাধান্য উপাদান বের হবে।
1.2. Priority Queue এর ব্যবহার
- Task Scheduling: যখন বিভিন্ন টাস্কের জন্য বিভিন্ন প্রাধান্য সেট করা হয়, যেমন অপারেটিং সিস্টেমের স্কেজুলিং বা ব্যাচ প্রসেসিং।
- Dijkstra’s Algorithm: গ্রাফ অ্যালগরিদমে সর্বনিম্ন দূরত্ব খুঁজে বের করার জন্য।
- Huffman Encoding: কম্প্রেশন অ্যালগরিদমে।
1.3. Priority Queue Example in Java
import java.util.PriorityQueue;
public class PriorityQueueExample {
public static void main(String[] args) {
// Create a PriorityQueue
PriorityQueue<Integer> pq = new PriorityQueue<>();
// Adding elements to the priority queue
pq.add(10);
pq.add(5);
pq.add(20);
pq.add(15);
// Printing the priority queue elements (min-heap)
System.out.println("Priority Queue (Min-Heap): ");
while (!pq.isEmpty()) {
System.out.println(pq.poll());
}
}
}
ব্যাখ্যা:
- এখানে, PriorityQueue একটি min-heap হিসাবে কাজ করছে, যেখানে সবচেয়ে কম মানের উপাদান আগে বের হবে।
- poll() মেথড ব্যবহার করা হয়েছে PriorityQueue থেকে উপাদান বের করার জন্য, যা স্বয়ংক্রিয়ভাবে সর্বনিম্ন মানের উপাদান বের করে।
আউটপুট:
Priority Queue (Min-Heap):
5
10
15
20
2. Deque (Double-Ended Queue)
Deque (Double-Ended Queue) একটি ডাটা স্ট্রাকচার যা Queue এর একটি উন্নত সংস্করণ। এতে আপনি Queue এর মতো সাধারণভাবে উপাদান যোগ বা মুছতে পারেন, তবে এই ডাটা স্ট্রাকচারে আপনি দুই প্রান্ত থেকেই (অর্থাৎ front এবং rear) উপাদান যোগ বা মুছতে পারেন। এটি খুবই উপকারী যখন আপনি এমন পরিস্থিতি বা অ্যালগরিদমে কাজ করেন যেখানে দুটি প্রান্তের কাছ থেকে উপাদান হ্যান্ডলিং করতে হয়।
2.1. Deque এর বৈশিষ্ট্য
- Two-ended operation: আপনি Deque এর শুরু এবং শেষে ডাটা যোগ বা মুছতে পারেন।
- FIFO (First-In-First-Out) and LIFO (Last-In-First-Out): এটি Queue এবং Stack উভয়ের বৈশিষ্ট্য ধারণ করে, কারণ আপনি Deque তে উপাদান যোগ এবং মুছতে পারেন যেকোনো প্রান্ত থেকে।
2.2. Deque এর ব্যবহার
- Deque as a Stack: Deque এর মাধ্যমে আপনি Stack তৈরি করতে পারেন, যেখানে উপাদান LIFO পদ্ধতিতে প্রবাহিত হবে।
- Deque as a Queue: আপনি এটি Queue হিসেবেও ব্যবহার করতে পারেন, যেখানে উপাদানগুলি FIFO পদ্ধতিতে প্রবাহিত হবে।
- Sliding Window: এটি এমন পরিস্থিতিতে ব্যবহৃত হয় যেখানে আপনি ডেটার একটি সাবসেটের উপর অপারেশন করছেন এবং সেটি স্লাইডিং উইন্ডোর মতো পরিবর্তিত হচ্ছে।
2.3. Deque Example in Java
import java.util.ArrayDeque;
import java.util.Deque;
public class DequeExample {
public static void main(String[] args) {
// Create a Deque
Deque<Integer> deque = new ArrayDeque<>();
// Adding elements at the front and rear
deque.addFirst(10); // Add 10 at the front
deque.addLast(20); // Add 20 at the rear
deque.addFirst(5); // Add 5 at the front
deque.addLast(25); // Add 25 at the rear
// Printing the deque elements
System.out.println("Deque elements: " + deque);
// Removing elements from the front and rear
deque.removeFirst(); // Remove from front
deque.removeLast(); // Remove from rear
System.out.println("Deque after removal: " + deque);
}
}
ব্যাখ্যা:
- এখানে, ArrayDeque ব্যবহার করা হয়েছে যা Deque এর একটি ইমপ্লেমেন্টেশন।
- addFirst() এবং addLast() মেথডের মাধ্যমে উপাদান যোগ করা হয়েছে, প্রথমে এবং পরে।
- removeFirst() এবং removeLast() মেথডের মাধ্যমে উপাদান সরানো হয়েছে, প্রথম এবং পরে।
আউটপুট:
Deque elements: [5, 10, 20, 25]
Deque after removal: [10, 20]
3. Priority Queue vs Deque
| Feature | Priority Queue | Deque (Double-Ended Queue) |
|---|---|---|
| Access | Accesses elements based on priority (min/max heap) | Accesses elements from both ends (front/rear) |
| Insertion Order | Does not preserve insertion order (based on priority) | Preserves insertion order (FIFO or LIFO depending on use) |
| Usage | Task scheduling, Dijkstra's algorithm, Huffman encoding | Sliding window, deque as stack, deque as queue |
| Operation Complexity | Insertion and removal operations are logarithmic | Insertion and removal from both ends are O(1) |
| Implementation | Uses a heap (min/max) for ordering | Can be implemented using arrays or linked lists |
সারাংশ
- Priority Queue হল একটি বিশেষ ধরনের কিউ যেখানে উপাদানগুলি তাদের প্রাধান্য অনুসারে সাজানো থাকে এবং সবচেয়ে বেশি প্রাধান্যযুক্ত উপাদান দ্রুত বের হয়ে আসে। এটি সাধারণত task scheduling, graph algorithms, এবং compression algorithms তে ব্যবহৃত হয়।
- Deque হল এমন একটি কিউ যা দুটি প্রান্ত থেকে উপাদান যোগ বা মুছতে পারে, অর্থাৎ আপনি FIFO বা LIFO উভয় পদ্ধতি অনুসরণ করতে পারেন। এটি সাধারণত sliding window, queue, এবং stack হিসেবেও ব্যবহৃত হতে পারে।
দুটি ডাটা স্ট্রাকচারই Java তে খুবই কার্যকরী এবং বিভিন্ন পরিস্থিতিতে ব্যবহার করা যেতে পারে। Priority Queue এবং Deque উভয়েই Java Collections Framework এর অংশ, যা ডাটা স্ট্রাকচার এবং অ্যালগরিদম সম্পর্কিত বিভিন্ন সমস্যা সমাধান করতে সহায়ক।
Read more
