Очередь (queue) в C++: std::queue, приоритетная очередь и своя реализация на массиве

Очередь (queue) — это структура данных, которая отдает элементы в порядке FIFO (first in — first out, «первым пришел — первым ушел»): извлечь можно только тот элемент, который добавили раньше всех остальных, сохранившихся в очереди. В C++ есть готовый контейнер-адаптер std::queue, приоритетная очередь std::priority_queue и способ собрать очередь вручную на массиве. Разберем все три варианта на рабочих примерах, сравним их и разберем типичную ошибку ручной реализации.

Очередь, стек и дек: в чем разница

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

• Стек (stack) — работает по принципу LIFO (last in — first out): последним добавленный элемент извлекается первым. В C++ это std::stack.
• Дек (deque, double-ended queue) — позволяет добавлять и удалять элементы с обоих концов за O(1) и, в отличие от очереди, дает произвольный доступ по индексу через operator[].
• std::queue — это не отдельная структура данных, а контейнер-адаптер: обертка, которая ограничивает интерфейс нижележащего контейнера (по умолчанию std::deque) до операций push/pop/front/back, скрывая произвольный доступ.

Если в коде нужен доступ по индексу или проход по элементам в обе стороны, std::queue не подойдет — берите std::deque напрямую.

std::queue: интерфейс и пример

Очередь в C++ объявляется так: std::queue<T> q;, где T — тип элементов, а заголовок для подключения — <queue>. По умолчанию std::queue хранит данные в std::deque, но можно указать другой контейнер вторым параметром шаблона, например std::queue<int, std::list<int>>.

Методы, с которыми реально работают:

Важная деталь, которую часто путают: pop() не возвращает удаляемое значение (в отличие, например, от pop() в некоторых других языках). Чтобы получить значение и удалить его, сначала вызывают front(), потом pop().

Полный рабочий пример:

#include <iostream>
#include <queue>

int main() {
    std::queue<int> q;
    q.push(10);
    q.push(20);
    q.push(30);

    std::cout << "front: " << q.front() << std::endl;
    std::cout << "back: " << q.back() << std::endl;

    q.pop();
    std::cout << "after pop, front: " << q.front() << std::endl;
    std::cout << "size: " << q.size() << std::endl;
    std::cout << "empty: " << (q.empty() ? "true" : "false") << std::endl;

    return 0;
}

Результат в консоли:

front: 10
back: 30
after pop, front: 20
size: 2
empty: false

Порядок предсказуем: первым положили 10 — он же первым и front(), пока его не удалят через pop().

Приоритетная очередь: std::priority_queue

std::priority_queue — отдельная структура, а не разновидность FIFO: она выдает не «того, кто пришел раньше», а элемент с наибольшим приоритетом. По умолчанию это максимум по оператору < (через std::less), хранилище — бинарная куча поверх std::vector.

У приоритетной очереди нет front()/back() — только top(). Push и pop работают за O(log n) из-за восстановления свойства кучи, обращение к вершине — за O(1).

#include <iostream>
#include <queue>

int main() {
    std::priority_queue<int> pq;
    pq.push(5);
    pq.push(1);
    pq.push(9);
    pq.push(3);

    while (!pq.empty()) {
        std::cout << pq.top() << " ";
        pq.pop();
    }
    std::cout << std::endl;

    return 0;
}

Результат:

9 5 3 1

Если нужна очередь с минимумом на вершине (min-heap), меняют компаратор и хранилище явно: std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq;. Такую конструкцию используют, например, в алгоритме Дейкстры для выбора вершины с минимальным текущим расстоянием.

Очередь на массиве: кольцевой буфер своими руками

STL доступен не везде: во встраиваемых системах или там, где нельзя аллоцировать память динамически, очередь реализуют вручную на массиве — это кольцевой буфер (circular buffer). Индексы начала и конца циклически «оборачиваются» через остаток от деления на емкость.

Частая ошибка — различать пустую и полную очередь только по равенству head == tail, без отдельного счетчика элементов:

// НЕВЕРНО: не различает "пусто" и "полностью заполнено"
class BadQueue {
public:
    explicit BadQueue(int cap) : data(new int[cap]), capacity(cap), head(0), tail(0) {}
    ~BadQueue() { delete[] data; }

    void push(int value) {
        data[tail] = value;
        tail = (tail + 1) % capacity;
    }

    bool empty() const { return head == tail; }

private:
    int* data;
    int capacity;
    int head;
    int tail;
};

int main() {
    BadQueue bq(3);
    bq.push(1);
    bq.push(2);
    bq.push(3); // tail снова стал равен 0, то есть head

    std::cout << (bq.empty() ? "empty" : "not empty") << std::endl;
    return 0;
}

Фактический результат:

empty

Хотя очередь заполнена под завязку, empty() вернул true: tail после третьей вставки совпал с head. Дальнейший push() молча перезапишет данные с начала буфера — это и есть баг, из-за которого в старой версии статьи ошибочно утверждалось, что «каждая новая запись заменяет последний элемент»: не свойство очереди, а следствие сломанной проверки заполненности.

Исправление — добавить отдельный счетчик элементов и проверять емкость явно:

#include <iostream>

class CircularQueue {
public:
    explicit CircularQueue(int cap)
        : data(new int[cap]), capacity(cap), head(0), tail(0), count(0) {}
    ~CircularQueue() { delete[] data; }

    bool push(int value) {
        if (count == capacity) return false; // очередь заполнена
        data[tail] = value;
        tail = (tail + 1) % capacity;
        ++count;
        return true;
    }

    bool pop() {
        if (count == 0) return false; // очередь пуста
        head = (head + 1) % capacity;
        --count;
        return true;
    }

    int front() const { return data[head]; }
    bool empty() const { return count == 0; }

private:
    int* data;
    int capacity;
    int head;
    int tail;
    int count;
};

int main() {
    CircularQueue q(3);
    q.push(1);
    q.push(2);
    q.push(3);

    std::cout << "push 4 into full queue: " << (q.push(4) ? "ok" : "queue full") << std::endl;
    std::cout << "front: " << q.front() << std::endl;

    q.pop();
    std::cout << "front after pop: " << q.front() << std::endl;
    std::cout << "push 4 after pop: " << (q.push(4) ? "ok" : "queue full") << std::endl;
    std::cout << "front stays: " << q.front() << std::endl;

    return 0;
}

Результат:

push 4 into full queue: queue full
front: 1
front after pop: 2
push 4 after pop: ok
front stays: 2

count однозначно определяет состояние: push()/pop() явно отказывают, когда это невозможно, вместо порчи данных.

Когда какую очередь выбрать

Выводы

• Очередь работает по принципу FIFO: первым добавленный элемент извлекается первым.
• std::queue — контейнер-адаптер над std::deque, дает только push/pop/front/back/empty/size, без доступа по индексу.
• std::priority_queue извлекает не по порядку добавления, а по приоритету, за O(log n) на бинарной куче.
• Ручная реализация на массиве (кольцевой буфер) требует отдельного счетчика элементов, иначе head == tail не различает пустую и полную очередь.
• Выбор структуры зависит от задачи: для приоритетов нужна std::priority_queue, для доступа по индексу — std::deque, для фиксированной памяти — свой кольцевой буфер.

Где применяется / связь с практикой

Очереди — одна из первых структур данных на пути разработчика C++: обработка событий, буферы сетевых пакетов, планировщики задач, обход графа в ширину (BFS) на std::queue, поиск кратчайшего пути (Дейкстра) на std::priority_queue. Разница между FIFO-очередью, приоритетной очередью и их устройством под капотом — база для более сложных структур и алгоритмов.

Смежные темы: Сортировка Хоара и другие способы сортировки массивов, Строки в C.

FAQ

Можно ли обратиться к элементу std::queue по индексу, как в массиве?
Нет, у std::queue нет operator[] — доступны только front() и back(). Если нужен произвольный доступ, используйте std::deque напрямую вместо адаптера.

Чем std::queue отличается от std::stack по устройству?
Оба — контейнеры-адаптеры над одним и тем же нижележащим контейнером (по умолчанию std::deque), различие только в наборе разрешенных операций: std::queue дает FIFO через push/front/back, std::stack — LIFO через push/top.

Как реализовать очередь в чистом C, где нет STL?
Так же, как кольцевой буфер выше, но без классов: структура с массивом, head, tail, count и обычные функции queue_push()/queue_pop(), принимающие указатель на структуру. Логика с остатком от деления и отдельным счетчиком элементов остается точно такой же.