Prednostna čakalna vrsta v C++ je izpeljan vsebnik v STL, ki upošteva le element z najvišjo prioriteto. Čakalna vrsta sledi politiki FIFO, medtem ko prednostna čakalna vrsta izloči elemente na podlagi prioritete, tj. element z najvišjo prioriteto je prvi izločen.
V nekaterih vidikih je podobna navadni čakalni vrsti, vendar se razlikuje v naslednjih pogledih:
- V prednostni čakalni vrsti je vsak element v čakalni vrsti povezan z določeno prioriteto, vendar prioriteta ne obstaja v podatkovni strukturi čakalne vrste.
- Element z najvišjo prioriteto v prednostni čakalni vrsti bo odstranjen prvi, medtem ko čakalna vrsta sledi elementu FIFO (First-In-First-Out) pravilnik pomeni, da bo element, ki je prvi vstavljen, prvi izbrisan.
- Če obstaja več kot en element z enako prioriteto, se bo upošteval vrstni red elementov v čakalni vrsti.
Opomba: prednostna čakalna vrsta je razširjena različica običajne čakalne vrste, le da bo element z najvišjo prioriteto prvi odstranjen iz prednostne čakalne vrste.
Sintaksa prednostne čakalne vrste
priority_queue variable_name;
Razumejmo prednostno čakalno vrsto s preprostim primerom.
Na zgornji sliki smo elemente vstavili s funkcijo push(), operacija vstavljanja pa je enaka običajni čakalni vrsti. Ko pa s funkcijo pop() izbrišemo element iz čakalne vrste, bo najprej izbrisan element z najvišjo prioriteto.
Članska funkcija prednostne čakalne vrste
| funkcija | Opis |
|---|---|
| potisni() | V prednostno čakalno vrsto vstavi nov element. |
| pop() | Iz čakalne vrste odstrani zgornji element, ki ima najvišjo prioriteto. |
| vrh() | Ta funkcija se uporablja za naslavljanje najvišjega elementa prednostne čakalne vrste. |
| velikost () | Določa velikost prednostne čakalne vrste. |
| prazno() | Preveri, ali je čakalna vrsta prazna ali ne. Na podlagi preverjanja vrne status. |
| zamenjaj() | Zamenja elemente prednostne čakalne vrste z drugo čakalno vrsto enake vrste in velikosti. |
| lokacija() | Vstavi nov element na vrh prednostne čakalne vrste. |
Ustvarimo preprost program prednostne čakalne vrste.
#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<<'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 'p' :3 30 20 10 zzzzz/ </pre> <p> <strong>Let'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 '1' in p. p.push(2); // inserting element '2' in p. p.push(3); // inserting element '3' in p. p.push(4); // inserting element '4' in p. q.push(5); // inserting element '5' in q. q.push(6); // inserting element '6' in q. q.push(7); // inserting element '7' in q. q.push(8); // inserting element '8' in q. p.swap(q); std::cout << 'Elements of p are : ' << std::endl; while(!p.empty()) { std::cout << p.top() << std::endl; p.pop(); } std::cout << 'Elements of q are :' << std::endl; while(!q.empty()) { std::cout << q.top() << 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 'p' priority queue and four in 'q' priority queue. After inserting the elements, we swap the elements of 'p' queue with 'q' 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> Oglejmo si še en primer prednostne čakalne vrste.
#include #include using namespace std; int main() { priority_queue p; // priority queue declaration priority_queue q; // priority queue declaration p.push(1); // inserting element '1' in p. p.push(2); // inserting element '2' in p. p.push(3); // inserting element '3' in p. p.push(4); // inserting element '4' in p. q.push(5); // inserting element '5' in q. q.push(6); // inserting element '6' in q. q.push(7); // inserting element '7' in q. q.push(8); // inserting element '8' in q. p.swap(q); std::cout << 'Elements of p are : ' << std::endl; while(!p.empty()) { std::cout << p.top() << std::endl; p.pop(); } std::cout << 'Elements of q are :' << std::endl; while(!q.empty()) { std::cout << q.top() << std::endl; q.pop(); } return 0; } V zgornji kodi smo deklarirali dve prednostni čakalni vrsti, tj. p in q. Štiri elemente smo vstavili v prednostno čakalno vrsto 'p' in štiri v prednostno čakalno vrsto 'q'. Po vstavitvi elementov s funkcijo swap() zamenjamo elemente vrste 'p' s čakalno vrsto 'q'.
Izhod
Elements of p are : 8 7 6 5 Elements of q are : 4 3 2 1