Kolejka priorytetowa w C++ jest kontenerem pochodnym w STL, który uwzględnia tylko element o najwyższym priorytecie. Kolejka działa zgodnie z polityką FIFO, podczas gdy kolejka priorytetowa umieszcza elementy w oparciu o priorytet, tj. element o najwyższym priorytecie jest otwierany jako pierwszy.
Pod pewnymi względami przypomina zwykłą kolejkę, ale różni się od niej następującymi cechami:
pawandeep rajan
- W kolejce priorytetowej każdy element kolejki jest powiązany z pewnym priorytetem, ale priorytet nie istnieje w strukturze danych kolejki.
- Element o najwyższym priorytecie w kolejce priorytetowej zostanie usunięty jako pierwszy, a kolejka nastąpi po nim FIFO (pierwsze weszło, pierwsze wyszło) polityka oznacza, że element wstawiony jako pierwszy zostanie usunięty jako pierwszy.
- Jeżeli istnieje więcej niż jeden element o tym samym priorytecie, wówczas pod uwagę brana będzie kolejność elementów w kolejce.
Uwaga: Kolejka priorytetowa jest rozszerzoną wersją zwykłej kolejki, z tą różnicą, że element o najwyższym priorytecie zostanie usunięty jako pierwszy z kolejki priorytetowej.
Składnia kolejki priorytetowej
priority_queue variable_name;
Przyjrzyjmy się kolejce priorytetowej na prostym przykładzie.
Na powyższej ilustracji wstawiamy elementy za pomocą funkcji push(), a operacja wstawiania jest identyczna jak w przypadku normalnej kolejki. Kiedy jednak usuniemy element z kolejki za pomocą funkcji pop(), wówczas element o najwyższym priorytecie zostanie usunięty jako pierwszy.
Funkcja członkowska kolejki priorytetowej
| Funkcjonować | Opis |
|---|---|
| naciskać() | Wstawia nowy element do kolejki priorytetowej. |
| Muzyka pop() | Usuwa z kolejki najwyższy element, który ma najwyższy priorytet. |
| szczyt() | Ta funkcja służy do adresowania najwyższego elementu kolejki priorytetowej. |
| rozmiar() | Określa rozmiar kolejki priorytetowej. |
| pusty() | Sprawdza, czy kolejka jest pusta, czy nie. Na podstawie weryfikacji zwraca status. |
| zamieniać() | Zamienia elementy kolejki priorytetowej z inną kolejką tego samego typu i rozmiaru. |
| Lokalizacja() | Wstawia nowy element na górze kolejki priorytetowej. |
Stwórzmy prosty program kolejki priorytetowej.
#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> Zobaczmy inny przykład kolejki priorytetowej.
#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; } W powyższym kodzie zadeklarowaliśmy dwie kolejki priorytetowe, tj. p i q. Wstawiliśmy cztery elementy do kolejki priorytetowej „p” i cztery elementy do kolejki priorytetowej „q”. Po wstawieniu elementów zamieniamy elementy kolejki „p” z kolejką „q” za pomocą funkcji swap().
Wyjście
Elements of p are : 8 7 6 5 Elements of q are : 4 3 2 1