Aula por Matheo Angelo
Esta aula vai te ensinar a usar uma estrutura de dados muito importante, a Priority Queue, ou Fila de Prioridade. Essa estrutura funciona de maneira semelhante à Queue, já que as operações principais são inserir um elemento e checar (ou remover) o elemento da frente, mas com uma exceção bastante interessante: o maior elemento é sempre o primeiro da fila. Ou seja, os elementos ficam ordenados de acordo com a prioridade.
A sintaxe usada para declarar uma Priority Queue é semelhante à das outras estruturas de dados da STL.
| #include<iostream> | |
| #include<queue> // biblioteca da Priority Queue | |
| using namespace std; | |
| int main() | |
| { | |
| // priority_queue< tipo_de_variavel > nome_da_priority_queue; | |
| priority_queue<int> fila; | |
| return 0; | |
| } |
Vamos agora comentar sobre as funções mais importantes que já vêm implementadas na biblioteca STL do C++!
Adicionar um elemento na fila:
Para adicionar um elemento à fila de prioridade, basta usar o comando push(). Inserir elementos na Priority Queue tem complexidade $O(log \ N)$. Vale lembrar que a notação $log \ N$, neste curso, significa $log_{{}_2} \ N$.
| priority_queue<int> fila; | |
| // Adiciona os elemntos em fila | |
| fila.push(3); | |
| fila.push(1); | |
| fila.push(2); | |
| // Ao final a priority queue vai conter os elementos 3, 2 e 1 nessa ordem. |
Checar o elemento na frente da fila:
O primeiro elemento da fila pode ser acessado através da função top().
| priority_queue<int> fila; | |
| fila.push(3); | |
| fila.push(1); | |
| fila.push(2); | |
| cout << fila.top() << "\n"; | |
| // O programa irá imprimir o número 3, que é o | |
| // elemento que está na frente, no topo, da fila. |
Tirar o elemento na frente da fila:
Para remover o elemento na frente da fila, ou seja, fazer “a fila andar”, usa-se o comando pop().
| priority_queue<int> fila; | |
| fila.push(3); | |
| fila.push(1); | |
| fila.push(2); | |
| fila.pop(); // Remove o primeiro elemento da fila, ou seja, o 3. | |
| cout << fila.top() << "\n"; | |
| // O programa irá imprimir o número 2, | |
| // que é agora o elemento da frente |
Obter o tamanho da fila:
A função size() retorna a quantidade de elementos na fila atualmente.
| priority_queue<int> fila; | |
| fila.push(5); | |
| fila.push(10); | |
| cout << fila.size() << "\n"; // nesse caso, a fila tem 2 elementos |
Saber se a fila está vazia:
A função empty() retorna um valor de true (Verdadeiro) se a fila estiver vazia, ou false (Falso) caso haja pelo menos 1 elemento nela.
| priority_queue<int> fila; | |
| if(fila.empty()) // Aqui a fila está vazia, já que nada foi inserido ainda | |
| { | |
| cout << "Vazia\n"; | |
| } | |
| fila.push(3); // A partir deste momento a fila não está mais vazia | |
| // Então, fila.empty() retornará Falso | |
| if(fila.empty()) // Como a fila não está vazia não entraremos nesse if | |
| { | |
| cout << "Vazia\n"; | |
| } | |
| // Logo, o código so irá imprimir "Vazio" uma unica vez |
Uma observação interessante é que se quisermos checar se a fila não está vazia podemos usar o operador lógico de negação (!), ou seja, iremos fazer !fila.empty(). Isso funciona porque, se a fila tiver vazia fila.empty() irá retornar Verdadeiro e a negação de Verdeiro é Falso, ou se a fila não estiver vazia fila.empty() irá retornar Falso e a negação de Falso é Verdadeiro. Observe o código abaixo para maior compreensão:
| priority_queue<int> fila; | |
| if(!fila.empty()) // Aqui a fila está vazia, já que nada foi inserido ainda | |
| { | |
| cout << "Não está vazia\n"; | |
| } | |
| // Note que o código não irá entrar na checagem anterior | |
| fila.push(3); // A partir deste momento a fila não está mais vazia | |
| // Então, !fila.empty() retornará Verdadeiro | |
| if(fila.empty()) // Como a fila não está vazia o código entrar nessa checagem | |
| { | |
| cout << "Não está vazia\n"; | |
| } | |
| // Logo, o código so irá imprimir "Não está vazia" uma unica vez. |
Se você quiser ver direitinho tudo que a Priority Queue faz, da uma olhada no C++ Reference clicando aqui.
Para dar aquela testada nos seus conhecimentos recém adquiridos, segue alguns problemas para você se divertir. 
Deseja voltar para página do Curso de Informática, então clique aqui.