logo

Priority Queue C++:ssa

Prioriteettijono C++:ssa on johdettu STL:n säilö, joka ottaa huomioon vain korkeimman prioriteetin elementin. Jono noudattaa FIFO-käytäntöä, kun taas prioriteettijono ponnahtaa elementit prioriteetin perusteella, eli korkeimman prioriteetin elementti pompataan ensin.

Se on tietyiltä osin samanlainen kuin tavallinen jono, mutta eroaa seuraavista tavoista:

  • Prioriteettijonossa jokainen jonon elementti liittyy johonkin prioriteettiin, mutta prioriteettia ei ole jonotietorakenteessa.
  • Elementti, jolla on korkein prioriteetti prioriteettijonossa, poistetaan ensin, kun taas jono seuraa FIFO (First-In-First-Out) Käytäntö tarkoittaa, että ensin lisätty elementti poistetaan ensin.
  • Jos on olemassa useampi kuin yksi elementti samalla prioriteetilla, elementin järjestys jonossa otetaan huomioon.

Huomautus: Prioriteettijono on normaalin jonon laajennettu versio, paitsi että korkeimman prioriteetin omaava elementti poistetaan ensin prioriteettijonosta.

Prioriteettijonon syntaksi

 priority_queue variable_name; 

Ymmärretään prioriteettijono yksinkertaisen esimerkin avulla.

Priority Queue C++:ssa

Yllä olevassa kuvassa olemme lisänneet elementit push()-funktiolla, ja lisäystoiminto on identtinen normaalin jonon kanssa. Mutta kun poistamme elementin jonosta pop()-funktiolla, korkeimman prioriteetin omaava elementti poistetaan ensin.

Priority Queuen jäsentoiminto

Toiminto Kuvaus
työntää() Se lisää uuden elementin prioriteettijonoon.
pop() Se poistaa jonosta ylimmän elementin, jolla on korkein prioriteetti.
alkuun() Tätä funktiota käytetään käsittelemään prioriteettijonon ylintä elementtiä.
koko() Se määrittää prioriteettijonon koon.
tyhjä() Se tarkistaa, onko jono tyhjä vai ei. Vahvistuksen perusteella se palauttaa tilan.
vaihtaa() Se vaihtaa prioriteettijonon elementit toisen jonon kanssa, jolla on sama tyyppi ja koko.
sijainti() Se lisää uuden elementin prioriteettijonon yläosaan.

Luodaan yksinkertainen ohjelma prioriteettijonosta.

 #include #include using namespace std; int main() { priority_queue p; // variable declaration. p.push(10); // inserting 10 in a queue, top=10 p.push(30); // inserting 30 in a queue, top=30 p.push(20); // inserting 20 in a queue, top=20 cout&lt;<'number of elements available in 'p' :'<<p>In the above code, we have created a priority queue in which we insert three elements, i.e., 10, 30, 20. After inserting the elements, we display all the elements of a priority queue by using a while loop.<p></p> <p> <strong>Output</strong> </p> <pre> Number of elements available in &apos;p&apos; :3 30 20 10 zzzzz/ </pre> <p> <strong>Let&apos;s see another example of a priority queue.</strong> </p> <pre> #include #include using namespace std; int main() { priority_queue p; // priority queue declaration priority_queue q; // priority queue declaration p.push(1); // inserting element &apos;1&apos; in p. p.push(2); // inserting element &apos;2&apos; in p. p.push(3); // inserting element &apos;3&apos; in p. p.push(4); // inserting element &apos;4&apos; in p. q.push(5); // inserting element &apos;5&apos; in q. q.push(6); // inserting element &apos;6&apos; in q. q.push(7); // inserting element &apos;7&apos; in q. q.push(8); // inserting element &apos;8&apos; in q. p.swap(q); std::cout &lt;&lt; &apos;Elements of p are : &apos; &lt;&lt; std::endl; while(!p.empty()) { std::cout &lt;&lt; p.top() &lt;&lt; std::endl; p.pop(); } std::cout &lt;&lt; &apos;Elements of q are :&apos; &lt;&lt; std::endl; while(!q.empty()) { std::cout &lt;&lt; q.top() &lt;&lt; std::endl; q.pop(); } return 0; } </pre> <p>In the above code, we have declared two priority queues, i.e., p and q. We inserted four elements in &apos;p&apos; priority queue and four in &apos;q&apos; priority queue. After inserting the elements, we swap the elements of &apos;p&apos; queue with &apos;q&apos; queue by using a swap() function.</p> <p> <strong>Output</strong> </p> <pre> Elements of p are : 8 7 6 5 Elements of q are : 4 3 2 1 </pre> <hr></'number>

Katsotaanpa toinen esimerkki prioriteettijonosta.

 #include #include using namespace std; int main() { priority_queue p; // priority queue declaration priority_queue q; // priority queue declaration p.push(1); // inserting element &apos;1&apos; in p. p.push(2); // inserting element &apos;2&apos; in p. p.push(3); // inserting element &apos;3&apos; in p. p.push(4); // inserting element &apos;4&apos; in p. q.push(5); // inserting element &apos;5&apos; in q. q.push(6); // inserting element &apos;6&apos; in q. q.push(7); // inserting element &apos;7&apos; in q. q.push(8); // inserting element &apos;8&apos; in q. p.swap(q); std::cout &lt;&lt; &apos;Elements of p are : &apos; &lt;&lt; std::endl; while(!p.empty()) { std::cout &lt;&lt; p.top() &lt;&lt; std::endl; p.pop(); } std::cout &lt;&lt; &apos;Elements of q are :&apos; &lt;&lt; std::endl; while(!q.empty()) { std::cout &lt;&lt; q.top() &lt;&lt; std::endl; q.pop(); } return 0; } 

Yllä olevassa koodissa olemme ilmoittaneet kaksi prioriteettijonoa, eli p ja q. Lisäsimme neljä elementtiä 'p'-prioriteettijonoon ja neljä 'q'-prioriteettijonoon. Kun elementit on lisätty, vaihdamme 'p'-jonon elementit 'q'-jonoon käyttämällä swap()-funktiota.

Lähtö

 Elements of p are : 8 7 6 5 Elements of q are : 4 3 2 1