`std::stack` în C++

Adaptoare: stack, queue, priority_queue C++98

Stivă (LIFO): adaugi deasupra cu push, citești vârful cu top și îl scoți cu pop.

Sintaxă

#include <stack>

std::stack<T> nume;
void push(const T& valoare);
void pop();
T& top();

Ce face `std::stack`

std::stack permite doar operațiile unei stive: ultimul element pus este primul scos (last in, first out), ca un teanc de farfurii. push(x) pune x deasupra, top() returnează elementul de deasupra, pop() îl scoate. Mai ai empty(), size() și emplace().

Este un adaptor: folosește în spate alt container (implicit std::deque; poți alege std::vector: std::stack<int, std::vector<int>>) și ascunde restul operațiilor. Nu poți parcurge o stivă cu for și nici accesa elemente din mijloc.

pop() nu returnează elementul scos: citește-l întâi cu top(). Pe o stivă goală, top() și pop() sunt comportament nedefinit.

Parametri

Parametru	Descriere
`valoare`	Pentru `push`: elementul pus în vârful stivei.

Ce returnează

top(): referință la vârf. push și pop: nimic.

Exemple

Exemplul 1: push, top, pop

#include <print>
#include <stack>
#include <string>

int main() {
    std::stack<std::string> farfurii;
    farfurii.push("albastră");
    farfurii.push("verde");
    farfurii.push("roșie");
    std::println("Deasupra: {} (în total {})", farfurii.top(), farfurii.size());

    while (!farfurii.empty()) {
        std::println("Spăl farfuria {}", farfurii.top());
        farfurii.pop();
    }
}

Rezultat

Deasupra: roșie (în total 3)
Spăl farfuria roșie
Spăl farfuria verde
Spăl farfuria albastră

Exemplul 2: Verificarea parantezelor

Fiecare paranteză deschisă se pune pe stivă; o paranteză închisă trebuie să se potrivească cu vârful stivei.

#include <print>
#include <stack>
#include <string_view>

bool echilibrat(std::string_view expresie) {
    std::stack<char> deschise;
    for (char c : expresie) {
        if (c == '(' || c == '[' || c == '{') {
            deschise.push(c);
        } else if (c == ')' || c == ']' || c == '}') {
            if (deschise.empty()) {
                return false;
            }
            char d = deschise.top();
            deschise.pop();
            if ((c == ')' && d != '(') || (c == ']' && d != '[') || (c == '}' && d != '{')) {
                return false;
            }
        }
    }
    return deschise.empty();
}

int main() {
    for (auto e : {"(2 + 3) * [4 - 1]", "{[(x)]}", "(a + b]", "((1)"}) {
        std::println("{:<18} {}", e, echilibrat(e) ? "corect" : "greșit");
    }
}