Stiva std::stack

Clasa std::stack<T> reprezintă o stivă – o structură de date care funcționează după principiul LIFO (last-in, first-out – „ultimul intrat, primul ieșit”) — întotdeauna se extrage primul elementul adăugat cel mai recent. Stiva poate fi comparată cu o grămadă de obiecte, de exemplu, o grămadă de farfurii – farfuriile se adaugă deasupra, fiecare farfurie nouă se pune peste cea precedentă. Iar dacă trebuie să luăm o farfurie, se ia mai întâi cea de deasupra (cea adăugată ultima).

Pentru a lucra cu o stivă trebuie inclus fișierul antet <stack>. Definirea unei stive goale:

#include <iostream>
#include <stack>
 
int main()
{
    std::stack<std::string> stack;    // stivă goală de șiruri de caractere
}

Dimensiunea stivei

Cu ajutorul funcției size() putem obține numărul de elemente din stivă, iar cu empty() putem verifica dacă stiva este goală (dacă returnează true, atunci stiva nu conține elemente):

#include <iostream>
#include <stack>
 
int main()
{
    std::stack<std::string> stack;
    if(stack.empty())
    {
        std::cout << "stack is empty" << std::endl;
    }
    std::cout << "stack size: " << stack.size() << std::endl; // stack size: 0
}

Adăugarea elementelor

Pentru a adăuga elemente în stivă se folosește funcția push(), căreia i se transmite elementul de adăugat:

#include <iostream>
#include <stack>
 
int main()
{
    std::stack<std::string> stack;
    // adăugăm trei elemente
    stack.push("Tom");
    stack.push("Bob");
    stack.push("Sam");
 
    std::cout << "stack size: " << stack.size() << std::endl; // stack size: 3
}

Obținerea elementelor

Putem obține doar elementul din vârful stivei – pentru aceasta se folosește funcția top():

#include <iostream>
#include <stack>
 
int main()
{
    std::stack<std::string> stack;
    stack.push("Tom");
    stack.push("Bob");
    stack.push("Sam");
    std::cout << "Top: " << stack.top() << std::endl;   // Top: Sam
}

În acest caz, după adăugarea celor trei elemente, stiva va arăta astfel:

-------
| Sam |
-------
| Bob |
-------
| Tom |
-------

În vârful stivei se află ultimul element adăugat. Cu ajutorul funcției top() putem accesa acest element.

Ștergerea elementelor

Pentru ștergere se folosește funcția pop(). Ștergerea se face în ordinea inversă adăugării:

stack.pop();

Combinând această funcție cu top() putem extrage toate elementele din stivă:

#include <iostream>
#include <stack>
 
int main()
{
    std::stack<std::string> stack;
    stack.push("Tom");
    stack.push("Bob");
    stack.push("Sam");
 
    while (!stack.empty())  // cât timp stiva nu este goală
    {
        std::cout << stack.top() << std::endl;
        stack.pop();    // extragem elementul din vârf
    }
}

În acest caz, cât timp stiva nu este goală, se afișează în consolă elementul din vârf (ultimul adăugat) folosind top() și apoi este eliminat cu pop(). Ieșirea în consolă a programului:

Sam  
Bob  
Tom

Inițializarea cu un deque

Stiva poate fi inițializată și cu o altă stivă sau cu un deque (coadă dublu-extremă):

#include <iostream>
#include <stack>
 
int main()
{
    std::deque<std::string> users{"Tom", "Sam", "Bob"};
    std::stack<std::string> stack {users};
 
    while (!stack.empty())
    {
        std::cout << stack.top() << std::endl;
        stack.pop();
    }
}