Coada de priorități std::priority_queue

Clasa std::priority_queue<T> reprezintă o coadă de priorități – un container care, asemenea unei cozi standard, funcționează după principiul FIFO (first-in, first-out – „primul intrat, primul ieșit”). Totuși, din punct de vedere al funcționalității, această clasă seamănă mai mult cu o stivă (stack).

Clasa este definită în fișierul antet <queue> (același ca pentru queue).

Definirea unei cozi de priorități goale:

#include <iostream>
#include <queue>
 
int main()
{
    std::priority_queue<std::string> queue;
}

Dimensiunea cozii

Cu ajutorul funcției size() putem obține numărul de elemente din coadă, iar cu empty() putem verifica dacă aceasta este goală (dacă returnează true, coada este goală):

#include <iostream>
#include <queue>
 
int main()
{
    std::priority_queue<std::string> queue;
    if(queue.empty())
    {
        std::cout << "queue is empty" << std::endl;
    }
    std::cout << "queue size: " << queue.size() << std::endl; // queue size: 0
}

Adăugarea elementelor

Pentru a adăuga elemente în coada de priorități se folosește funcția push():

#include <iostream>
#include <queue>
 
int main()
{
    std::priority_queue<std::string> queue;
 
    // adăugăm trei elemente
    queue.push("Tom");
    queue.push("Bob");
    queue.push("Sam");
 
    std::cout << "queue size: " << queue.size() << std::endl; // queue size: 3
}

Accesarea elementelor

Putem accesa doar primul (cel mai prioritar) element al cozii cu ajutorul funcției top():

#include <iostream>
#include <queue>
 
int main()
{
    std::priority_queue<std::string> queue;
 
    // adăugăm trei elemente
    queue.push("Sam");
    queue.push("Tom");
    queue.push("Bob");
 
    std::cout << "First: " << queue.top() << std::endl; // Top: Tom
}

Observație: deși "Sam" este adăugat primul, iar "Bob" ultimul, primul element returnat este "Tom". Aici intervine mecanismul de prioritizare. La adăugarea elementelor, se folosește o funcție de comparare (comparator) care le ordonează într-un anumit mod.

În mod implicit, se utilizează o funcție care consideră „mai mari” (mai prioritare) elementele cu valoare mai mare. De exemplu, "Tom" este considerat mai mare decât "Sam" sau "Bob", deoarece litera 'T' vine după 'S' și 'B' în alfabet. Astfel, coada arată astfel:

Tom (1) - Sam (2) - Bob (3)

Un alt exemplu:

#include <iostream>
#include <queue>
 
int main()
{
    std::priority_queue<int> numbers;
 
    numbers.push(4);
    numbers.push(22);
    numbers.push(13);
 
    std::cout << "First: " << numbers.top() << std::endl; // Top: 22
}

În acest caz, elementele vor fi ordonate așa:

22 - 13 - 4

Ștergerea elementelor

Pentru a elimina elementul cu cea mai mare prioritate se folosește funcția pop():

queue.pop();

Combinând această funcție cu top() putem extrage toate elementele în ordinea priorității:

#include <iostream>
#include <queue>
 
int main()
{
    std::priority_queue<std::string> queue;
    queue.push("Sam");
    queue.push("Tom");
    queue.push("Bob");
 
    while (!queue.empty())  // cât timp coada nu este goală
    {
        std::cout << queue.top() << std::endl;
        queue.pop();    // extragem elementul cu cea mai mare prioritate
    }
}

În acest caz, cât timp coada nu este goală, afișăm elementul cu prioritatea cea mai mare folosind top() și apoi îl eliminăm cu pop(). Ieșirea în consolă a programului:

Tom  
Sam  
Bob