Limbajul C. Implementarea unei stive cu un tablou monodimensional

O stiva este o colectie de elemente de acelasi tip procesata dupa principiul LIFO, last in, first out. Asta inseamna ca procesarea se face intotdeauna la "capatul din dreapta", adica introducerea de element nou, stergerea unui element si citirea elementelor din stiva se realizeaza pornind de la ultimul element adaugat.

Implementarea pe baza unui tablou monodimensional, numit in continuare 'stack', are o anumita valoare didactica dar si limitari, care pot fi depasite prin folosirea unei liste inlantuite, caz ce va fi detaliat intr-o postare ulterioara.

index: 0  stack[0]: neinitializat

Adaugam elementul x:

index:  0  stack[0]: x

            1  stack[1]: neintitializat

Adaugam elementul y:

index : 0  stack[0]: x

            1  stack[1]: y

            2  stack[2]: neinitializat

.....

Mai detaliat, implementarea va tine cont de urmatoarele aspecte referitoare la stack si la functiile push(), pop() si list(). Sigur ca pot fi folosite alte nume pentru functiile asociate stivei dar s-a preferat jargonul consacrat.

1. Se porneste cu stiva neinitializata, astfel incat pozitia curenta, de index 0, este si prima pozitie libera in stiva.

2. Functia de adaugare push() atribuie elementului pozitiei curente valoarea dorita, x, si incrementeaza cu 1 indexul (numit 'iter' in cod) catre urmatoarea pozitie neinitializata.

3. Cand indexul curent a ajuns la dimensiunea maxima a stivei (variabila 'dim') procesul de adaugare nu mai poate continua si se emite un mesaj corespunzator.

4. Este posibila in continuare eliminarea de elemente din stiva cu functia pop(). Aceasta decrementeaza indexul pozitiei curente, pozitia decrementata devenind 'libera'. Este returnata valoarea corespunzatoare indexului decrementat, altfel spus, valoarea 'eliminata'. Evident, valoarea respectiva nu este eliminata in implementarea prezentata. Ea continua sa fie rezidenta in tablou pana la o noua populare a stivei, dar in virtutea mecanismului descris pana aici valoarea in cauza este acum inaccesibila.

5. Cand ultima pozitie 'libera' devine cea corespunzatoare indexului 0, procesul de eliminare nu mai poate continua si se emite un mesaj corespunzator.

6. Functia list() afiseaza elementele stivei dinspre capatul din dreapta catre inceput (index 0).

7. Declararea tabloului care implementeaza stiva si a indexului curent al pozitiei libere in stiva drept variabile globale ne scuteste de declararea unor parametri suplimentari in functiile push(), pop() si list().

Codul si printscreen-urile executiei:

//Stiva cu tablou monodimensional

#include <stdio.h>

int * stack;

int iter = 0;

void push(int x);

int pop();

void list(void);

int main()

{

            int x, dim;

            char c = '\0';

            puts("Cate elemente vreti sa aiba stiva de numere intregi?");

            scanf("%d", &dim);

            stack = (int *)malloc(dim * sizeof(int));

            // s-a generat stiva;

            puts("Containerul stivei a fost creat.");

            do

            {

        

              puts("Dorim sa:\na) adaugam la stiva; b) stergem din stiva; \nc) afisam stiva; d) iesim din program.");

              _flushall();

              c = getchar();

              if(c == 'a')

                   {

                                    if(iter == dim) printf("\nStiva plina!");

                                    else

                                    {

                                                printf("\nElementul x: ");

                                                scanf("%d", &x);

                                                _flushall();

                                                push(x);

                                    }

                   }

                        else if(c == 'b')

                        {

                                    if(iter == 0) printf("\nStiva este goala!");

                                                else

                                    {

                                                printf("\nAm extras elementul %d.", pop());

                                    }

                                    }

                        else if(c == 'c') list();

            }

            while(c != 'd');

            free(stack);

            return 0;

}

           

void push(int x){ stack[iter++] = x; }  

int pop(void) { return stack[--iter]; }

void list()

{

            int i = iter;

            while(--i >= 0) printf("\nElementul # %d: %d.", i, stack[i]);

}