Ugrás a tartalomhoz

queue library

A Wikiszótárból, a nyitott szótárból

Angol


Főnév

queue library (tsz. queue libraries)

  1. (informatika) A C++ szabványos könyvtár (<queue>) egy „konténer-adapter”, amely FIFO (first-in, first-out) elven működő sorokat biztosít. Három fő osztályt tartalmaz:
  1. std::queue – egyszerű FIFO-sor
  2. std::priority_queue – prioritási sor (legnagyobb vagy legkisebb elem lerendezve)
  3. std::deque – nem közvetlenül sor, de az alapértelmezett tároló az előzőkhöz

Az alábbiakban áttekintjük mindhárom lehetőséget, belső működésüket, API-jukat, bonyolultsági osztályaikat, valamint tipikus felhasználási mintákat.


1. Általános elvek és a konténer-adapter modell

A konténer-adapterek olyan osztályok, amelyek mögött valamilyen másik konténer („alapkonténer”) áll, de csak egy szűkített, speciális API-t kínálnak. A <queue> esetében alapértelmezés szerint egy std::deque<T> szolgál háttértárolóként, de használhatunk std::vector<T>-et vagy akár std::list<T>-et is, ha az alapján például stabilabb iterációt vagy memóriakezelést szeretnénk.

Minden adapter – legyen az queue, priority_queue vagy a hozzájuk közeli stack – ugyanazokat az általános sablonszerkezetet követi:

template<
    class T,
    class Container = std::deque<T>
> class queue;

template<
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>
> class priority_queue;

A paraméterek:

  • T: a tárolt típus
  • Container: a háttérkonténer típusa
  • Compare: a prioritásnál használt komparátor (nagyobb vagy kisebb elem kerüljön előre)


2. std::queue – egyszerű FIFO-sor

2.1 Konstruktorok és destruktor

  • Alapértelmezett konstruktor létrehoz egy üres, Container típusú tárolót.
  • Másoló- és mozgatókonstruktor, valamint értékadó operátorok a háttérkonténer azonos konstrukciós lehetőségeit öröklik.
  • A destruktor a tárolt objektumok destruktorát hívja meg.

2.2 Főbb műveletek

Függvény Leírás Amortizált bonyolultság
empty() Igazzal tér vissza, ha nincs elem O(1)
size() A sorban levő elemek száma O(1)
front(), back() Referencia az első/utolsó elemre O(1)
push(const T&) Elem beszúrása a sor végére Amortizált O(1)
emplace(Args&&…) Helyben konstruálás a végén Amortizált O(1)
pop() Az első elem eltávolítása O(1)
swap(queue&) Két sor tartalmának hatékony felcserélése O(1)

2.3 Használati példa

#include <queue>
#include <iostream>

int main() {
    std::queue<int> q;
    for (int i = 1; i <= 5; ++i) {
        q.push(i);
    }
    while (!q.empty()) {
        std::cout << q.front() << ' ';
        q.pop();
    }
    return 0;
}
// Kimenet: 1 2 3 4 5

Tipikus alkalmazások: szélességi keresés grafokban (BFS), üzenetsorok, producer–consumer minták.


3. std::priority_queue – prioritás szerinti sor

A prioritási sor esetén az elemek sorrendje nem a beszúrás sorrendjét követi, hanem a legmagasabb (vagy legalacsonyabb) prioritásút adjuk vissza. Az alapértelmezett Compare = std::less<> esetén a legnagyobb elem a „front”.

3.1 Konstruktorok

  • Üres sor, adott komparátorral
  • Tartalommal inicializálás tetszőleges iterátorpárral: azonnali heap kiépítéssel (O(n))

3.2 Főbb műveletek

Függvény Leírás Bonyolultság
empty(), size() Sor üres-e, elemszám O(1)
top() Legnagyobb/legkisebb elem O(1)
push(const T&) Elem beszúrása – heapify-up O(log n)
emplace(Args&&…) Helyben konstruálás + heapify-up O(log n)
pop() Top eltávolítása – heapify-down O(log n)
swap() Hatékony csere O(1)

3.3 Komparátor testreszabása

struct MinCompare {
    bool operator()(int a, int b) const {
        return a > b; // kisebb elem kerüljön felülre
    }
};

std::priority_queue<int, std::vector<int>, MinCompare> minHeap;

3.4 Alkalmazási területek

  • Dijkstra- és A* algoritmusok (gráfokban), ahol a következő feldolgozandó csúcs prioritása a távolság
  • Heurisztikus eseménykezelés
  • Scheduling algoritmusok, ahol a magasabb prioritású feladatokat előbb indítjuk el


4. A háttérkonténer kiválasztása

Mind a std::queue, mind a std::priority_queue esetén megadható a tároló típusa. A főbb szempontok:

  • std::deque<T>: általános, hatékony mindkét végén végzett beszúrás/eltávolítás (O(1)). Alapértelmezett mindkét adapterhez.
  • std::list<T>: garantált O(1) beszúrás/eltávolítás akár középen is, de nincs véletlen elérés. Akkor érdemes, ha iteratorok stabilitása fontos, vagy gyakori a középre szúrás.
  • std::vector<T>: ha ritkán vagy soha nem távolítunk elemeket a közepéről, és a memória tömörsége (cache-hatékonyság) fontos. A std::priority_queue alapértelmezettje.

Példa: std::queue<int, std::list<int>> qlist;


5. Teljesítmény és komplexitás

  • std::queue: minden művelet amortizált O(1). A pop() és push() garantáltan konstans idő alatt fut deque-szel és list-tel.
  • std::priority_queue: beszúrás és törlés O(log n), a kiolvasás (top()) O(1). Kezdő heap-építés (iterátorból) O(n).

Gyakorlati tanács: ha gyakran kell a legkisebb értéket kivenni, akkor fordítsuk meg a Compare-t, hogy a kisebb felkerüljön a gyökérre, így szintén O(log n).


6. Esettanulmány: BFS gráfkeresés std::queue-vel

#include <vector>
#include <queue>
#include <iostream>
using Graph = std::vector<std::vector<int>>;

void BFS(const Graph& g, int start) {
    std::vector<bool> visited(g.size(), false);
    std::queue<int> q;
    visited[start] = true;
    q.push(start);

    while (!q.empty()) {
        int u = q.front(); q.pop();
        std::cout << u << ' ';
        for (int v : g[u]) {
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
            }
        }
    }
}

int main() {
    Graph g = {{1,2}, {0,3}, {0,3}, {1,2}};
    BFS(g, 0); // Kimenet: 0 1 2 3
}

Ebben a példában a std::queue biztosítja, hogy mindig azokat a csúcsokat dolgozzuk fel először, amelyek a legrövidebb úton érhetők el a kezdőponttól.


7. Esettanulmány: Dijkstra algoritmus std::priority_queue-vel

#include <vector>
#include <queue>
#include <limits>
#include <iostream>
using pii = std::pair<int,int>; // {távolság, csúcs}

void dijkstra(const std::vector<std::vector<pii>>& adj, int src) {
    int n = adj.size();
    std::vector<int> dist(n, std::numeric_limits<int>::max());
    dist[src] = 0;

    std::priority_queue<pii, std::vector<pii>, std::greater<pii>> pq;
    pq.push({0, src});

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;
        for (auto [w, v] : adj[u]) {
            if (dist[v] > d + w) {
                dist[v] = d + w;
                pq.push({dist[v], v});
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        std::cout << "dist[" << i << "] = " << dist[i] << "\n";
    }
}

int main() {
    std::vector<std::vector<pii>> adj = {
        {{1,1},{4,2}}, {{1,0},{2,2},{6,3}}, {{4,0},{2,1},{3,3}}, {{6,1},{3,2}}
    };
    dijkstra(adj, 0);
}

Az iteratív heap műveletek összessége garantálja az O((V+E) log V) futási időt.


8. Összefoglalás

  • std::queue: egyszerű FIFO-sor, amortizált O(1) minden alapművelet.
  • std::priority_queue: prioritási sor, O(log n) beszúrás és törlés, O(1) top().
  • Háttérkonténer testreszabható deque, vector, list alapján, az igényeink szerint.
  • Gyakori felhasználási területek: grafalgoritmusok (BFS, Dijkstra), üzenetkezelés, task scheduling, eseménykezelés.

A <queue> könyvtár jól átgondolt, egyszerű API-val és garantált teljesítménnyel segít a sorok biztonságos és hatékony kezelésében.


További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=queue_library&oldid=3494568”