std::stack w C++ – adapter stosu, implementacja LIFO i przydatne metody

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:

1. 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
2. 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
3. pop() – usuwa element z wierzchołka bez zwracania wartości. Wymaga wcześniejszego odczytu top();
   s.pop(); // Usuwa wierzchołek
4. top() – zwraca referencję do elementu na wierzchołku, pozwala na modyfikację wartości;
   s.top() = 99; // Modyfikuje wierzchołek
5. size() – zwraca liczbę elementów przechowywanych na stosie;
   cout << s.size(); // Np. 3 elementy
6. 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, lecz 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

1. Brak iteratorów – std::stack nie udostępnia iteratorów, uniemożliwiając przeglądanie elementów bez modyfikacji struktury;
2. 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, lecz 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++.