Implementando Fila de Prioridade

Introdução

Neste laboratório, aprenderemos sobre a funcionalidade básica da Fila de Prioridade (Priority Queue) na linguagem de programação C++. A Fila de Prioridade é um container na STL (Standard Template Library) do C++ que permite inserir e remover elementos de acordo com sua prioridade. O elemento com a maior prioridade é sempre colocado na frente da fila. Quando um elemento é removido da fila, a fila de prioridade automaticamente se encarrega de inserir o elemento de prioridade mais alta seguinte em sua posição correta.

Incluir as Bibliotecas Necessárias

Criaremos um novo arquivo chamado main.cpp no diretório ~/project usando o seguinte comando:

touch ~/project/main.cpp

Primeiramente, precisamos incluir as bibliotecas necessárias para que nosso programa funcione corretamente. Neste programa, usaremos as bibliotecas iostream e bits/stdc++.h.

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

Definir a Função 'show'

A função show é usada para exibir todos os elementos presentes na fila de prioridade. A função recebe um objeto fila de prioridade como argumento e copia a fila para outra, a fim de manter a fila de prioridade original. Depois disso, ela imprime todos os elementos presentes na fila de prioridade, iterando sobre ela.

void show(priority_queue<int> q)
{
    priority_queue<int> pq = q;
    while (!pq.empty())
    {
        cout << "\t" << pq.top(); //printing the top most element
        pq.pop();                 //deleting the top most element to move to the next
    }
    cout << endl;
}

Implementar a Função Principal (Main)

A função main é onde toda a ação acontece. Primeiro, declaramos uma variável inteira i. Em seguida, criamos uma fila de prioridade de inteiros chamada q. Depois, adicionamos alguns inteiros à fila de prioridade usando a função push.

Após isso, exibimos os elementos presentes na fila de prioridade usando a função show. Em seguida, usamos a função size para exibir o número de elementos presentes na fila, e usamos a função top para exibir o elemento com a maior prioridade.

Em seguida, usamos a função pop para remover o elemento com a maior prioridade e exibir a fila de prioridade atualizada usando a função show.

int main()
{
    priority_queue<int> q;

    for (int i = 1; i < 6; i++)
    {
        q.push(i * 10);
    }

    cout << "The Priority Queue is: ";
    show(q);

    cout << "\n\nThe number of elements in the Priority Queue are: " << q.size();

    cout << "\n\nThe element with the highest priority is: " << q.top();

    q.pop();
    cout << "\n\nAfter Deleting the top most element, Priority Queue becomes: ";
    show(q);

    return 0;
}

Código Final

Você pode usar o seguinte código para implementar a Fila de Prioridade em C++:

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

void show(priority_queue<int> q)
{
    priority_queue<int> pq = q;
    while (!pq.empty())
    {
        cout << "\t" << pq.top();
        pq.pop();
    }
    cout << endl;
}

int main()
{
    priority_queue<int> q;

    for (int i = 1; i < 6; i++)
    {
        q.push(i * 10);
    }

    cout << "The Priority Queue is: ";
    show(q);

    cout << "\n\nThe number of elements in the Priority Queue are: " << q.size();

    cout << "\n\nThe element with the highest priority is: " << q.top();

    q.pop();
    cout << "\n\nAfter Deleting the top most element, Priority Queue becomes: ";
    show(q);

    return 0;
}

Salve o código acima em ~/project/main.cpp. Para compilar e executar este código, use os seguintes comandos:

g++ main.cpp -o main && ./main

Resumo

Neste laboratório, aprendemos sobre os conceitos básicos de Fila de Prioridade (Priority Queue) em C++. Também vimos como declarar e inicializar uma fila de prioridade e como adicionar, remover e exibir elementos dela. Esperamos que este tutorial tenha sido útil.