STRUCTURA DE TIP STIVA

DEFINITIE SI IMPLEMENTARE

CONTINUT

• DEFINITIE

• DECLARAREA STIVEI

• PRELUCRAREA STIVEI

- Testare

- Initializare

- Adaugarea unui nod

- Eliminarea unui nod

DEFINITIE

•Def: Stiva este o lista restrictiva in care operatiile de

introducere si extragere se efectueaza pe la o singura

extremitate.

•Proprietati:

-cele doua extremitati ale stivei se numesc baza si

varf.

- accesul la nodurile stivei este permis numai prin

extremitatea varf.

- stiva se mai numeste si structura de tip LIFO

(Last In First Out)

10

8

12

vf

baza

IMPLEMENTARE

Implementarea stivei se poate face:

• cu alocare inlantuita. – la fel ca a unei liste liniare dar se vor folosi

numai adaugarea in fata primului nod si eliminarea primului nod.

• cu alocare secventiala – este un mecanism mult mai simplu pentru

adaugarea si eliminarea nodurilor.

Concluzie: cea mai simpla implementare a stivelor este cea

secventiala cu ajutorul unui vector.

DECLARAREA STIVEISintaxa:

const unsigned NMAX=100;

typedef <tip_data> nod;

nod stiva[NMAX+1], val;

unsigned vf,baza;

unde: tip_data = orice tip al limbajului

val - valoarea introdusa in nod

vf - varful stivei

Prelucrarea se face de la varf spre baza. Accesul la informatia din

varful stivei se face cu stiva[vf]

PRELUCRAREA STIVEI1.Testarea stiveia.stiva vida: este_vida = vf == NULL;

unde este_vida e o variabila cu valoarea 1 daca stiva e vida si 0 in caz contrar.

b.stiva plina: este_plina = vf == NMAX;

unde este_plina e o variabila cu valoarea 1 daca stiva e plina si 0 in caz contrar.

2.Initializarea stiveiIn aceasta secventa se creeaza stiva vida:vf = baza = NULL;

PRELUCRAREA STIVEI3.Adaugarea unui nod in stiva:

if (! este_plina) {if (este_vida) baza = 1; vf++; stiva [vf] = val;}

Exemplu: Pentru o stiva in care se adauga 3 caractere a,b,c operatiile de adaugare se executa astfel:

a

b

a

c

b

a

PRELUCRAREA STIVEI4.Eliminarea unui nod din stiva:

if (! este_vida) {val = stiva[vf]; vf --;}if(este_vida) vf = baza = NULL;

Exemplu: Eliminarea a doua caractere din stiva se executa astfel:

c

b

a

b

a a

sfarsit