`std::queue` în C++

Adaptoare: stack, queue, priority_queue C++98

Coadă (FIFO): adaugi la coadă cu push și servești de la început cu front și pop.

Sintaxă

#include <queue>

std::queue<T> nume;
void push(const T& valoare);
void pop();
T& front();
T& back();

Ce face `std::queue`

std::queue funcționează ca un rând la casă: primul venit este primul servit (first in, first out). push(x) adaugă la sfârșit, front() returnează primul element, back() ultimul, iar pop() îl scoate pe primul.

Ca și std::stack, este un adaptor peste std::deque și nu poate fi parcurs. pop() nu returnează nimic, iar front() pe o coadă goală este comportament nedefinit.

Parametri

Parametru	Descriere
`valoare`	Pentru `push`: elementul pus la sfârșitul cozii.

Ce returnează

front()/back(): referință la primul/ultimul element. push, pop: nimic.

Exemple

Exemplul 1: Rândul la ghișeu

#include <print>
#include <queue>
#include <string>

int main() {
    std::queue<std::string> rand;
    rand.push("Ana");
    rand.push("Ion");
    rand.push("Maria");
    std::println("Primul: {}, ultimul: {}", rand.front(), rand.back());

    while (!rand.empty()) {
        std::println("Servim pe {} ({} în așteptare)", rand.front(), rand.size() - 1);
        rand.pop();
    }
}

Rezultat

Primul: Ana, ultimul: Maria
Servim pe Ana (2 în așteptare)
Servim pe Ion (1 în așteptare)
Servim pe Maria (0 în așteptare)

Exemplul 2: Parcurgere în lățime (BFS) pe o rețea de orașe

Coada procesează orașele în ordinea descoperirii, deci pe niveluri: întâi vecinii direcți, apoi vecinii lor.

#include <map>
#include <print>
#include <queue>
#include <set>
#include <string>
#include <vector>

int main() {
    std::map<std::string, std::vector<std::string>> drumuri{
        {"Iași", {"Suceava", "Bacău"}}, {"Suceava", {"Cluj"}},
        {"Bacău", {"Brașov"}}, {"Brașov", {"Cluj", "București"}},
    };
    std::queue<std::string> de_vizitat;
    std::set<std::string> vazute{"Iași"};
    de_vizitat.push("Iași");
    while (!de_vizitat.empty()) {
        std::string oras = de_vizitat.front();
        de_vizitat.pop();
        std::print("{} ", oras);
        for (const auto& vecin : drumuri[oras]) {
            if (vazute.insert(vecin).second) {
                de_vizitat.push(vecin);
            }
        }
    }
    std::println();
}