Очередь приоритетов std::priority_queue

Класс std::priority_queue<T> представляет очередь приоритетов - контейнер, который, как и станлдартная очередь, работает по принципу FIFO. Данный класс определен в заголовочном файле <queue> (там же, где и класс queue), однако в плане функционала больше похож на класс stack.

Определение пустой очереди приоритетов:

#include <iostream>
#include <queue>

int main()
{
    std::priority_queue<std::string> queue;
}

Размер очереди

С помощью функции size() можно получить количество элементов в стеке, а с помощью функции empty() проверить стек на наличие элементов (если возвращается true, то стек пуст):

#include <iostream>
#include <queue>

int main()
{
    std::priority_queue<std::string> queue;
    if(queue.empty())
    {
        std::cout << "queue is empty" << std::endl;
    }
    std::cout << "queue size: " << queue.size() << std::endl; // queue size: 0
}

добавление элементов

Для добавления в очередь приоритетов применяется функция push(), в которую передается добавляемый элемент:

#include <iostream>
#include <queue>

int main()
{
    std::priority_queue<std::string> queue;

    // добавляем три элемента
    queue.push("Tom");
    queue.push("Bob");
    queue.push("Sam");

	std::cout << "queue size: " << queue.size() << std::endl; // queue size: 3
}

Получение элементов

Мы можем получить только самый первый элемент очереди - для этого применяется функция top():

#include <iostream>
#include <queue>

int main()
{
    std::priority_queue<std::string> queue;

    // добавляем три элемента
    queue.push("Sam");
    queue.push("Tom");
    queue.push("Bob");

	std::cout << "First: " << queue.top() << std::endl; // Top: Tom
}

Обратите внимание, что первой добавляется строка "Sam", а последней - строка "Bob", однако первой (условно более приоритетной) мы получаем строку "Tom". В данном случае мы как раз сталкиваемся с действием приоритетов. При добавлении элементов в очередь приоритетов применяется функция компаратора, которая сравнивает добавляемые элементы и располагает их в очереди в определенном порядке.

По умолчанию применяется для сравнения данных применяется функция, которая располагает первыми элементы, которые условно "больше". Например, строка "Tom" условно больше, чем "Sam" или "Bob", потому что буква "T" располагается в алфавите после "S" и "B". Соответственно очередь будет выглядеть таким образом:

Tom(1) - Sam (2) - Bob(3)

Другой пример:

#include <iostream>
#include <queue>

int main()
{
    std::priority_queue<int> numbers;

    numbers.push(4);
    numbers.push(22);
    numbers.push(13);

	std::cout << "First: " << numbers.top() << std::endl; // Top: 22
}

В данном случае элементы будут располагаться следующим образом:

22 - 13 - 4

Удаление элементов

Для удаления элементов применяется функция pop(), которая извлекает элемент из начала очереди:

queue.pop()

Комбинируя эту функцию с функцией top() можно извлечь все элементы очереди:

#include <iostream>
#include <queue>

int main()
{
    std::priority_queue<std::string> queue;
    queue.push("Sam");
    queue.push("Tom");
    queue.push("Bob");

    while (!queue.empty())	// пока очередь не станет пустой
    {
        std::cout << queue.top() << std::endl;
        queue.pop();	// извлекаем первый элемент
    }
}

В данном случае, пока очередь не станет пустой, выводим на консоль первый (самый приоритетный) элемент с помощью функции top и затем извлекаем его с помощью функции pop. Консольный вывод программы:

Tom
Sam
Bob