सी ++ प्रायोरिटी_क्यू का उपयोग कैसे करें?

How Use C Priority_queue

सी ++ में, एक कतार एक सूची डेटा संरचना है जहां सूची में रखा जाने वाला पहला तत्व हटाया जाने वाला पहला तत्व होता है, जब हटाना होता है। सी ++ में प्राथमिकता कतार समान है, लेकिन इसमें कुछ ऑर्डरिंग है; यह सबसे बड़ा मूल्य वाला तत्व है जिसे पहले हटा दिया जाता है। प्राथमिकता कतार को अभी भी कॉन्फ़िगर किया जा सकता है ताकि यह कम से कम मान वाला तत्व हो जिसे पहले हटा दिया गया हो। किसी भी कतार में कम से कम होना चाहिए धकेलना() समारोह और पॉप () समारोह। NS धकेलना() फ़ंक्शन पीछे एक नया तत्व जोड़ता है। सामान्य कतार के लिए, पॉप () फ़ंक्शन पहले तत्व को हटा देता है जिसे कभी धक्का दिया जाता है। प्राथमिकता कतार के लिए, पॉप () फ़ंक्शन उच्चतम प्राथमिकता वाले तत्व को हटा देता है, जो ऑर्डरिंग स्कीम के आधार पर सबसे बड़ा या छोटा हो सकता है।

सी ++ प्राथमिकता_क्यू का उपयोग करने के लिए, प्रोग्राम को कोड से शुरू होना चाहिए जैसे:







#शामिल
#शामिल
का उपयोग करते हुए नाम स्थानघंटे;

इसमें कार्यक्रम में कतार पुस्तकालय शामिल है।



पढ़ना जारी रखने के लिए, पाठक को C++ का बुनियादी ज्ञान होना चाहिए।



लेख सामग्री

बुनियादी निर्माण

डेटा संरचना का उपयोग करने से पहले उसका निर्माण पहले किया जाना चाहिए। यहां निर्माण का अर्थ है पुस्तकालय के कतार वर्ग से किसी वस्तु को तत्काल करना। कतार वस्तु को तब प्रोग्रामर द्वारा दिया गया एक नाम होना चाहिए। प्राथमिकता कतार बनाने का सबसे सरल सिंटैक्स है:





प्राथमिकता कतार<प्रकार>कतारनाम;

इस सिंटैक्स के साथ, सबसे बड़ा मान पहले हटा दिया जाता है। तात्कालिकता का एक उदाहरण है:

प्राथमिकता कतार<NS>पी क्यू;

या



प्राथमिकता कतार<char>पी क्यू;

सी ++ में वेक्टर और डेक दो डेटा संरचनाएं हैं। उनमें से किसी के साथ प्राथमिकता_क्यू बनाया जा सकता है। वेक्टर संरचना से प्राथमिकता कतार बनाने का सिंटैक्स है:

प्राथमिकता कतार<प्रकार, वेक्टर<इसी प्रकार का>, तुलना करना>पी क्यू;

इस तात्कालिकता का एक उदाहरण है:

प्राथमिकता कतार<NS, वेक्टर<NS>, कम<NS> >पी क्यू;

घोषणा के अंत में > और > के बीच के अंतर पर ध्यान दें। यह भ्रम को रोकने के लिए है >>। डिफ़ॉल्ट तुलना कोड कम है, जिसका अर्थ है सबसे बड़ा, और जरूरी नहीं कि पहला मान, पहले हटा दिया जाएगा। तो, निर्माण कथन को केवल इस प्रकार लिखा जा सकता है:

प्राथमिकता कतार<NS, वेक्टर<NS> >पी क्यू;

यदि कम से कम मान को पहले हटाना है, तो कथन होना चाहिए:

प्राथमिकता कतार<NS, वेक्टर<NS>, ग्रेटर<NS> >पी क्यू;

महत्वपूर्ण सदस्य कार्य

पुश () फ़ंक्शन
यह फ़ंक्शन एक मान को, जो कि इसका तर्क है, प्रायॉरिटी_क्यू में पुश करता है। यह शून्य हो जाता है। निम्नलिखित कोड इसे दिखाता है:

प्राथमिकता कतार<NS>पी क्यू;

पी क्यू।धकेलना(10);
पी क्यू।धकेलना(30);
पी क्यू।धकेलना(बीस);
पी क्यू।धकेलना(पचास);
पी क्यू।धकेलना(40);

इस प्राथमिकता_क्यू को १०, ३०, २०, ५०, ४० के क्रम में ५ पूर्णांक मान प्राप्त हुए हैं। यदि इन सभी तत्वों को प्राथमिकता कतार से बाहर किया जाना है, तो वे ५०, ४०, ३० के क्रम में बाहर आएंगे, 20, 10.

पॉप () फ़ंक्शन
यह फ़ंक्शन प्राथमिकता_क्यू से सर्वोच्च प्राथमिकता वाले मान को हटा देता है। यदि तुलना कोड अधिक है, तो यह सबसे छोटे मान वाले तत्व को हटा देगा। यदि फिर से कॉल किया जाता है, तो यह अगले तत्व को बाकी के सबसे छोटे मान के साथ हटा देता है; फिर से बुलाया जाता है, यह अगले सबसे छोटे मूल्य को हटा देता है, और इसी तरह। यह शून्य हो जाता है। निम्नलिखित कोड इसे दिखाता है:

प्राथमिकता कतार<char, वेक्टर<char>, ग्रेटर<NS> >पी क्यू;
पी क्यू।धकेलना('प्रति');पी क्यू।धकेलना('सी');पी क्यू।धकेलना('बी');पी क्यू।धकेलना('और');पी क्यू।धकेलना('डी');

ध्यान दें कि किसी सदस्य फ़ंक्शन को कॉल करने के लिए, ऑब्जेक्ट के नाम के बाद एक बिंदु और फिर फ़ंक्शन होना चाहिए।

शीर्ष () फ़ंक्शन
NS पॉप () फ़ंक्शन सर्वोच्च प्राथमिकता के अगले मान को हटा देता है, लेकिन इसे वापस नहीं करता है, जैसे पॉप () एक शून्य कार्य है। उपयोग ऊपर() सर्वोच्च प्राथमिकता के मूल्य को जानने के लिए कार्य करें जिसे आगे हटाया जाना है। NS ऊपर() फ़ंक्शन प्राथमिकता_क्यू में सर्वोच्च प्राथमिकता के मान की एक प्रति देता है। निम्नलिखित कोड, जहां सर्वोच्च प्राथमिकता का अगला मूल्य सबसे कम मूल्य है, यह दर्शाता है:

प्राथमिकता कतार<char, वेक्टर<char>, ग्रेटर<NS> >पी क्यू;
पी क्यू।धकेलना('प्रति');पी क्यू।धकेलना('सी');पी क्यू।धकेलना('बी');पी क्यू।धकेलना('और');पी क्यू।धकेलना('डी');
charch1=पी क्यू।ऊपर();पी क्यू।पॉप();
charch2=पी क्यू।ऊपर();पी क्यू।पॉप();
charch3=पी क्यू।ऊपर();पी क्यू।पॉप();
charch4=पी क्यू।ऊपर();पी क्यू।पॉप();
charch5=पी क्यू।ऊपर();पी क्यू।पॉप();

लागत<<ch1<<''<<ch2<<''<<ch3<<''<<ch4<<''<<ch5<<'एन';

आउटपुट 'ए' 'बी' 'सी' 'डी' 'ई' है।

खाली () फ़ंक्शन
यदि कोई प्रोग्रामर का उपयोग करता है ऊपर() एक खाली प्राथमिकता_क्यू पर कार्य, सफल संकलन के बाद, उसे एक त्रुटि संदेश प्राप्त होगा जैसे:

विभाजन दोष(मूल फेंका)

इसलिए, हमेशा जांच लें कि क्या प्राथमिकता कतार का उपयोग करने से पहले खाली नहीं है ऊपर() समारोह। NS खाली() सदस्य फ़ंक्शन एक बूल देता है, यदि कतार खाली है, तो सत्य है, और यदि कतार खाली नहीं है, तो गलत है। निम्नलिखित कोड इसे दिखाता है:

प्राथमिकता कतार<NS>पी क्यू;
NSi1= 10; NSi2= 30; NSi3= बीस; NSi4= पचास; NSi5= 40;
पी क्यू।धकेलना(i1);पी क्यू।धकेलना(i2);पी क्यू।धकेलना(i3);पी क्यू।धकेलना(i4);पी क्यू।धकेलना(i5);

जबकि(!पी क्यू।खाली())
{
लागत <<पी क्यू।ऊपर() << '';
पी क्यू।पॉप();
}
लागत << 'एन';

अन्य प्राथमिकता कतार कार्य

आकार () फ़ंक्शन
यह फ़ंक्शन प्राथमिकता कतार की लंबाई देता है, जैसा कि निम्न कोड दिखाता है:

प्राथमिकता कतार<NS>पी क्यू;
NSi1= 10; NSi2= 30; NSi3= बीस; NSi4= पचास; NSi5= 40;
पी क्यू।धकेलना(i1);पी क्यू।धकेलना(i2);पी क्यू।धकेलना(i3);पी क्यू।धकेलना(i4);पी क्यू।धकेलना(i5);

NSलेन=पी क्यू।आकार();
लागत <<लेन<< 'एन';

आउटपुट 5 है।

स्वैप () फ़ंक्शन
यदि दो प्राथमिकता_क्यू एक ही प्रकार और आकार के हैं, तो उन्हें इस फ़ंक्शन द्वारा स्वैप किया जा सकता है, जैसा कि निम्न कोड दिखाता है:

प्राथमिकता कतार<NS>pq1;
NSi1= 10; NSi2= 30; NSi3= बीस; NSi4= पचास; NSi5= 40;
पीक्यू1.धकेलना(i1);पीक्यू1.धकेलना(i2);पीक्यू1.धकेलना(i3);पीक्यू1.धकेलना(i4);पीक्यू1.धकेलना(i5);

प्राथमिकता कतार<NS>पीक्यूए;
NSआईटी1= 1; NSआईटी२= 3; NSआईटी3= 2; NSआईटी4= 5; NSआईटी5= 4;
पीक्यूएधकेलना(आईटी1);पीक्यूएधकेलना(आईटी२);पीक्यूएधकेलना(आईटी3);पीक्यूएधकेलना(आईटी4);पीक्यूएधकेलना(आईटी5);

पीक्यू1.विनिमय(पीक्यूए);

जबकि(!पीक्यू1.खाली())
{
लागत <<पीक्यू1.ऊपर() << '';
पीक्यू1.पॉप();
} लागत<<'एन';

जबकि(!पीक्यूएखाली())
{
लागत <<पीक्यूएऊपर() << '';
पीक्यूएपॉप();
} लागत<<'एन';

आउटपुट है:

 5  4  3  2  1
 50  40  30  20 ​​ 10

एम्प्लेस () फंक्शन
NS जगह () फ़ंक्शन पुश फ़ंक्शन के समान है। निम्नलिखित कोड इसे दिखाता है:

प्राथमिकता कतार<NS>pq1;
NSi1= 10; NSi2= 30; NSi3= बीस; NSi4= पचास; NSi5= 40;
पीक्यू1.ठहरना(i1);पीक्यू1.ठहरना(i2);पीक्यू1.ठहरना(i3);पीक्यू1.ठहरना(i4);पीक्यू1.ठहरना(i5);

जबकि(!पीक्यू1.खाली())
{
लागत <<पीक्यू1.ऊपर() << '';
पीक्यू1.पॉप();
} लागत<<'एन';

आउटपुट है:

50 40 30 20 10

स्ट्रिंग डेटा

स्ट्रिंग्स की तुलना करते समय, स्ट्रिंग क्लास का उपयोग किया जाना चाहिए, न कि स्ट्रिंग अक्षर का प्रत्यक्ष उपयोग क्योंकि यह पॉइंटर्स की तुलना करेगा न कि वास्तविक स्ट्रिंग्स। निम्न कोड दिखाता है कि स्ट्रिंग क्लास का उपयोग कैसे किया जाता है:

#शामिल
प्राथमिकता कतार<डोरी>pq1;
स्ट्रिंग s1=डोरी('कलम'), एस२=डोरी('पेंसिल'), एस३=डोरी('अभ्यास पुस्तिका'), एस४=डोरी('पाठ्य पुस्तक'), s5=डोरी('शासक');

पीक्यू1.धकेलना(एस 1);पीक्यू1.धकेलना(एस 2);पीक्यू1.धकेलना(s3);पीक्यू1.धकेलना(एस 4);पीक्यू1.धकेलना(s5);
जबकि(!पीक्यू1.खाली())
{
लागत <<पीक्यू1.ऊपर() << '';
पीक्यू1.पॉप();
} लागत<<'एन';

आउटपुट है:

 पाठ्यपुस्तक शासक  पेंसिल  पेन  व्यायाम पुस्तक

अन्य प्राथमिकता कतार निर्माण

एक वेक्टर से स्पष्ट निर्माण
निम्न कोड से पता चलता है कि एक वेक्टर से एक प्राथमिकता कतार स्पष्ट रूप से बनाई जा सकती है:

#शामिल
वेक्टर<NS>वीटीआर= {10,30,बीस,पचास,40};

प्राथमिकता कतार<NS>पी क्यू(वीटीआरशुरू(), वीटीआर।समाप्त());

जबकि(!पी क्यू।खाली())
{
लागत <<पी क्यू।ऊपर() << '';
पी क्यू।पॉप();
} लागत<<'एन';

आउटपुट है: 50 40 30 20 10. इस बार, वेक्टर हेडर को भी शामिल करना होगा। कंस्ट्रक्टर फ़ंक्शन के तर्क वेक्टर के प्रारंभ और अंत पॉइंटर्स लेते हैं। वेक्टर के लिए डेटा प्रकार और प्राथमिकता_क्यू के लिए डेटा प्रकार समान होना चाहिए।

कम से कम मूल्य को प्राथमिकता देने के लिए, कंस्ट्रक्टर के लिए घोषणा होगी:

प्राथमिकता कतार<NS, वेक्टर<NS>, ग्रेटर>NS> >पी क्यू(वीटीआरशुरू(), वीटीआर।समाप्त());

एक सरणी से स्पष्ट निर्माण
एक प्राथमिकता कतार स्पष्ट रूप से एक सरणी से बनाई जा सकती है जैसा कि निम्न कोड दिखाता है:

NSआगमन[] = {10,30,बीस,पचास,40};

प्राथमिकता कतार<NS>पी क्यू(गिरफ्तार, गिरफ्तार+5);

जबकि(!पी क्यू।खाली())
{
लागत <<पी क्यू।ऊपर() << '';
पी क्यू।पॉप();
} लागत<<'एन';

आउटपुट है: ५० ४० ३० २० १०। कंस्ट्रक्टर फ़ंक्शन के लिए तर्क सरणी के प्रारंभ और अंत पॉइंटर्स लेते हैं। arr प्रारंभ सूचक देता है, arr+5 सरणी के ठीक पहले सूचक देता है, और 5 सरणी का आकार है। सरणी के लिए डेटा प्रकार और प्राथमिकता_क्यू के लिए डेटा प्रकार समान होना चाहिए।

कम से कम मूल्य को प्राथमिकता देने के लिए, कंस्ट्रक्टर के लिए घोषणा होगी:

प्राथमिकता कतार<NS, वेक्टर<NS>, ग्रेटर<NS> >पी क्यू(गिरफ्तार, गिरफ्तार+5);

नोट: सी ++ में, प्राथमिकता_क्यू को वास्तव में एक एडेप्टर कहा जाता है, न कि केवल एक कंटेनर।

कस्टम तुलना कोड

प्राथमिकता कतार में सभी मान आरोही या सभी अवरोही होना प्राथमिकता कतार के लिए एकमात्र विकल्प नहीं है। उदाहरण के लिए, अधिकतम ढेर के लिए 11 पूर्णांकों की सूची है:

88, 86, 87, 84, 82, 79,74, 80, 81, 64, 69

उच्चतम मान 88 है। इसके बाद दो संख्याएँ आती हैं: 86 और 87, जो 88 से कम हैं। शेष संख्याएँ इन तीन संख्याओं से कम हैं, लेकिन वास्तव में क्रम में नहीं हैं। सूची में दो खाली सेल हैं। संख्याएँ ८४ और ८२ ८६ से कम हैं। संख्याएँ ७९ और ७४ संख्याएँ ८७ से कम हैं। संख्याएँ ८० और ८१ संख्याएँ ८४ से कम हैं। संख्याएँ ६४ और ६९ संख्याएँ ७९ से कम हैं।

संख्याओं की नियुक्ति अधिकतम-ढेर मानदंड का पालन करती है - बाद में देखें। प्राथमिकता_क्यू के लिए ऐसी योजना प्रदान करने के लिए, प्रोग्रामर को अपना तुलना कोड प्रदान करना होगा - बाद में देखें।

निष्कर्ष

एक सी ++ प्राथमिकता_क्यू पहली-इन-फर्स्ट-आउट कतार है। सदस्य समारोह, धकेलना(), कतार में एक नया मान जोड़ता है। सदस्य समारोह, ऊपर(), कतार में शीर्ष मान पढ़ता है। सदस्य समारोह, पॉप (), कतार के शीर्ष मूल्य को वापस किए बिना हटा देता है। सदस्य समारोह, खाली(), जाँचता है कि क्या कतार खाली है। हालांकि, प्राथमिकता_क्यू कतार से अलग है, इसमें, यह कुछ प्राथमिकता एल्गोरिदम का पालन करता है। यह सबसे बड़ा हो सकता है, पहले से आखिरी तक, या कम से कम, पहले से आखिरी तक। मानदंड (एल्गोरिदम) प्रोग्रामर-परिभाषित भी हो सकते हैं।