baner
home exercises theme

Stack

Wprowadzenie

Stack to typ kontenera w C++ działający w trybie LIFO (Last In, First Out). Oznacza to, że dodając i odczytując wartości ze stosu (stack), operacje te wykonywane są na elemencie znajdującym się na samej górze. Nie ma możliwości bezpośredniego dostępu do elementów znajdujących się niżej w strukturze.

Aby lepiej zrozumieć, jak działa stos, można przyrównać go do talii kart leżącej na stole. W tym przypadku można manipulować wyłącznie kartą znajdującą się na samej górze. Jeśli chcesz dostać się do kart znajdujących się niżej, musisz najpierw zdjąć karty znajdujące się wyżej.

Przykładowy kod z użyciem stack

#include <iostream> 
#include <stack>
using namespace std;
int main() {
    stack<int> stack;
    // Dodajemy wartości na stos za pomocą funkcji push
    stack.push(13);
    stack.push(42);
    stack.push(68);
    stack.push(2137);
    // Teraz stos wygląda w taki sposób: {13, 42, 68, 2137}
    return 0;
}

Funkcje

W kontenerze stack dostępnych jest kilka przydatnych funkcji:

  • empty() - zwraca informację, czy stos jest pusty (O(1)).
  • size() - zwraca liczbę elementów na stosie (O(1)).
  • top() - zwraca wartość elementu znajdującego się na górze stosu (O(1)).
  • push(v) - dodaje wartość v na górę stosu (O(1)).
  • pop() - usuwa element z góry stosu (O(1)).

Przykładowy kod z użyciem funkcji stosu

#include <iostream>
#include <stack>
using namespace std;
int main() {
    stack<int> stack;
    stack.push(13); // przy pomocy funkcji push dodajemy wartości na górę
    stack.push(42);
    stack.push(68);
    stack.push(2137);
    // teraz nasz stack wygląda w taki sposób {13,42,68,2137}
    cout << stack.size() << endl;  // wypisze 4
    cout << stack.empty() << endl;  // wypisze 0 czyli false
    stack.pop(); // teraz stack wygląda tak {13,42,68}
    cout << stack.top() << endl;  // wypisze 68
    cout << stack.size() << endl; // wypisze 3
    while (!stack.empty()) {
        stack.pop();
    }
    cout << stack.empty() << endl; // wypisze 1 czyli true
    return 0;  
}

Teraz wiesz czym jest stos!