Очередь std::queue

Класс std::queue<T> представляет очередь - контейнер, который работает по принципу FIFO (first-in first-out или "первый вошел — первым вышел") — первым всегда извлекается первый добавленный элемент. То есть это контейнер, аналогичный стандартной очереди, которая часто встречается в нашей повседневной жизни.

Для работы со очередью надо подключать заголовочный файл <queue>. Определение пустой очереди:

#include <iostream>
#include <queue>

int main()
{
    std::queue<std::string> queue;  // пустая очередь
}

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

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

#include <iostream>
#include <queue>

int main()
{
    std::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::queue<std::string> queue;  // пустая очередь
    // добавляем три элемента
    queue.push("Tom");
    queue.push("Bob");
    queue.push("Sam");

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

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

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

#include <iostream>
#include <queue>

int main()
{
    std::queue<std::string> queue;  // пустая очередь
    queue.push("Tom");
    queue.push("Bob");
    queue.push("Sam");

    std::cout << "First: " << queue.front() << std::endl;   // First: Tom
    std::cout << "Last: " << queue.back() << std::endl;     // Last: Sam
}

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

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

queue.pop()

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

#include <iostream>
#include <queue>

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

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

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

Tom
Bob
Sam

Инициализация деком

Очередь можно инициализировать другой очередь. или деком (двусторонней очередью):

#include <iostream>
#include <queue>

int main()
{
    std::deque<std::string> people{"Tom", "Sam", "Bob"};
    std::queue<std::string> queue {people};

    while (!queue.empty())
    {
        std::cout << queue.front() << std::endl;
        queue.pop();
    }
}

Обмен элементами

С помощью функции swap() можно обменять элементы двух очередей:

#include <iostream>
#include <queue>

int main()
{
    std::queue<std::string> queue1 {std::deque<std::string>{"Alice", "Kate"}};

    std::queue<std::string> queue2;
    queue2.push("Tom");
    queue2.push("Bob");

    // обмен queue1 на queue2
    queue1.swap(queue2);
    // queue1 = {"Tom", "Bob"}
    // queue2 = {"Alice", "Kate"}
}