Как работает std::queue в C++? push/pop/front выдают не то, что я жду
Пишу BFS по графу, нужна обычная очередь (FIFO). Взял std::queue, но запутался с методами:
#include <queue>
queue<int> q;
q.push(1); q.push(2); q.push(3);
int x = q.pop(); // ошибка компиляции!
Почему pop() не возвращает значение? И как тогда правильно достать элемент из очереди? Где front, где back, и в каком порядке всё это извлекается?
2 ответа
Классическая ошибка. В std::queue метод pop() ничего не возвращает (тип void), он только удаляет первый элемент. Чтобы прочитать элемент, используй front() — а удаление это отдельный шаг.
Очередь работает по принципу FIFO (первый зашёл — первый вышел). Корректный код:
#include <iostream>
#include <queue>
using namespace std;
int main() {
queue<int> q;
q.push(1); // добавляем в конец
q.push(2);
q.push(3);
while (!q.empty()) {
int x = q.front(); // читаем первый
q.pop(); // удаляем первый
cout << x << " "; // 1 2 3 — в порядке добавления
}
return 0;
}
Все методы:
q.push(x)— добавить в конецq.front()— посмотреть первый (тот, что выйдет следующим)q.back()— посмотреть последнийq.pop()— удалить первыйq.empty()— пустая лиq.size()— размер
Типичный шаблон обхода: while (!q.empty()) { auto v = q.front(); q.pop(); /* обработка v */ }. Именно так пишется BFS.
Если тебе нужна очередь, из которой можно удалять с обоих концов (для алгоритмов вроде 0-1 BFS или скользящего минимума), смотри в сторону std::deque:
#include <deque>
deque<int> dq;
dq.push_back(1);
dq.push_front(0);
dq.pop_front();
dq.pop_back();
Обычный queue под капотом и так использует deque, просто ограничивает интерфейс.
