Datová struktura “priority_queue”
C++ 11

image_printTisk

Někdy potřebujeme jiné zpracování než sekvenční dle pořadí vložení prvků jako u klasické fronty. Řekněme, že prvky mají například číselně vyjádřenou prioritu své důležitosti a my je chceme zpracovávat dle této priority. Právě k tomu slouží datová struktura prioritní fronta popsaná právě v tomto článku.

Deklarace

Deklarace prioritní fronty vypadá následovně, jak ukazuje příklad.

#include <queue>
#include <string>
using namespace std;

struct Employee {
    string name;
    int wage;
    
    bool operator<(const Employee& emp) const {
        return wage < emp.wage;
    }
};

int main() {
    priority_queue<int> intPQueue;
    priority_queue<Employee> empPQueue;
    return 0;
}

Napřed musíme vložit hlavičkový soubor <queue>. Prioritní frontu pak deklarujeme stejně jako jakoukoliv jinou šablonu STL datové struktury. U uživatelsky definovaného typu nesmíme zapomenou na definici operátoru “menší než”, jak bude vysvětleno dále. Je důležité také zmínit, že tento operátor musí být deklarován jako const, tedy že nemění vnitřní stav objektu a může být vyvolán pro konstantní prvky daného uživatelského typu.

Užití

Prvky jsou do prioritní fronty vkládány pomocí metody push(). Následné zpracování probíhá pak způsobem, že prvek, který je na řadě, získáme zavoláním metody top() a až je zpracovaný, tak pak jej můžeme z prioritní fronty vyjmout zavoláním metody pop(). Další užitečnou metodou je metoda empty(), která vrací hodnotu true, pokud již je prioritní fronta prázdná. Tato metoda se většinou používá v cyklech, kde testujeme, zda jsme zpracovali všechny položky fronty.

Jelikož prioritní fronta řadí položky dle jejich důležitosti, existuje požadavek na uživatelsky definované datové typy, aby obsahovali operátor “menší než”. Tento operátor pak vyvolává daná datová struktura prioritní fronty ke třídění prvků dle priority a jejich předávání ke zpracování.

Seznam metod

empty


Metoda empty() testuje, zda je datová struktura prázdná anebo ne. Pokud neobsahuje žádné položky, vrací true, jinak false.

size


Metoda size() vrací počet položek v prioritní frontě.

top


Metoda top() vrací následující položku ke zpracování, tedy položku s největší prioritou.

push a pop


Metoda push() vkládá do prioritní fronty novou položku a metoda pop() odstraňuje prvek s nejvyjšší prioritou.

#include &lt;iostream&gt;
#include &lt;queue&gt;
using namespace std;

const int itemCount = 10;
int data[itemCount] = { 1, 4, 3, 5, 2, 4, 6, 3, 7, 1 };

int main() {
    priority_queue&lt;int&gt; pq;
    for(int i = 0; i &lt; itemCount; i++)
        pq.push(data[i]);
        
    while(! pq.empty()) {
        cout &lt;&lt; pq.top() &lt;&lt; &quot;;&quot;;
        pq.pop();
    }
    return 0;
}
Unable to connect to the JDoodle service.

emplace


#include &lt;iostream&gt;
#include &lt;queue&gt;
#include &lt;string&gt;
using namespace std;

struct Employee {
    string name;
    int wage;
    
    Employee(string n, int w): name(n), wage(w) {}
    
    bool operator&lt;(const Employee&amp; emp) const {
        return wage &lt; emp.wage;
    }
};

ostream&amp; operator&lt;&lt;(ostream&amp; os, const Employee&amp; emp) {
    os &lt;&lt; emp.name &lt;&lt; &quot;: &quot; &lt;&lt; emp.wage &lt;&lt; &quot; Kč&quot; &lt;&lt; endl;
    return os;
}

int main() {
    priority_queue&lt;Employee&gt; empPQ;
    empPQ.emplace(&quot;Aleš&quot;, 20000);
    empPQ.emplace(&quot;Monika&quot;, 30000);
    empPQ.emplace(&quot;Yveta&quot;, 15000);
    empPQ.emplace(&quot;Václav&quot;, 40000);
    empPQ.emplace(&quot;Dominik&quot;, 25000);
    
    while(! empPQ.empty()) {
        cout &lt;&lt; empPQ.top();
        empPQ.pop();
    }
}
Unable to connect to the JDoodle service.

image_printTisk
Datová struktura “priority_queue”
C++ 11
Ohodnoťte tento článek

Související články

  • Datová struktura “queue” Fronta funguje na principu zvaném FIFO (First-In First-Out). To znamená, že prvek, který byl do fronty vložen dříve, bude také dříve zpracováván. V podstatě můžeme říci, že prvky vyjímáme […]
  • Datová struktura “stack” Datová struktura zásobník funguje na principu zvaném LIFO (Last In First Out). To znamená, že položka, která do něj byla vložena poslední,  je jako první vyjmuta. V podstatě můžeme říci, […]
  • Relační operátory Tento článek pojednává o porovnávacích, jinak nazývané také relačních,  operátorech v jazyce C++. Souhrnně se o nich zmíníme, ukážeme si opět rozdíl jejich zápisu od klasické matematiky a […]
  • Aritmetické operátory Tento článek by měl čtenáři nastínit používání základních aritmetických operátorů v jazyce C++. Je dobré upozornit, že C++ disponuje širší sadou operátorů, než se třeba pojednává ve […]
  • Práce se soubory pomocí knihovny STL V tomto článku si popíšeme základy práce se soubory pomocí knihovny STL. Práce se soubory pomocí této knihovny je mnohem snadnější, než pomocí staršího přístupu pomocí standardní knihovny […]
  • Seznamy hodnot a cyklus “range-for” Úvod Datový typ vector nový datový typ v zobáčcích datový typ prvku inicalizace pomocí { } indexovací operátor pouze pouze na čísla range for cyklus […]