Structuri de date și algoritmi

Stiva este o structura de date in care introducerea (extragerea) de elemente se

poate efectua doar intr-o (dintr-o) singura pozitie, numita varful stivei, care este de fapt,

sfarsitul listei. Stivele sunt cunoscute de asemenea ca liste LIFO (Last In First Out).

Operatiile fundamentale care se pot efectua asupra unei stive sunt: introducerea in

stiva (PUSH) si extragerea din stiva (POP) a celui mai recent element introdus. De

asemenea, acest element poate fi accesat printr-o operatie care nu presupune si extragerea

sa din stiva (TOP). Operatiile POP si TOP asupra unei stive vide sunt considerate erori.

POP

TOP

PUSH

STIVA

Fig.2.1. Modelul stivei. Introducerea, extragerea si accesarea primului element

Modelul general al stivei este acela in care doar un singur element este accesibil

(acela care se afla in varful stivei).

A

B

A A

B B

C

VARF

VARF

VARF

Fig.2.2. Modelul stivei. Accesibilitatea elementului din varf dupa operatiile PUSH

si POP

2.2. IMPLEMENTAREA STIVELOR

Stivele pot fi implementate in doua moduri clasice: static si dinamic.

Implementarea dinamica utilizeaza pointeri, iar cea statica, tablouri. Implementarea sub

forma de tablou are dezavantajul lungimii finite a stivei.

Lucrarea 2. Stive

--------------------------------------------------------------------------------------------------------------------------------

2

Operatiile care pot fi efectuate asupra unei stive sunt urmatoarele:

- crearea stivei;

- introducerea unui element in stiva;

- extragerea unui element din stiva;

- extragerea informatiei elementului aflat in varful stivei;

- testul de stiva vida.

2.2.1. IMPLEMENTAREA DINAMICA

Implementarea dinamica utilizeaza modelul listei inlantuite. O operatie de tip

PUSH realizeaza introducerea unui element in capul listei, iar o operatie de tip POP

determina eliminarea elementului din capul listei. O operatie de tip TOP va accesa

elementul din capul listei si va intoarce informatia continuta de acesta.

Crearea unei stive consta in initializarea varfului stivei cu valoarea NULL.

Introducerea elementului urmator se va realiza prin:

- alocarea unui spatiu in memorie pentru acesta si

- atribuirea valorii din varful stivei campului care indica spre elementul urmator.

Apoi, se va actualiza varful stivei.

Exemplu:

# include <stdio.h>

# include <alloc.h>

# include <conio.h>

typedef struct

{

int Valoare;

} InfoT;

typedef struct Nod

{

InfoT Date;

struct Nod *Urm;

} NodT;

typedef struct

{

NodT *Varf;

}StivaT;

Implementarea stivelor. Aplicatii