Definirea tipului abstract stiva

Stiva este un tip special de lista în care toate insertiile si suprimarile de noduri au loc la un singur capat. Acest capat se numeste vârful stivei.

Tipul abstract stiva pe care îl definim contine urmatorii operatori:

1. Initializarea stivei.
2. Verificarea faptului ca stiva e plina.
3. Verificarea faptului ca stiva e goala.
4. Introducerea unui element în vârful stivei.
5. Eliminarea elementului din vârful stivei.
6. Furnizarea elementului din vârful stivei fara a-l elimina.

În exemplul nostru, stiva este materializata printr-un tablou de numere reale, numit stiva, iar vârful stivei este indicat de variabila ind_top. Dimensiunea stivei este egala cu MAX, valoare care este lungimea tabloului.

Toate declaratiile si definitiile care urmeaza mai jos trebuie sa fie continute într-un singur fisier. Pentru a "ascunde" de utilizator detaliile de implementare a stivei, atât stiva cât si ind_top sunt definite cu clasa de memorare static. Astfel domeniul lor de vizibilitate se restrânge la fisierul curent si aceste variabile nu pot fi accesate dintr-un alt fisier.

Functiile au implicit clasa de memorare extern. Prin urmare, ele pot fi apelate din alte fisiere, iar toate operatiile asupra stivei sunt realizate doar prin intermediul lor.

static double stiva[MAX];  /* stiva */
static int ind_top;  /* varful stivei */

Operatorii sunt implementati astfel:

Initializarea stivei:

void init(void)
{
  int i;

  for (i=0; i<MAX; i++) 
    stiva[i]=0; /* toate elementele devin 0 */

  ind_top=-1; /* varful stivei indica primul element ocupat*/
} /* init */

Verificarea faptului ca stiva este plina:

int plin(void)
{
  return ind_top==MAX-1; 
} /* plin */

Stiva este plina atunci când vârful stivei indica spre ultimul element din stiva (cel de indice MAX-1).

Verificarea faptului ca stiva este goala:

int gol(void)
{
  return ind_top==-1;
} /* gol */

Functia gol verifica daca stiva este goala. Când indicele stivei este egal cu -1, stiva nu contine nici o valoare si gol returneaza 1. Daca ind_top$>$-1 atunci stiva contine cel putin o valoare, astfel ca gol returneaza 0.

Introducerea unui element în vârful stivei:

void push(double nr)
{
  if (plin()) /* daca stiva este plina */
  {
    printf("Eroare: stiva este plina\n");
    exit(1);
  }

  stiva[++ind_top] = nr; /* noul element este 
                            introdus in varful stivei */
} /* push */

Rutina push introduce în vârful stivei numarul transmis prin parametrul double nr. Daca stiva este plina atunci se afiseaza un mesaj de eroare si executia programului este terminata. În caz contrar, se incrementeaza vârful stivei ind_top, dupa care noul element este memorat în vârful stivei.

Eliminarea elementului din vârful stivei:

void pop(void)
{
  if (gol() ) /* daca stiva este goala */
  {
    printf("Eroare: stiva este goala\n");
    exit(1);
  }
  ind_top--; /* decrementeaza varful stivei */
} /* pop */

Rutina pop extrage elementul din vârful stivei fara a-l returna. Daca stiva este goala atunci pop afiseaza un mesaj de eroare si executia programului este încheiata. În caz contrar, vârful stivei este decrementat.

Furnizarea elementului din vârful stivei (fara a-l elimina):

double top(void)
{
  if (gol()) /* daca stiva este goala */
  {
    printf("Eroare: stiva este goala\n");
    exit(1);
  }
  return stiva[ind_top]; /* returneaza 
                            elementul din varful stivei */
} /* top */

Functia top returneaza valoarea elementului din vârful stivei, însa fara a-l extrage. Daca stiva este goala atunci se afiseaza un mesaj de eroare si executia programului este încheiata. În caz contrar, top returneaza valoarea din vârful stivei.