Stive și cozi: principiile LIFO și FIFO explicate

Stiva și coada sunt două structuri de date simple, definite nu prin felul în care sunt memorate, ci prin regula după care adaugi și scoți elemente. Le întâlnești la BAC Informatică în mai multe forme: în simulări de operații de tipul „ce conține stiva după următoarea secvență”, în felul în care funcționează recursivitatea și backtracking-ul, sau în parcurgerea grafurilor. Odată ce înțelegi cele două reguli, LIFO și FIFO, totul devine mecanic.

Stiva: LIFO

O stivă funcționează după principiul LIFO (Last In, First Out): ultimul element adăugat este primul extras. Gândește-te la un teanc de farfurii: pui farfuria nouă deasupra și tot de deasupra o iei. Locul în care se fac toate operațiile se numește vârful stivei.

• push(x): adaugă x în vârful stivei;
• pop: elimină elementul din vârf;
• top: consultă elementul din vârf, fără să-l elimine.

Coada: FIFO

O coadă funcționează după principiul FIFO (First In, First Out): primul element adăugat este primul extras, exact ca la coada de la casa de marcat. Elementele intră pe la sfârșitul cozii și ies pe la început.

Simulare pas cu pas: aceeași secvență, două rezultate

Aplicăm aceeași secvență de operații întâi unei stive, apoi unei cozi, ambele inițial vide. „Adaugă” înseamnă push pentru stivă și adăugare la sfârșit pentru coadă; „extrage” înseamnă pop pentru stivă și eliminare de la început pentru coadă.

La final, stiva conține 1 și 5 (cu 5 în vârf), iar elementele au fost extrase în ordinea 2, 4, 3. Coada conține 4 și 5 (cu 4 la început), iar elementele au fost extrase în ordinea 1, 2, 3. Observă că la coadă elementele ies mereu în ordinea în care au intrat.

Implementarea cu vectori

În C++ poți implementa ambele structuri cu un vector obișnuit și unul sau doi indici.

Stiva

Folosești vectorul st și variabila vf, poziția vârfului. Stiva e vidă când vf == 0.

int st[1001], vf = 0;

st[++vf] = x;      // push(x): crește vârful, apoi pune x
vf--;              // pop: elementul din vârf este „uitat”
st[vf]             // top: elementul din vârf
vf == 0            // stiva este vidă

Coada

Folosești vectorul c și doi indici: prim (începutul) și ultim (sfârșitul). Coada e vidă când prim > ultim.

int c[1001], prim = 1, ultim = 0;

c[++ultim] = x;    // adăugare la sfârșit
prim++;            // eliminare de la început
c[prim]            // primul element din coadă
prim > ultim       // coada este vidă

Înainte de pop sau de eliminare verifici întotdeauna că structura nu e vidă. A extrage dintr-o stivă goală este o eroare clasică.

Aplicația 1: verificarea parantezelor

Problemă: un șir conține paranteze rotunde și pătrate. Sunt ele corect închise? De exemplu, ([()]) este corect, iar ([)] nu este, deși are câte o pereche din fiecare tip.

Ideea: parcurgi șirul; la o paranteză deschisă faci push; la una închisă, vârful stivei trebuie să fie paranteza deschisă de același tip, pe care o scoți. La final, stiva trebuie să fie goală.

#include <iostream>
using namespace std;

int main()
{
    char s[256], st[256];
    int vf = 0;
    bool corect = true;
    cin.getline(s, 256);
    for (int i = 0; s[i] != '\0' && corect; i++)
    {
        if (s[i] == '(' || s[i] == '[')
            st[++vf] = s[i];
        else if (s[i] == ')' || s[i] == ']')
        {
            char pereche;
            if (s[i] == ')')
                pereche = '(';
            else
                pereche = '[';
            if (vf == 0 || st[vf] != pereche)
                corect = false;
            else
                vf--;
        }
    }
    if (vf != 0)
        corect = false;
    if (corect)
        cout << "corect";
    else
        cout << "incorect";
    return 0;
}

Pentru ([)]: se pun în stivă ( și [; la ), vârful este [, nu (, deci programul afișează incorect. Pentru ([()]) fiecare paranteză închisă găsește perechea în vârf, stiva rămâne goală, iar programul afișează corect.

Aplicația 2: inversarea ordinii

Stiva inversează ordinea elementelor, iar asta o face utilă oriunde rezultatul se obține „de la coadă la cap”. Exemplu: la conversia lui 13 în baza 2, resturile împărțirilor succesive la 2 sunt, în ordine, 1, 0, 1, 1. Dacă le pui într-o stivă și apoi le scoți, obții 1, 1, 0, 1, adică exact scrierea corectă: 13 = 1101 în baza 2.

Unde mai apar stiva și coada

• Recursivitatea folosește o stivă de apeluri: fiecare apel nou este pus în vârf, iar întoarcerile se fac în ordine inversă. De aceea o funcție care afișează după apelul recursiv afișează valorile „invers”.
• Backtracking-ul își construiește soluția într-un vector numit chiar stivă: adaugă pe poziția următoare și, la blocaj, revine la poziția anterioară.
• Parcurgerea în lățime (BFS) a unui graf folosește o coadă: nodurile sunt vizitate în ordinea în care au fost descoperite.