Structuri de date liniare

Stive

Stiva este o lista liniara in care inserarile si stergerile din lista se pot face numai pe la un capat al listei, numit varful stivei. Singurul element care poate fi accesat la un moment dat este cel din varful stivei. Se poate face o analogie intre o stiva folosita in programare si o stiva de carti. Adaugarea unei carti se poate face numai in varful stivei de carti, peste cartile existente si singura carte ce poate fi accesata, eventual eliminata din stiva este cea din varful stivei.

Stivele se mai numesc si liste push-down sau LIFO (last in/first out) deoarece primul element care este extras din stiva este ultimul introdus in stiva.

Vom nota inserarea unui element a intr-o stiva S: a S, iar stergerea unui element a dintr-o stiva S: S  a. Cele doua operatii se mai numesc si push respectiv pop.

2.1 Alocarea secventiala

In alocarea secventiala, presupunand ca stiva este definita

T x[N];

unde N este o constanta suficient de mare, T este un tip de date definit anterior (eventual printr-o definitie de tipul typedef), iar n este numarul de elemente din stiva,

n N, iar elementul din varful stivei este considerat elementul x[n-1],

x[0] x[1] x[2] x[n -1]

atunci operatia de inserare  elem_nou S se poate descrie astfel:

if n = N then OVERFLOW

else n = n + 1

x[n-1] = elem_nou

endif

iar operatia de stergere S elem_sters se poate descrie astfel:

if n = 0 then UNDERFLOW

else elem_sters = x[n-1]

n = n - 1

endif

2.2 Alocarea inlantuita

In alocarea inlantuita, folosim aceeasi structura ca si in cazul listei liniare

struct nod

typedef struct nod NOD;

unde T este presupus definit anterior (eventual printr-o definitie typedef) si notam cu top pointerul stivei (adica pointerul care pointeaza la elementul din varful stivei).

NOD *top;

Cu aceste notatii, operatiile cu stive se pot descrie astfel:

inserarea unui nod nou: Algoritm: Folosim variabilele info_nou ce contine valoarea informatiei nodului ce trebuie introdus in lista si p pointer la un nod. Aloca memorie pentru un nod nou.  Returneaza p, un pointer la noul nod. if p NULL then p -> link = top p -> info = info_nou top = p else OVERFLOW endif info_nou   p top ....... NULL

stergerea/accesarea unui nod: Algoritm: if top = NULL then UNDERFLOW else elem_sters = top -> info top = top -> link endif info

  top

NULL

.............

Scrieti un program care implementeaza algoritmii de mai sus pentru o stiva.