Реализация приоритетной очереди в C++

Введение

В этом лабе мы узнаем о базовых возможностях приоритетной очереди в языке программирования C++. Приоритетная очередь - это контейнер в C++ STL (Standard Template Library), который позволяет вставлять и удалять элементы в соответствии с их приоритетом. Элемент с наивысшим приоритетом всегда размещается в начале очереди. Когда элемент удаляется из очереди, приоритетная очередь автоматически заботится о вставке следующего элемента с наивысшим приоритетом в правильную позицию.

Skills Graph

%%%%{init: {'theme':'neutral'}}%%%% flowchart RL cpp(("C++")) -.-> cpp/StandardLibraryGroup(["Standard Library"]) cpp(("C++")) -.-> cpp/SyntaxandStyleGroup(["Syntax and Style"]) cpp(("C++")) -.-> cpp/ControlFlowGroup(["Control Flow"]) cpp(("C++")) -.-> cpp/IOandFileHandlingGroup(["I/O and File Handling"]) cpp/ControlFlowGroup -.-> cpp/for_loop("For Loop") cpp/ControlFlowGroup -.-> cpp/while_loop("While Loop") cpp/IOandFileHandlingGroup -.-> cpp/output("Output") cpp/StandardLibraryGroup -.-> cpp/standard_containers("Standard Containers") cpp/SyntaxandStyleGroup -.-> cpp/code_formatting("Code Formatting") subgraph Lab Skills cpp/for_loop -.-> lab-96225{{"Реализация приоритетной очереди"}} cpp/while_loop -.-> lab-96225{{"Реализация приоритетной очереди"}} cpp/output -.-> lab-96225{{"Реализация приоритетной очереди"}} cpp/standard_containers -.-> lab-96225{{"Реализация приоритетной очереди"}} cpp/code_formatting -.-> lab-96225{{"Реализация приоритетной очереди"}} end

Подключите необходимые библиотеки

Мы создадим новый файл с именем main.cpp в директории ~/project с помощью следующей команды:

touch ~/project/main.cpp

Сначала нам нужно подключить необходимые библиотеки, чтобы наша программа работала корректно. В этом программе мы будем использовать библиотеки iostream и bits/stdc++.h.

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

Определите функцию show

Функция show используется для отображения всех элементов, присутствующих в приоритетной очереди. Функция принимает объект приоритетной очереди в качестве аргумента и копирует очередь в другую, чтобы сохранить исходную приоритетную очередь. Затем она выводит все элементы, присутствующие в приоритетной очереди, перебирая ее.

void show(priority_queue<int> q)
{
    priority_queue<int> pq = q;
    while (!pq.empty())
    {
        cout << "\t" << pq.top(); //печатаем самый верхний элемент
        pq.pop();                 //удаляем самый верхний элемент, чтобы перейти к следующему
    }
    cout << endl;
}

Реализуйте функцию main

В функции main происходит вся активность. Мы сначала объявляем целочисленную переменную i. Затем мы создаем приоритетную очередь целых чисел под названием q. Затем мы добавляем несколько целых чисел в приоритетную очередь с помощью функции push.

После этого мы отображаем элементы, присутствующие в приоритетной очереди, с помощью функции show. Затем мы используем функцию size, чтобы отобразить количество элементов в очереди, и функцию top, чтобы отобразить элемент с наивысшим приоритетом.

Далее мы используем функцию pop, чтобы удалить элемент с наивысшим приоритетом, и отображаем обновленную приоритетную очередь с помощью функции 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++:

#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;
}

Сохраните вышеуказанный код в ~/project/main.cpp. Чтобы скомпилировать и запустить этот код, используйте следующие команды:

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

Резюме

В этом лабе мы узнали о базовых концепциях приоритетной очереди в C++. Мы также увидели, как объявить и инициализировать приоритетную очередь, а также как добавлять, удалять и отображать элементы из нее. Надеемся, что этот туториал был для вас полезен.