Очередь в С++

Что такое очереди, вы можете узнать из этой статьи. Сейчас я хочу вам рассказать про замечательный контейнер STL — <queue>. Как вы уже наверное догадались, этот контейнер реализует модель очереди. Итак, чтобы использовать в своей программе очередь, необходимо подключить следующий заголовочный файл:

#include <queue>

Давайте рассмотрим простой пример использования очереди — queue:

#include <iostream>
#include <queue>        // подключаем заголовочный файл очереди
#include <string>       // заголовочный файл для работы со строками типа string
using namespace std;

int main()
{
    queue<string> myQueue;     // создаем пустую очередь типа string

    // добавили в очередь несколько элементов типа string
    myQueue.push("No pain ");
    myQueue.push("- no gain");

    cout << "Количество элементов в очереди: " << myQueue.size() << endl;
    cout << "\nВот они: " << myQueue.front() << myQueue.back();

    myQueue.pop(); // удаляем один элемент в очереди
    cout << "\nТеперь в очереди остался один элемент: " << myQueue.front();
    return 0;
}

Вот вывод результата работы программы:

Количество элементов в очереди: 2 
Вот они: No pain - no gain 
Теперь в очереди остался один элемент: - no gain

Программа получилась достаточно простой, а значит — понятной, особенно для тех, кто уже знает что такое очереди и как с ними работать. Давайте вкратце пройдемся по коду. В данной программе, мы воспользовались заголовочным файлом (строка 2) для того, чтобы объявить очередь — строка 8. Мы объявили шаблон очереди с типом данных string, это было сделано для того, чтобы можно было сохранять слова как отдельный элемент очереди. В строках 10-11 воспользовавшись операцией push(), в пустую очередь было добавлено два элемента. После этого в строке 14, узнаем размер очереди, воспользовавшись операцией size(). В строке 15, мы выводим два элемента очереди на экран, с помощью функций front(), back(). Хочу обратить ваше внимание на то, что кроме функций front() и back(), в очереди нет других способов получить доступ к элементам. Например вот такой способ вызовет ошибку:

for(int i = 0; i < myQueue.size(); i++) {
    cout << myQueue[i];
}

Текст ошибки будет примерно такой:

Ошибка возникает из-за того, что в контейнер очереди не перегружена операция индексирования. А значит получить произвольный доступ к элементам очереди не возможно. Кроме этого в queue нет итераторов begin() и end(), поэтому такой способ вывода элементов на экран тоже не сработает:

copy(myQueue.begin(), myQueue.end(), ostream_iterator<int>(cout," "));

Вот такие ошибки мы получим:

Поэтому, одновременно получить прямой доступ мы можем только к двум элементам очереди — первому и последнему, воспользовавшись методами front(), back(), запомните это и не делайте ошибок.

В природе существую еще и приоритетные очереди, по сути, это те же обычные очереди, только в приоритетных очередях порядок элементов определяется не по алгоритму FIFO (First in First Out — первый пришел — первый ушел), а по некоторому приоритету. То есть, в приоритетных очередях следующим элементом считается тот элемент, у которого самый максимальный приоритет.
Приоритетные очереди определены все в том же заголовочном файле — <queue>. Объявить приоритетную очередь можно следующим образом:

priority_queue<float> myPrQueue;

То есть, при объявлении приоритетной очереди используется класс priority_queue. Рассмотрим простой пример программы с использованием приоритетной очереди:

#include <iostream>
#include <queue>        // подключаем заголовочный файл очереди
using namespace std;

int main()
{
    priority_queue<float> myPrQueue;   // создаем пустую приоритетную очередь типа float

    // вставка в очередь несколько элементов типа float
    myPrQueue.push(12.45);
    myPrQueue.push(6.93);
    myPrQueue.push(-0.1);
    myPrQueue.push(26.93);
    myPrQueue.push(-3.03);

    cout << "Количество элементов в очереди: " << myPrQueue.size() << endl;
    cout << "Порядок элементов в приоритетной очереди: ";

    // выгружаем элементы очереди по одному, в порядке их приоритета
    while(!myPrQueue.empty()) {
        cout << myPrQueue.top() << " ";
        myPrQueue.pop();
    }
    return 0;
}

Так же как и в обычных очередях, с помощью метода push() в очередь добавляются новые элементы, строки 10-14. В строке 7, объявлена приоритетная очередь, пока еще пустая. По умолчанию, все элементы в приоритетной очереди сортируются по возрастанию, это видно в результате работы программы.

Количество элементов в очереди: 5 
Порядок элементов в приоритетной очереди: 26.93 12.45 6.93 -0.1 -3.03

То есть, самый первый элемент очереди считается тот, значение которого превосходит все остальные. Конечно же приоритет очереди можно поменять. В строках 20-23 выполняется вывод на экран каждого первого элемента очереди, после того как первый элемент в очереди был выведен на экран, он удаляется из очереди методом pop(), строка 22. И это происходит до тех пор пока в очереди не останется ни одного элемента. Кстати говоря, в приоритетных очередях нет методов front(), back(). Хотя есть метод top(), который аналогичен методу front().