15. STL. Queue / priority queue. Адаптеры контейнеров.

STL. Queue / priority queue. Адаптеры контейнеров.

Также как и stack очереди являются адаптерами для контейнеров, т.е. они изменяют обращение к памяти у контейнеров и некоторое использование методов, но сами по себе контейнерами не являются.

Очереди реализуют описанный ранее принцип:

• Простая очередь queue – первый вошел/первый вышел, она может работать с контейнерами list и deque, С ВЕКТОРОМ НЕ МОЖЕТ РАБОТАТЬ!!!
• Очередь с приоритетом priority queue – все вошли, первым вышел элемент с более высоким приоритетом, она может работать с контейнерами vector и deque, С LIST НЕ МОЖЕТ РАБОТАТЬ!!!

В основу простой очереди зачастую положен контейнер типа deque, в основе очереди с приоритетом обычно лежит вектор.
С дополнительными методами, поэтому зачастую (в некоторых средах) можно получить доступ к изначальному deque и иным контейнерам в обход стека.

Для работы необходимо подключить библиотеку
#include < queue >
Queue входит в пространство имен std, поэтому или пишем std:: или используем пространство имен using namespace std;

 

Методы в очередях похожи на методы в остальных шаблонах STL.
При работе стоит помнить, про принцип формирования очереди.

вход в очередь (back)->3->2->1->выход из очереди (.front/.top)

Простая очередь:

#include <deque>
#include <list>
#include <queue>
#include <functional> //для priority_queue и изменения принципа приоритезации

using namespace std;

//в функции main
    queue MyQueue;
    MyQueue.push(1);
    MyQueue.emplace(2);
    MyQueue.push(3);

    cout<<MyQueue.front()<<endl;    //позволяет работать (читать и перезаписывать) с первым элементом (#1)
    cout<<MyQueue.back()<<endl;     //позволяет работать (читать и перезаписывать) с последним элементом (#3)

    MyQueue.pop(); //ИЗВЛЕКАЕТ ПЕРВЫЙ элемент в очереди (#1)


    queue<int, list> MyQueueList;
    MyQueueList.push(1);
    MyQueueList.emplace(2);
    MyQueueList.push(3);

 

 

Очереди с приоритетом:
В очереди с приоритетом мы НЕ МОЖЕМ посмотреть последний элемент.

В STL по умолчанию элементы при добавлении в очередь выстраиваются по их приоритету, обычно по принципу БОЛЬШИЕ элементы в начало очереди, меньшие в конец.
т.е. при добавлении 1,4,3,2
очередь сформируется 1->2->3->4->выход из очереди (.top)

    priority_queue<int, vector> MyPQueue;
    MyPQueue.push(1);
    MyPQueue.push(4);
    MyPQueue.emplace(3);
    MyPQueue.push(2);


    cout<<endl<<"_____________________"<<endl;

    while (!MyPQueue.empty()) //выведет 4,3,2,1
    {
       cout<<MyPQueue.top()<<endl;
       MyPQueue.pop();
    }

Мы можем изменить приоритет очереди, используя шаблоны сравнения из файла <functional>, например greater или less

    priority_queue <int, vector , greater  > MyPQueue2;
    MyPQueue2.push(1);
    MyPQueue2.push(4);
    MyPQueue2.emplace(3);
    MyPQueue2.push(2);

    cout<<endl<<"_____________________"<<endl;

    while (!MyPQueue2.empty()) //выведет 1,2,3,4
    {
       cout<<MyPQueue2.top()<<endl;
       MyPQueue2.pop();
    }

Примечание:
Отдельно стоит отметить, что очереди не ограничиваются по размеру и выделяются в динамической памяти, поэтому:

1. Средняя скорость выборки элементов должна быть больше или равна скорости поступления элементов.
2. Желательно все-таки ограничивать поступление новых элементов в очередь/децимировать их при рассинхронизации поступления и обработки данных.