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.
noexcept
A 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.