Stiva (Stack)

O stivă este o structură de date care funcționează pe principiul LIFO - Last In, First Out (ultimul intrat, primul ieșit).

Imaginează-ți un teanc de farfurii: pui o farfurie deasupra și o iei tot de deasupra. Nu poți scoate una din mijloc fără să le dai pe cele de deasupra la o parte.

Operații fundamentale

Exemplu vizual

push(3)    push(7)    push(2)    pop()      push(5)
                       
                      [2]                   [5]
           [7]        [7]        [7]        [7]
[3]        [3]        [3]        [3]        [3]

top = 3    top = 7    top = 2    top = 7    top = 5

Implementare pe vector

int stiva[100001];
int varf = 0;  // numărul de elemente

void push(int x) {
    varf++;
    stiva[varf] = x;
}

void pop() {
    if (varf > 0)
        varf--;
}

int top() {
    return stiva[varf];
}

bool empty() {
    return varf == 0;
}

varf indică poziția ultimului element. Stiva este goală când varf == 0.

Problema clasică: paranteze echilibrate

Verificăm dacă un șir de paranteze (, ), [, ], {, } este corect:

• Fiecare paranteză deschisă trebuie închisă cu tipul corect
• Parantezele trebuie să fie în ordine corectă

Exemple: - ([{}]) - corect - ([)] - greșit (ordinea nu e bună) - ((() - greșit (rămân paranteze deschise)

Ideea

Parcurgem șirul caracter cu caracter: - Dacă e paranteză deschisă: o punem pe stivă - Dacă e paranteză închisă: verificăm dacă vârful stivei conține perechea corectă

#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

char s[100001];
char stiva[100001];
int varf;

char pereche(char c) {
    if (c == ')') return '(';
    if (c == ']') return '[';
    if (c == '}') return '{';
    return 0;
}

int main()
{
    fin >> s;
    int lung = strlen(s);
    varf = 0;
    int ok = 1;

    for (int i = 0; i < lung && ok; i++) {
        char c = s[i];
        if (c == '(' || c == '[' || c == '{') {
            varf++;
            stiva[varf] = c;
        } else {
            if (varf == 0 || stiva[varf] != pereche(c))
                ok = 0;
            else
                varf--;
        }
    }

    if (varf != 0) ok = 0;

    if (ok) fout << "DA";
    else fout << "NU";

    return 0;
}

date.in:

([{}()])

date.out:

DA

Pas cu pas pentru ([{}()])

Stiva goală la final - corect.

Problema: cel mai apropiat element mai mic la stânga

Pentru fiecare element al vectorului, găsim cel mai apropiat element mai mic aflat la stânga lui.

Vector: 4 5 2 10 8
Răspuns: - 4 - 2  2

4 nu are nimic la stânga
5 → 4 (primul mai mic la stânga)
2 → nu are (e cel mai mic)
10 → 2 (cel mai mic la stânga)
8 → 2

Ideea

Menținem o stivă cu elementele “candidate”. Pentru fiecare element nou, scoatem din stivă tot ce e mai mare sau egal - rămâne în vârf răspunsul.

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int v[100001];
int stiva[100001];
int varf;
int n;

int main()
{
    fin >> n;
    for (int i = 1; i <= n; i++)
        fin >> v[i];

    varf = 0;

    for (int i = 1; i <= n; i++) {
        while (varf > 0 && stiva[varf] >= v[i])
            varf--;

        if (varf == 0)
            fout << -1 << " ";
        else
            fout << stiva[varf] << " ";

        varf++;
        stiva[varf] = v[i];
    }

    return 0;
}

date.in:

5
4 5 2 10 8

date.out:

-1 4 -1 2 2

Complexitate: O(n) - fiecare element intră și iese din stivă cel mult o dată.

Problema: evaluarea unei expresii în notație poloneză inversă

Notația poloneză inversă (postfix): 3 4 + 2 * înseamnă (3 + 4) * 2 = 14.

Regulă: când întâlnim un număr, îl punem pe stivă. Când întâlnim un operator, scoatem 2 numere, aplicăm operatorul, și punem rezultatul înapoi.

#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int stiva[100001];
int varf;
char token[101];

int main()
{
    varf = 0;

    while (fin >> token) {
        if (token[0] >= '0' && token[0] <= '9') {
            // E număr
            int nr = 0;
            for (int i = 0; token[i]; i++)
                nr = nr * 10 + (token[i] - '0');
            varf++;
            stiva[varf] = nr;
        } else {
            // E operator
            int b = stiva[varf]; varf--;
            int a = stiva[varf]; varf--;
            int rez = 0;
            if (token[0] == '+') rez = a + b;
            if (token[0] == '-') rez = a - b;
            if (token[0] == '*') rez = a * b;
            if (token[0] == '/') rez = a / b;
            varf++;
            stiva[varf] = rez;
        }
    }

    fout << stiva[varf];

    return 0;
}

date.in:

3 4 + 2 *

date.out:

14

Greșeli frecvente

1. Pop pe stivă goală

varf--; // dacă varf e 0, devine -1 - EROARE

Mereu verifică if (varf > 0) înainte de pop.

2. Uitarea verificării stivei la final (paranteze)

Dacă la finalul parcurgerii stiva nu e goală, mai sunt paranteze deschise fără pereche.

3. Confuzia ordinii la operatori

La notația poloneză inversă, ordinea contează: a - b nu e același lucru cu b - a. Primul scos din stivă e b (operandul drept).

Ce să reții

• Stiva funcționează LIFO: ultimul intrat, primul ieșit.
• Operații O(1): push, pop, top, empty.
• Implementare simplă pe vector cu variabila varf.
• Paranteze echilibrate: push la deschidere, pop + verificare la închidere.
• Element mai mic la stânga: stivă monotonă - O(n) total.
• Evaluare postfix: numere pe stivă, operatori scot 2 și pun rezultatul.

Probleme

pbinfoSkyline→

pbinfoParanteze1→

pbinfoPlaja→

pbinfoDepou→

pbinfoIzistack→