stack library (tsz. stack libraries)
std::stack egyszerű, de hatékony „Last In, First Out” (LIFO) működésű adatszerkezetet valósít meg. Gyakran használjuk ideiglenes tárolásra, visszalépési (undo) műveletekhez, rekurzió helyettesítésére, grammatikai elemzésnél, gráfalgoritmusoknál (például mélységi bejárásnál) és még sok más esetben. Ebben a szövegben részletesen bemutatjuk a <stack> fejléc alatti osztályt, annak lehetőségeit, belső működését, testreszabási lehetőségeit és legjobb gyakorlatait.
std::stack definíciója és alapokA std::stack tulajdonképpen egy konténeradapter, ami azt jelenti, hogy nem önálló tároló, hanem belsőleg egy másik konténert használ (deklarált alapértelmezésben std::deque), és annak egyes metódusaira épít.
#include <stack>
std::stack<T, Container> myStack;
back(), push_back(), pop_back() műveleteket). Alapértelmezetten std::deque<T>.
A Standard Library konténerek (vector, deque, list stb.) általános célúak, míg a konténeradapterek (stack, queue, priority_queue) szűkebb, jól definiált interfészt biztosítanak, így egyértelműbb a használatuk és a kód olvashatóbbá válik.
„Last In, First Out”: az utoljára betett elem kerül először kiolvasásra. Ennek megfelelően a push() mindig a konténer hátuljára helyezi az elemet, a top() a hátulsó elemet adja vissza, a pop() pedig eltávolítja azt.
| Metódus | Leírás | Időkomplexitás |
|---|---|---|
bool empty() const noexcept;
|
Megmondja, hogy üres-e a verem. | O(1) |
size_type size() const noexcept;
|
Visszaadja a verem elemeinek számát. | O(1) |
reference top(); const_reference top() const;
|
Referenciával visszaadja a verem tetején álló elemet (nem távolítja el). | O(1) |
void push(const value_type& value);
|
Másolással (copy) beszúr egy új elemet a verem tetejére. | Amortizált O(1) |
void push(value_type&& value);
|
Mozgatással (move) beszúr egy elemet. | Amortizált O(1) |
template <class... Args> void emplace(Args&&... args);
|
Helyben (in-place) építi az elemet a verem tetején. | Amortizált O(1) |
void pop() noexcept;
|
Eltávolítja a verem tetején lévő elemet (nem ad vissza értéket). | O(1) |
void swap(stack& other) noexcept;
|
Gyorsan felcseréli két verem tartalmát (általában pointer-szintű swap). | O(1) (amortizált) |
std::stack<int> s;
s.push(10);
s.push(20);
std::cout << s.top(); // 20
s.pop();
std::cout << s.top(); // 10
emplace() vs. push()push() előbb létrehozza az objektumot (vagy másolja), majd beteszi.emplace() közvetlenül a belső konténer hátsó pozícióján építi fel az objektumot, így elkerülhető egy felesleges másolás vagy mozgatás.
Bár alapértelmezettként std::deque<T>-t használ, helyettesíthetjük std::vector<T>-tel vagy akár std::list<T>-tel is, ha speciális viselkedést akarunk:
#include <vector>
std::stack<int, std::vector<int>> vecStack;
vecStack.push(1);
vecStack.pop();
Mire figyeljünk?
std::vector esetén a push_back amortizált O(1), de újraallokációkor O(n).std::list teljesen biztonságos O(1)-es push_back és pop_back, viszont nagyobb memóriaigény és nem cache-barát.
noexceptA std::stack metódusai általában noexcept-nek tekinthetők, ha a belső konténer megfelelően van definiálva. Például a pop() felügyelhető, hogy ne dobjon kivételt, a push() azonban a belső konténer push_back()-jétől függően dobhat memóriahiány (bad_alloc) kivételt.
Jó gyakorlat: ha lehet, használjunk emplace()-et, és kerüljük a felesleges másolásokat, hogy minimalizáljuk a kivételek kockázatát.
std::deque duplavégű sorozat, mely több kis memóriablokkot használ, stabil push_back/pop_back teljesítményt nyújt. A std::vector egyszerű tömb alapú, de újraallokálás esetén ideiglenesen kétszeres memóriahasználat szükséges.std::vector jobb, ha sorozatos hozzáférés van; std::deque kevésbé optimalizált, de rugalmasabb.move semantics) jelentősen csökkentheti a teljesítményhibákat, ezért érdemes push(T&&) vagy emplace() módszereket használni.
Rekurzió helyettesítése
std::stack<Node*> st;
st.push(root);
while (!st.empty()) {
auto node = st.top(); st.pop();
// feldolgozás
if (node->right) st.push(node->right);
if (node->left) st.push(node->left);
}
Undo/Redo mechanizmus Két verem: undoStack, redoStack.
Szöveg szerkesztők történet-kezelése
Számológép kifejezés-értékelés Operátor- és operandus-veremmel: shunting-yard algoritmus.
Max-stack: olyan verem, amely mindig tudja a jelenlegi maximális értéket. Két verem kombinációjával megvalósítható:
std::stack<int> mainSt, maxSt;
void push(int x) {
mainSt.push(x);
if (maxSt.empty() || x >= maxSt.top())
maxSt.push(x);
}
void pop() {
if (mainSt.top() == maxSt.top())
maxSt.pop();
mainSt.pop();
}
int getMax() { return maxSt.top(); }
Min-stack, priority-stack stb. a hasonló elven alapul.
std::stack egyszerű, de sokoldalú LIFO-adatszerkezet konténeradapter a C++ Standard Library-ben.std::deque, de testreszabható más típusokra (vector, list).empty(), size(), top(), push(), pop(), emplace(), swap().A std::stack használata egyszerűsíti a kódot, mivel elrejti a belső tárolás részleteit, és egyértelmű, jól definiált interfészt kínál. Modern C++-ban mindenképpen érdemes emplace()-et és move-szemantikát alkalmazni a hatékonyság és kivételbiztonság érdekében.