std::stack
De klasse std::stack<T> in <stack> is de STL-implementatie van een
stapel (Eng. stack) of LIFO-structuur ("last in first out").
Elementen worden toegevoegd met push(x) en verwijderd met pop().
Opgelet: in tegenstelling tot implementaties in andere talen/bibliotheken geeft pop()
hier geen waarde terug (void-functie of procedure).
Je kunt een referentie naar het laatst toegevoegde element krijgen via top().
Men heeft voor een referentie gekozen uit efficiëntie-overwegingen
(stel je voor dat T een "groot" datatype is).
Een voorbeeldje:
stack<string> stapel;
stapel.push("een");
stapel.push("twee");
stapel.push("drie");
cout << stapel.top() << endl; // "drie"
stapel.pop(); // verwijdert "drie"
stapel.top() = "deux"; // referentie is ook bruikbaar als linkerlid!
Andere nuttige methodes zijn empty() en size(). Er is geen clear().
In de STL-documentatie noemt men stack een container adaptor.
Dat is een container die steunt op een onderliggende container en de mogelijkheden
ervan beperkt (in dit geval) of uitbreidt.
Bij stack kun je het type van de onderliggende container kiezen, maar het moet een back-insertion sequence
zijn, die methodes back(), push_back() en pop_back() implementeert,
liefst (geamortizeerd) in O(1). Voorbeelden zijn vector, list en deque
(dit is de default). In principe is slist ook een goede kandidaat (vooraan toevoegen), maar die voldoet niet aan de back-insertion eisen.
Voorbeeld:
stack<,string, list<string> > stapel;
Merk op dat het onmogelijk is om te itereren over alle elementen zonder de stapel af te breken.
Als je dit nodig hebt, moet je rechtstreeks gebruik maken van een back-insertion sequence zoals vector.
std::queue
De klasse std::queue<T> in <queue> implementeert een wachtrij of FIFO-structuur ("first in first out").
Zoals stack is het een container adaptor die de mogelijkheden van de achterliggende container beperkt.
De achterliggende container moet in dit geval zowel een front-insertion als een back-insertion zijn.
De afspraak is dat elementen "achteraan" toegevoegd worden met push(x) en "vooraan" afgehaald met pop() (opnieuw void!) Je kunt een referentie krijgen naar het voorste element met front()
(dus niet top() !!) en naar het achterste element met back().
Deze operaties gebeuren, afhankelijk van de onderliggende implementatie, (geamortizeerd) in O(1).
queue<string> rij;
rij.push("een");
rij.push("twee");
rij.push("drie");
cout << rij.front() << endl; // "een"
rij.pop(); // verwijdert "een"
rij.top() = "deux"; // referentie is ook bruikbaar als linkerlid!
std::priority_queue
De klasse std::priority_queue<T>implementeert een prioriteitswachtrij.
De interface is dezelfde als bij stack.
Het top-element is nu echter (op elk moment) het grootste element.
Merk op dat de klasse in <queue> gedefinieerd wordt.
De prioriteitswachtrij steunt intern op een binaire heap die geïmplementeerd wordt in een vector.
De operaties push() en pop() gebeuren in O(log(N)), top() in O(1).
Belangrijk is dat operator< moet gedefinieerd zijn voor het type T.
Is dit niet het geval, of wil men een niet-standaard orde, dan kan men als extra argument een comparator meegeven.
(zie sorteren)
Voorbeeld:
priority_queue<int> pq; pq.push(10); pq.push(12); pq.push(8); cout << pq.top() << endl; // 12 pq.pop(); cout << pq.top() << endl; // 10 pq.pop(); cout << pq.top() << endl; // 8 pq.pop();
Als je het sorteercriterium wil omdraaien (top is telkens het kleinste element), dan kan dit bv. zo
priority_queue<int, vector<int>, greater<int> > priorrij;Opm.
greater wordt gedefinieerd in <functional>, wat meestal automatisch geïncludeerd wordt door andere container-headers. Aangezien de comparator de derde template-parameter is moet je wel de onderliggende container (de tweede parameter) opgeven, hier vector<int>.
Hetzelfde kan ook met een functie:
bool omgekeerd(int a, int b) {
return a > b;
}
void foo() {
priority_queue<int, vector<int>, bool(*)(int, int)> pq(omgekeerd);
...
}
De comparator (hier een functie) wordt aan de constructor meegegeven. Let op het derde template-argument:
dit is de signatuur van een functie-pointer!!
Meestal maakt men een hulpklasse als comparator:
struct Andersom {
bool operator()(int a, int b) {
return a > b;
}
};
void foo() {
Andersom a;
priority_queue<int, vector<int>, Andersom> pq1(a);
...
// ofwel:
priority_queue<int, vector<int>, Andersom> pq2; // default Andersom ctor
}
Voor de eenvoud is voor een struct gekozen, wat identiek hetzelfde is als een class met publieke velden.
Een priority_queue<string> sorteert de strings lexicaal ("aap" < "noot" en "AAP" < "aap"...).
Zoals bij stack en queu kun je bij priority_queue niet aan de onderliggende representatie. Indien je meer controle nodig hebt kun je "zelf" een prioriteitswachtrij maken, bv. met een vector, gebruik makende van de heap-operaties
push_heap(), pop_heap(), make_heap(), sort_heap() en is_heap(), gedefinieerd in <algorithm>.
[W. Schepens okt. 2008]