Prioritní fronta v C++ je odvozený kontejner v STL, který bere v úvahu pouze prvek s nejvyšší prioritou. Fronta se řídí zásadou FIFO, zatímco prioritní fronta vybírá prvky na základě priority, tj. prvek s nejvyšší prioritou je vyskakován jako první.
V určitých aspektech je podobná běžné frontě, ale liší se v následujících ohledech:
- V prioritní frontě je každému prvku ve frontě přiřazena nějaká priorita, ale priorita v datové struktuře fronty neexistuje.
- Prvek s nejvyšší prioritou ve frontě s prioritou bude odstraněn jako první, zatímco fronta bude následovat FIFO (first-in-first-out) zásada znamená, že prvek, který je vložen jako první, bude smazán jako první.
- Pokud existuje více než jeden prvek se stejnou prioritou, bude zohledněno pořadí prvku ve frontě.
Poznámka: Fronta priority je rozšířenou verzí normální fronty s tím rozdílem, že prvek s nejvyšší prioritou bude z fronty s prioritou odstraněn jako první.
Syntaxe prioritní fronty
priority_queue variable_name;
Pojďme pochopit prioritní frontu na jednoduchém příkladu.
Na obrázku výše jsme prvky vložili pomocí funkce push() a operace vložení je totožná s normální frontou. Ale když odstraníme prvek z fronty pomocí funkce pop(), pak bude nejprve odstraněn prvek s nejvyšší prioritou.
rozdíl tygří lev
Členská funkce prioritní fronty
| Funkce | Popis |
|---|---|
| TAM() | Vloží nový prvek do prioritní fronty. |
| pop() | Odebere horní prvek z fronty, který má nejvyšší prioritu. |
| horní() | Tato funkce se používá k adresování nejvyššího prvku prioritní fronty. |
| velikost() | Určuje velikost prioritní fronty. |
| prázdný() | Ověřuje, zda je fronta prázdná nebo ne. Na základě ověření vrátí stav. |
| swap() | Vymění prvky prioritní fronty s jinou frontou, která má stejný typ a velikost. |
| umístění() | Vloží nový prvek na začátek prioritní fronty. |
Vytvořme jednoduchý program prioritní fronty.
#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> Podívejme se na další příklad prioritní fronty.
#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; } Ve výše uvedeném kódu jsme deklarovali dvě prioritní fronty, tj. p a q. Vložili jsme čtyři prvky do prioritní fronty 'p' a čtyři do prioritní fronty 'q'. Po vložení prvků zaměníme prvky fronty 'p' za frontu 'q' pomocí funkce swap().
Výstup
obrácený řetězec v jazyce Java
Elements of p are : 8 7 6 5 Elements of q are : 4 3 2 1