Kompleksowy przegląd std::stack w C++ – implementacja LIFO, metody i zastosowania
Stos (std::stack) to fundamentalna struktura danych w bibliotece standardowej C++, realizująca zasadę LIFO (Last-In, First-Out). Jako adapter kontenera, std::stack abstrahuje operacje na bazowym kontenerze (domyślnie std::deque), oferując minimalny interfejs do efektywnego zarządzania danymi w scenariuszach wymagających sekwencyjnego przetwarzania w odwróconej kolejności.
Implementacja LIFO
Mechanizm LIFO w std::stack polega na ograniczeniu operacji do jednego końca struktury danych:
- Wstawianie (push) – nowe elementy dodawane są wyłącznie na wierzchołek stosu;
- Usuwanie (pop) – elementy usuwane są wyłącznie z wierzchołka stosu;
- Dostęp (top) – jedynym elementem dostępnym bez modyfikacji struktury jest element wierzchołkowy.
Ta semantyka odwzorowuje zachowanie stosu fizycznego (np. stosu talerzy), gdzie ostatnio dodany element jest pierwszym do usunięcia.
Metody i ich zastosowania
Interfejs std::stack składa się z sześciu kluczowych metod:
- push(const Type& val) – dodaje element na wierzchołek stosu poprzez kopię lub przeniesienie;
std::stack<int> s;
s.push(42); // Wstawia 42 na wierzchołek - emplace(Args&&... args) – konstruuje element w miejscu na wierzchołku stosu, unikając kopiowania;
s.emplace(100); // Efektywniejsze niż push dla obiektów złożonych - pop() – usuwa element z wierzchołka bez zwracania wartości. Wymaga wcześniejszego odczytu top();
s.pop(); // Usuwa wierzchołek - top() – zwraca referencję do elementu na wierzchołku, pozwala na modyfikację wartości;
s.top() = 99; // Modyfikuje wierzchołek - size() – zwraca liczbę elementów przechowywanych na stosie;
cout << s.size(); // Np. 3 elementy - empty() – sprawdza obecność elementów na stosie. Zwraca true dla stosu pustego;
if (s.empty()) { /* ... */ } // Logika dla pustego stosu
Zaawansowane techniki
- Wybór kontenera bazowego – domyślnie std::stack wykorzystuje std::deque, ale możliwe jest zastosowanie alternatywnych kontenerów spełniających wymagania SequenceContainer (np. std::list, std::vector);
std::stack<int, std::list<int>> customStack; // Stos z listą jako kontenerem - Optymalizacje – emplace vs push: emplace unika tworzenia tymczasowych obiektów, redukując narzuty pamięciowe, swap(): zamienia zawartości dwóch stosów w czasie stałym O(1) poprzez wymianę wskaźników kontenerów bazowych.
Przykład praktyczny: odwracanie sekwencji
using namespace std; vector<int> reverseVector(const vector<int>& input) { stack<int> s; for (int elem : input) s.push(elem); // Wstawianie elementów vector<int> reversed; while (!s.empty()) { reversed.push_back(s.top()); // Pierwszy element: ostatni dodany s.pop(); } return reversed; // Zwraca odwrócony wektor }Ograniczenia i ostrzeżenia
- Brak iteratorów – std::stack nie udostępnia iteratorów, uniemożliwiając przeglądanie elementów bez modyfikacji struktury;
- Bezpieczeństwo wyjątków – metoda pop() nie zwraca wartości, by zagwarantować silną gwarancję wyjątków. Odczyt wymaga oddzielnego wywołania top().
Zastosowania w algorytmach
- Przeszukiwanie w głąb (DFS) – stos przechowuje wierzchołki do odwiedzenia;
- Ewaluacja wyrażeń – przetwarzanie notacji odwrotnej polskiej;
- Cofanie operacji – historia działania programu (np. mechanizm undo).
Podsumowanie
std::stack oferuje minimalistyczny, ale potężny interfejs dla struktur LIFO, będąc niezastąpionym narzędziem w scenariuszach wymagających sekwencyjnego przetwarzania danych w odwróconej kolejności. Elastyczność w doborze kontenera bazowego oraz wydajność operacji emplace i swap czynią ją kluczowym komponentem biblioteki standardowej C++.
