Ce este stiva ?

Stiva (sau „stack” in limba engleza) este o structură de date liniara ce lucreaza cu o colectie de date avand doua operatii principale:

• push(int numar) – adauga numar in stiva
• pop() – sterge ultimul element adaugat in lista (peek() – returneaza valoarea acestui element – deseori functia pop() contine si functia peek() integrata).

Modul in care acesta prelucreaza elementele i-a dat denumirea de LIFO ( Last In First Out=  ultimul venit-primul servit ).

Cum functioneaza stiva?

Avand in vedere ca este o structura de date secventiala, operatiile push si pop se intampla numai la capatul structurii (acest „capat” este numit top). Acest detaliu permite stivei sa fie implementata ca o lista simpla inlantuita. De mentionat este faptul ca stiva este o structura de date cu un numar total de elemente flexibil.

Stiva functioneaza pe principiul LIFO, imginati-va de exemplu mai multe farfurii expuse pe raft intr-un IKEA.

In mod normal cand faceti cumparaturile puneti in cos prima farfurie. Pe baza acestui principiu functioneaza si stiva – orice element adaugat în ea va fi pus in varful (capatul / top-ul) stivei, iar atunci când dorim sa accesam o anumita farfurie, incepem sa o parcurgem de la varf către baza (nu invers – le-ai sparge pe toate daca ai face invers).

La ce este folosita stiva?

• Backtracking – in momentul cand vrei sa parcurgi un labirint si te blochezi, pentru a retine pasii ce i-ai facut, ii memorezi intr-o stiva. Daca doresti sa te intorci inapoi un anumit numar de pasi, scoti pe rand coordonatele geografice din stiva.
• Inversarea unui string – Daca doresti sa construiesti imaginea in oglinda a unui string (de exemplu din „mere” sa faci „erem” – vei folosii o stiva). Pe masura ce citesti cuvantul, pui fiecare litera in stiva, iar in momentul cand construiesti cuvantul nou, scoti cate o litera pe rand din stiva.
• Multe alte exemple (evaluarea unei expresii, etc)

Cum implementam stiva?

Inainte de a implementa stiva vom traduce denumirile functiilor in engleza (pentru a te familiariza cu libraria STL).

• push(int numar) – adauga un element in stiva
• pop() – sterge ultimul element din stiva
• peek() – afiseaza ultimul element din stiva
• isEmpty() – verifica daca stiva este goala

Nota: Uneori functia pop() vine „la pachet cu functia peek()”

Există două feluri prin care o putem implementa: fie printr-un array, fie printr-o lista simpla inlantuita. La clasa veti aborda prima metoda, pentru ca listele nu mai intra in programa de Bacalaureat (din cate stiu, poate s-a schimbat intre-timp).

Probabil va intrebati: „de ce trebuie sa implementam noi ceva ce este gata scris in STL?„. Raspunsul este foarte simplu: inveti mult mai bine principiile cu care functioneaza si te forteaza sa intelegi programarea mai bine.

Varianta 1 – Utilizarea unui array (multimi)

#include    <iostream>

using namespace std;

const int LIM = 100;

bool isEmpty(int k) {
    if(k == 0)
        return true;
    return false;
}

void push(int stiva[], int &k, int numar) {
    k = k + 1;
    stiva[k] = numar;
}

int peek(int stiva[], int k) {
    return stiva[k];
}

int pop(int stiva[], int &k) {
    int rezultat = peek(stiva, k);
    k = k - 1;
    return rezultat;
}

int size(int k) {
    return k;
}

int main() {

    int stiva[LIM], k = 0;
    push(stiva, k, 2);
    push(stiva, k, 4);
    push(stiva, k, 6);
    push(stiva, k, 7);
    push(stiva, k, 8);
    cout << pop(stiva, k);
    cout << pop(stiva, k);
    cout << pop(stiva, k);
    return 0;
}

Aceasta varianta incalca una din principiile fundamentale ale stivei. Este restrictionata de un numar maxim de elemente. Stiva este o structura de date flexibila.

Varianta 2 – Utilizarea listelor simpu inlantuite

#include    <iostream>

using namespace std;

struct Nod {
    int data;
    Nod* next;
};

Nod* newNode(int data) {
    Nod* nodNou = new Nod();
    nodNou -> data = data;
    nodNou -> next = NULL;
    return nodNou;
}

bool isEmpty(Nod* top) {
    return top == NULL;
}

void push(Nod* &top, int data) {
    Nod* nodNou = newNode(data);
    nodNou -> next = top;
    top = nodNou;
}

int pop(Nod* &top) {
    if(isEmpty(top))
        return 0;

    Nod* tmp = top;
    top = top -> next;
    int rezultat = tmp -> data;
    delete tmp;
    return rezultat;
}

int peek(Nod* top) {
    if(isEmpty(top))
        return 0;
    return top -> data;
}

int main() {
    Nod* top = NULL;
    push(top, 2);
    push(top, 4);
    push(top, 6);
    push(top, 7);
    push(top, 8);
    cout << pop(top);
    cout << pop(top);
    cout << pop(top);
    return 0;
}

Probleme ce utilizeaza stivele

Pentru a va familiariza cu stivele, puteti sa rezolvati problemele

• Componente tare conexe – infoarena.ro
• Ciclu Eulerian – infoarena.ro