इस लेख में हम एक प्राथमिकता कतार, जावा वर्ग सीखते हैं, जो कतार इंटरफ़ेस को लागू करता है। प्रोग्रामर नियमित क्यू इंटरफ़ेस के बारे में क्या जानता है? सबसे पहले, यह इंटरफ़ेस फीफो सिद्धांत या "पहले अंदर पहले बाहर" पर आधारित है। यह एक नियमित कतार को उसके सामान्य अर्थ में याद दिलाता है। आप मैकड्राइव से कॉफी प्राप्त करना चाहते हैं? अगर आपकी कार सबसे पहले खिड़की के पास है, तो आपको अपनी कॉफी अगले ड्राइवर पार्टनर से पहले मिल जाएगी।
प्राथमिकता कतार क्या है? सबसे पहले यह एक वर्ग है जो पीछे से तत्व डालने और सिर से तत्व को हटाने के मामले में कतार इंटरफ़ेस लागू करता है। हालाँकि यह अंदर की सामान्य कतार नहीं है। जावा प्राथमिकता कतार तत्वों का क्रम तत्वों की प्राथमिकता पर निर्भर करता है। सर्वोच्च प्राथमिकता वाले तत्व को कतार के शीर्ष पर ले जाया जाएगा। यदि आप उच्चतम रैंक वाले तत्व को हटाते हैं (सेवा करते हैं), तो दूसरा अपनी कॉफी लेने के लिए सिर पर चढ़ जाता है। प्राथमिकता कैसे निर्धारित की जाती है? प्रलेखन के अनुसार, प्राथमिकता कतार के तत्वों को उनके प्राकृतिक क्रम के अनुसार, या कतार निर्माण के समय प्रदान किए गए एक तुलनित्र द्वारा क्रमबद्ध किया जाता है, जिसके आधार पर निर्माणकर्ता का उपयोग किया जाता है। प्राथमिकता कतार प्राथमिकता न्यूनतम ढेर पर आधारित है। इसका मतलब है, संख्या कतार तत्वों के मामले में, कतार का पहला तत्व इन संख्याओं में से न्यूनतम होगा। बहुत बार इस परिभाषा को पढ़ने के बाद नौसिखिए छात्र यह सोचने लगते हैं कि प्राथमिकता कतार एक रेखीय अर्थ में क्रमबद्ध है। यही है, अगर, कहते हैं, हम एक कतार का उपयोग करते हैं जिसके तत्व प्राकृतिक संख्याएं हैं, तो पहला तत्व सबसे छोटा और अंतिम सबसे बड़ा होगा। यह पूरी तरह से सच नहीं है। यह समझने के लिए कि प्राथमिकता कतार वास्तव में कैसे काम करती है और यह क्या देती है, आपको यह पता लगाने की आवश्यकता है कि हीप कैसे काम करता है। हम थोड़ी देर बाद एक उदाहरण का उपयोग करके प्राथमिकता कतार की आंतरिक संरचना पर विचार करेंगे। अब आइए इसके बाहरी गुणों पर ध्यान दें। तब पहला तत्व सबसे छोटा होगा, और अंतिम सबसे बड़ा होगा। यह पूरी तरह से सच नहीं है। यह समझने के लिए कि प्राथमिकता कतार वास्तव में कैसे काम करती है और यह क्या देती है, आपको यह पता लगाने की आवश्यकता है कि हीप कैसे काम करता है। हम थोड़ी देर बाद एक उदाहरण का उपयोग करके प्राथमिकता कतार की आंतरिक संरचना पर विचार करेंगे। अब आइए इसके बाहरी गुणों पर ध्यान दें। तब पहला तत्व सबसे छोटा होगा, और अंतिम सबसे बड़ा होगा। यह पूरी तरह से सच नहीं है। यह समझने के लिए कि प्राथमिकता कतार वास्तव में कैसे काम करती है और यह क्या देती है, आपको यह पता लगाने की आवश्यकता है कि हीप कैसे काम करता है। हम थोड़ी देर बाद एक उदाहरण का उपयोग करके प्राथमिकता कतार की आंतरिक संरचना पर विचार करेंगे। अब आइए इसके बाहरी गुणों पर ध्यान दें।
हटाने की प्रक्रिया एक जड़ से शुरू होती है, और यह रिवर्स प्रक्रियाओं को भड़काती है। इसलिए, पहले हमारे पास रूट के रूप में 1 है, फिर 2, 3, 4 और अंत में 5 है। इसीलिए रिमूविंग ऑपरेशन पोल () का उपयोग कर रहे हैं
कतार इंटरफ़ेस घोषणा
public interface Queue<E> extends Collection<E>
प्राथमिकता कतार क्या है

प्राथमिकता कतार वर्ग निर्माता और घोषणा
प्राथमिकता कतार वर्ग जावा में प्राथमिकता कतार बनाने के 6 अलग-अलग तरीके प्रदान करता है।- प्रायोरिटीक्यू () - डिफ़ॉल्ट प्रारंभिक क्षमता (11) के साथ खाली कतार जो इसके तत्वों को उनके प्राकृतिक क्रम के अनुसार व्यवस्थित करती है।
- प्रायोरिटीक्यू (संग्रह सी) - खाली कतार जिसमें निर्दिष्ट संग्रह में तत्व होते हैं।
- प्रायोरिटी क्यू (इंट इनिशियल कैपेसिटी) - निर्दिष्ट प्रारंभिक क्षमता के साथ खाली कतार जो इसके तत्वों को उनके प्राकृतिक क्रम के अनुसार व्यवस्थित करती है।
- प्रायोरिटीक्यू (इंट इनिशियलकैपेसिटी, तुलनित्र तुलनित्र) - निर्दिष्ट प्रारंभिक क्षमता के साथ खाली कतार जो निर्दिष्ट तुलनित्र के अनुसार अपने तत्वों को व्यवस्थित करती है।
- प्राथमिकता कतार(प्राथमिकता कतार सी) - निर्दिष्ट प्राथमिकता कतार में तत्वों से युक्त खाली कतार।
- प्रायोरिटीक्यू (सॉर्टेडसेट सी) - खाली कतार जिसमें निर्दिष्ट सॉर्ट किए गए सेट में तत्व होते हैं।
public class PriorityQueue<E> extends AbstractQueue<E> implements Serializable
प्राथमिकता कतार बनाना
आइए पूर्णांकों की एक प्राथमिकता कतार बनाएँ। प्राथमिकता कतार कार्यान्वयन, जावा कोड:
PriorityQueue<Integer> numbers = new PriorityQueue<>();
हमने तर्क के बिना प्राथमिकता कतार बनाई है। इस मामले में, प्राथमिकता कतार का प्रमुख कतार की न्यूनतम संख्या है। यदि आप सिर को हटाते हैं, तो अगला सबसे छोटा तत्व इस स्थान पर आ जाएगा। तो आप कतार से तत्वों को आरोही क्रम में हटा सकते हैं। यदि आवश्यक हो तो आप तुलनित्र इंटरफ़ेस का उपयोग करके आदेश देने के सिद्धांत को बदल सकते हैं।
जावा प्रायोरिटी क्यू के तरीके
प्रायोरिटीक्यू जावा क्लास में तत्वों को जोड़ने, हटाने और जांचने के महत्वपूर्ण तरीके हैं।तत्वों को प्राथमिकता कतार में डालें
- बूलियन ऐड (ऑब्जेक्ट) निर्दिष्ट तत्व को प्राथमिकता कतार में सम्मिलित करता है। सफलता के मामले में सच हो जाता है। यदि कतार भरी हुई है, तो विधि एक अपवाद को फेंक देती है।
- बूलियन प्रस्ताव (ऑब्जेक्ट) निर्दिष्ट तत्व को इस प्राथमिकता कतार में सम्मिलित करता है। यदि कतार भरी हुई है, तो विधि झूठी हो जाती है।
import java.util.PriorityQueue;
import java.util.Queue;
public class Priority2 {
public static void main(String[] args) {
Queue<Integer> priorityQueue1 = new PriorityQueue<>();
for (int i = 5; i > 0; i--) {
priorityQueue1.add(i);
}
System.out.println(priorityQueue1);
priorityQueue1.offer(0);
System.out.println(priorityQueue1);
}
}
आउटपुट है:
[1, 2, 4, 5, 3]
[0, 2, 1, 5, 3, 4]
तत्वों का क्रम अजीब लगता है, हम इसे बाद में समझाएंगे।
प्राथमिकता कतार से तत्वों को पुनः प्राप्त करना और हटाना
- बूलियन रिमूव (ऑब्जेक्ट) इस कतार से निर्दिष्ट तत्व का एक उदाहरण निकालता है, यदि यह मौजूद है।
- ऑब्जेक्ट पोल () इस कतार के प्रमुख को पुनः प्राप्त करता है और हटाता है। कतार खाली होने पर शून्य वापस आ जाता है।
- शून्य स्पष्ट () प्राथमिकता कतार से सभी तत्वों को हटा देता है।
- ऑब्जेक्ट एलिमेंट () इस कतार के प्रमुख को हटाए बिना प्राप्त करता है। कतार खाली होने पर NoSuchElementException को फेंकता है ।
- ऑब्जेक्ट पीक () कतार के प्रमुख को हटाए बिना पुनर्प्राप्त करता है। कतार खाली होने पर शून्य वापस आ जाता है।
import java.util.PriorityQueue;
import java.util.Queue;
public class Priority2 {
public static void main(String[] args) {
Queue<Integer> priorityQueue = new PriorityQueue<>();
//put 5 elements to the queue using add
for (int i = 5; i > 0; i--) {
priorityQueue.add(i);
}
System.out.println("the head of the queue = " + priorityQueue.peek());
//removing element by element from the queue using poll and print it out
while (!priorityQueue.isEmpty()) {
System.out.println(priorityQueue.poll());
}
//put 5 new elements into the empty queue using offer
for (int i = 10; i > 5; i--) {
priorityQueue.offer(i);
}
System.out.println("now the head of the queue = " + priorityQueue.peek());
System.out.println("the queue before removing 9:");
System.out.println(priorityQueue);
priorityQueue.remove(9);
System.out.println("the queue after removing 9:");
System.out.println(priorityQueue);
//removing all the elements from the queue
priorityQueue.clear();
System.out.println(priorityQueue);
//trying to print out the head of the empty Queue using peek - we'll get null
System.out.println(priorityQueue.peek());
//trying to print out the head of the empty Queue using element - we'll get the exception
System.out.println(priorityQueue.element());
}
}
उत्पादन:
the head of the queue = 1
1
2
3
4
5
now the head of the queue = 6
the queue before removing 9:
[6, 7, 9, 10, 8]
the queue after removing 9:
[6, 7, 8, 10]
[]
null
Exception in thread "main" java.util.NoSuchElementException
at java.base/java.util.AbstractQueue.element(AbstractQueue.java:136)
at Priority2.main(Priority2.java:32)
जैसा कि आप देख सकते हैं, एलिमेंट () विधि का उपयोग करके खाली कतार के सिर को प्रिंट करने का प्रयास करने से NoSuchElementException होता है ।
प्राथमिकता कतार तुलनित्र
- तुलनित्र तुलनित्र () उस तुलनित्र को लौटाता है जो कतार में तत्वों को क्रमबद्ध करता था। यदि कतार को उसके तत्वों के प्राकृतिक क्रम के अनुसार क्रमबद्ध किया जाता है, तो यह शून्य हो जाता है।
जावा प्राथमिकता कतार, तुलनित्र के साथ उदाहरण
हमने उपरोक्त कोड उदाहरणों में प्राकृतिक (आरोही) क्रम का उपयोग किया है, लेकिन कभी-कभी हमें इसे बदलना चाहिए। यहाँ जावा प्राथमिकता कतार उदाहरण है, जहाँ हम अपना आंतरिक तुलनित्र वर्ग बनाते हैं जो तुलनित्र इंटरफ़ेस को लागू करता है। हमारा तुलनित्र तत्वों को सबसे बड़े से छोटे के क्रम में छाँटेगा।
import java.util.PriorityQueue;
import java.util.Comparator;
class Priority3 {
public static void main(String[] args) {
// Creating a priority queue with myComparator
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new MyComparator());
for (int i = 5; i > 0; i--) {
priorityQueue.add(i);
}
System.out.println("the head of Queue = " + priorityQueue.peek());
while (!priorityQueue.isEmpty()) {
System.out.println(priorityQueue.poll());
}
}
}
class MyComparator implements Comparator<Integer> {
@Override
public int compare(Integer number1, Integer number2) {
int value = number1.compareTo(number2);
//sorting elements from maximal to minimal
if (value > 0) {
return -1;
} else if (value < 0) {
return 1;
} else {
return 0;
}
}
}
उत्पादन:
the head of Queue = 5
5
4
3
2
1
कतार का प्रमुख अब न्यूनतम नहीं, बल्कि अधिकतम तत्व है, और क्रम को उलट कर बदल दिया गया था।
इट्रेटर का उपयोग करके प्रायोरिटी क्यू पर इटरेट करना
ProrityQueue संग्रह ढांचे का एक हिस्सा है और Iterable<> इंटरफ़ेस लागू करता है। प्राथमिकता कतार के तत्वों पर पुनरावृति करने के लिए आप iterator() विधि का उपयोग कर सकते हैं। यहाँ एक उदाहरण है:
import java.util.PriorityQueue;
import java.util.Iterator;
import java.util.Queue;
class Priority4 {
public static void main(String[] args) {
// Creating a priority queue
Queue<Integer> priorityQueue = new PriorityQueue<>();
//put 5 elements to the queue using add
for (int i = 5; i > 0; i--) {
priorityQueue.add(i);
}
//Iterating via iterator() method
Iterator<Integer> iterator = priorityQueue.iterator();
while (iterate.hasNext()) {
System.out.print(iterator.next() + " ");
}
}
}
उत्पादन:
1 2 4 5 3
अधिक प्रायोरिटी क्यू विधियाँ
- बूलियन सम्मिलित (ऑब्जेक्ट ओ) सच लौटाता है यदि क्यू में ओ तत्व है।
- int size() इस कतार में तत्वों की संख्या लौटाता है।
- ऑब्जेक्ट [] toArray() इस कतार में सभी तत्वों वाली एक सरणी देता है।
import java.util.PriorityQueue;
import java.util.Queue;
public class Priority5 {
public static void main(String[] args) {
Queue<Integer> priorityQueue = new PriorityQueue<>();
for (int i = 5; i > 0; i--) {
priorityQueue.offer(i);
}
System.out.println("our queue: " + priorityQueue);
System.out.println("Does our queue contain 8? " + priorityQueue.contains(8));
System.out.println("Does queue contain 5? " + priorityQueue.contains(5));
System.out.println("The quantity of queue elements: " + priorityQueue.size());
Object[] myArray = priorityQueue.toArray();
System.out.println("print out our array:");
for (Object name : myArray) {
System.out.println(name);
}
}
}
उत्पादन:
our queue: [1, 2, 4, 5, 3]
Does our queue contain 8? false
Does our queue contain 5? true
The quantity of queue elements: 5
print out our array:
1
2
4
5
3
प्राथमिकता कतार जावा 8 परिभाषा
यदि आप प्राथमिकता कतार जावा 8 दस्तावेज़ खोलते हैं, तो आपको वहां अगली परिभाषा मिलेगी: प्राथमिकता हीप पर आधारित एक असीमित प्राथमिकता कतार। प्राथमिकता कतार के तत्वों को उनके प्राकृतिक क्रम के अनुसार, या कतार निर्माण के समय प्रदान किए गए एक तुलनित्र द्वारा क्रमबद्ध किया जाता है, जिसके आधार पर निर्माणकर्ता का उपयोग किया जाता है। प्राथमिकता कतार अशक्त तत्वों की अनुमति नहीं देती है। प्राकृतिक क्रम पर निर्भर एक प्राथमिकता कतार भी गैर-तुलनीय वस्तुओं को सम्मिलित करने की अनुमति नहीं देती है (ऐसा करने से ClassCastException हो सकती है)। हीप यहाँ एक बहुत ही महत्वपूर्ण शब्द है। यह वरीयता कतार तत्वों के क्रम के गुणों की व्याख्या करता है।प्राथमिकता कतार कार्य का सिद्धांत: बाइनरी हीप
आइए एक उदाहरण से शुरू करते हैं। क्यू इंटरफ़ेस को लागू करने वाले दो ऑब्जेक्ट बनाते हैं। उनमें से एक लिंक्डलिस्ट है, दूसरा - प्रायोरिटी क्यू। इन दोनों में पूर्णांक (1,2,3,4 और 5) के 5 तत्व हैं और हम तत्वों को सबसे बड़ी से छोटी कतार में रखना शुरू करते हैं। तो, पहले 5 आता है, फिर 4, 3, 2 और आखिरी 1 होगा। फिर ऑर्डर देखने के लिए दोनों सूचियों का प्रिंट आउट लें।
Queue<Integer> queueL = new LinkedList<>();
for (int i = 5; i > 0; i--) {
queueL.add(i);
}
System.out.println("LinkedList Queue (FIFO): " + queueL);
Queue<Integer> priorityQueue = new PriorityQueue<>();
for (int i = 5; i > 0; i--) {
priorityQueue.offer(i);
}
System.out.println("PriorityQueue: " + priorityQueue)
इन कोड के काम करने का परिणाम अगला है:
LinkedList Queue (FIFO): [5, 4, 3, 2, 1]
PriorityQueue: [1, 2, 4, 5, 3]
खैर, लिंक्डलिस्ट ऑर्डर अनुमानित और समझने योग्य है। यह फीफो सिद्धांत के अनुसार आदेश दिया गया है। हमने 5 से शुरुआत की थी, इसलिए यह तत्व पहली पंक्ति में है, फिर 4 और इसी तरह आगे बढ़ता है। प्राथमिकता कतार क्रम के बारे में हम क्या बता सकते हैं? डॉक्स ने कहा कि प्राथमिकता कतार के तत्वों को उनके प्राकृतिक क्रम के अनुसार, या कतार निर्माण के समय प्रदान किए गए एक तुलनित्र द्वारा क्रमबद्ध किया जाता है। हालाँकि यह क्रम रैखिक छँटाई अर्थ में "प्राकृतिक" नहीं लगता है। हम [1, 2, 3, 4, 5] की उम्मीद करेंगे, [1, 2, 4, 5, 3] की नहीं। यह समझने के लिए कि पुनर्प्राप्ति का क्रम ऐसा क्यों है, हमें उस प्राथमिकता कतार को ढेर पर आधारित याद करना चाहिए। ढेर क्या है? यह बाइनरी ट्री पर आधारित एक डेटा संरचना है. ढेर की मुख्य संपत्ति: प्रत्येक माता-पिता की प्राथमिकता उसके बच्चों की प्राथमिकताओं से अधिक होती है। मैं आपको याद दिला दूं कि एक पेड़ को पूर्ण बाइनरी कहा जाता है यदि प्रत्येक माता-पिता के दो से अधिक बच्चे नहीं हैं, और स्तरों को ऊपर से नीचे (समान स्तर से - बाएं से दाएं) भरना है। बाइनरी हीप हर बार खुद को पुनर्गठित करता है जब इसमें तत्व जोड़े या निकाले जाते हैं। मिन-हीप के मामले में, सबसे छोटा तत्व इसके सम्मिलन के क्रम की परवाह किए बिना जड़ में जाता है। प्राथमिकता कतार इस न्यूनतम ढेर पर आधारित है। इसका मतलब है, संख्या कतार तत्वों के मामले में, कतार का पहला तत्व इन संख्याओं में से न्यूनतम होगा। यदि आप रूट को हटाते हैं, तो अगला सबसे छोटा रूट बन जाता है।
आइए हमारे उदाहरण की ओर मुड़ें।
चरण 1. हम '5' को प्राथमिकता कतार में रखते हैं। जड़ बन जाता है। चरण 2. हम प्राथमिकता कतार में '4' जोड़ते हैं। 4 <5, इसलिए नया तत्व पुराने से अधिक होना चाहिए। 4 एक जड़ बन जाता है, 5 उसका बायाँ बच्चा है। अब जावा में डेटा संरचना [4, 5] चरण 3 है । हम '3' जोड़ते हैं। अस्थायी रूप से यह जड़ का सही सन्तान बन जाता है (4)। हालाँकि, 3 <4, इसलिए हमें इसे ऊपर उठाना चाहिए। एक्सचेंज 3 और 4। अब हमारे पास एक संरचना है जैसे [3, 5, 4] चरण 4। हम '2' जोड़ते हैं। यह 5. 2<5 का बायां बच्चा बन जाता है, इसलिए उन्हें एक्सचेंज करें। 2 3, 2 <3 का बायां बच्चा बन जाता है, इसलिए एक और विनिमय प्रक्रिया। अब हमारे पास एक संरचना है [2,3,4,5] चरण 5।हम '1' जोड़ते हैं। यह 3 के दाहिने बच्चे से 2 के बाएं बच्चे तक आता है, और फिर जड़ तक जाता है। परिणाम डेटा संरचना: [1,2,4,5,3]
while (!priorityQueue.isEmpty()) {
System.out.println(priorityQueue.poll());
}
हमें लीनियर सेंस आउटपुट में "सॉर्ट" मिला है:
1
2
3
4
5
तो कुछ कार्यों के लिए प्राथमिकता कतार प्रभावी हो सकती है। प्रत्येक तत्व को सम्मिलित करने और हटाने में O(log N) समय लगता है, और आप O(1) में न्यूनतम तत्व प्राप्त कर सकते हैं। यहाँ पूरा उदाहरण है:
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
public class PriorityQueueExample {
public static void main(String[] args) {
Queue<Integer> queueL = new LinkedList<>();
for (int i = 5; i > 0; i--) {
queueL.add(i);
}
System.out.println("Print our LinkedList Queue (FIFO): " + queueL);
Queue<Integer> priorityQueue = new PriorityQueue<>();
for (int i = 5; i > 0; i--) {
priorityQueue.offer(i);
}
System.out.println("PriorityQueue printing (by iterating, no elements removing): " + priorityQueue);
System.out.println("Print PriorityQueue using poll() (by retrieval): " );
while (!priorityQueue.isEmpty()) {
System.out.println(priorityQueue.poll());
}
}
}
Print our LinkedList Queue (FIFO): [5, 4, 3, 2, 1]
PriorityQueue printing (by iterating, no elements removing): [1, 2, 4, 5, 3]
Print our PriorityQueue using poll() (by retrieval):
1
2
3
4
5
यह समझना महत्वपूर्ण है कि प्राथमिकता कतारें बाइनरी ढेर पर आधारित होती हैं, इसलिए वे तत्वों को रैखिक क्रमबद्ध क्रम में नहीं रखती हैं। जड़ से पत्ते तक हर रास्ते का आदेश दिया गया है, लेकिन जड़ से अलग तरीके नहीं हैं। इसका मतलब है कि आप कतार का न्यूनतम तत्व बहुत जल्दी प्राप्त कर सकते हैं।
प्राथमिकता कतार के बारे में आपको क्या पता होना चाहिए। संक्षिप्त सूची
- प्राथमिकता कतार NULL वस्तुओं की अनुमति नहीं देती है।
- आप प्रायोरिटी क्यू में केवल तुलनीय वस्तुओं को जोड़ सकते हैं।
- प्राथमिकता कतार एक न्यूनतम हीप, एक प्रकार के बाइनरी ट्री के रूप में बनाई गई है। न्यूनतम तत्व जड़ है। प्राथमिकता कतार की वस्तुओं को प्राकृतिक क्रम में डिफ़ॉल्ट रूप से क्रमबद्ध किया जाता है।
- यदि आपको कस्टम ऑर्डरिंग की आवश्यकता है तो आप तुलनित्र का उपयोग कर सकते हैं।
- प्रायोरिटीक्यू थ्रेड सुरक्षित नहीं है, इसलिए आप समवर्ती वातावरण में काम करने के लिए प्रायोरिटीब्लॉकिंगक्यू का बेहतर उपयोग करते हैं।
- प्रायोरिटीक्यू ऐड और पोल विधियों के लिए O(log(n)) समय प्रदान करता है और न्यूनतम तत्व प्राप्त करने के लिए O(1) प्रदान करता है।
GO TO FULL VERSION