queue library (tsz. queue libraries)
<queue>) egy „konténer-adapter”, amely FIFO (first-in, first-out) elven működő sorokat biztosít. Három fő osztályt tartalmaz:std::queue – egyszerű FIFO-sorstd::priority_queue – prioritási sor (legnagyobb vagy legkisebb elem lerendezve)std::deque – nem közvetlenül sor, de az alapértelmezett tároló az előzőkhözAz 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.
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ípusContainer: a háttérkonténer típusaCompare: a prioritásnál használt komparátor (nagyobb vagy kisebb elem kerüljön előre)
std::queue – egyszerű FIFO-sor
Container típusú tárolót.
| 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) |
#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.
std::priority_queue – prioritás szerinti sorA 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”.
| 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) |
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;
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;
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).
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 = true;
q.push(start);
while (!q.empty()) {
int u = q.front(); q.pop();
std::cout << u << ' ';
for (int v : g) {
if (!visited) {
visited = 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.
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 = 0;
std::priority_queue<pii, std::vector<pii>, std::greater<pii>> pq;
pq.push({0, src});
while (!pq.empty()) {
auto = pq.top(); pq.pop();
if (d > dist) continue;
for (auto : adj) {
if (dist > d + w) {
dist = d + w;
pq.push({dist, v});
}
}
}
for (int i = 0; i < n; ++i) {
std::cout << "dist = " << dist << "\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.
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().deque, vector, list alapján, az igényeink szerint.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.