Stiva. Aspectul logic al stivei

Una dintre cele mai importante şi folositoare concepţii în tehnicile de programare este concepţia de stivă. Să încercăm să dăm câteva noţiuni ale stivei sub aspect logic.

Def. 1. Stiva – o listă secvenţială cu lungimea variabilă, inserarea şi eliminarea elementelor căreia se face numai la un capăt al ei, numit vârful stivei.

Def. 2. Stiva este o formă de organizare a datelor (structură de date) cu proprietatea că operaţiile de introducere şi scoatere a datelor, se fac la un capăt al ei numit vârful stivei (este o structură tip LIFO - Last In, First Out, “Ultimul sosit, primul ieşit”).

Def. 3. Stiva reprezintă o mulţime ordonată (fiecare element este ordonat în raport cu baza stivei) şi omogenă (de acelaşi tip) de elemente în care plasarea elementelor noi şi eliminarea celor existente se face numai la un capăt al ei, numit vârful stivei.

Grafic stiva se poate reprezenta ca în figura alăturată. Exemple de stive: platourile de la o cafenea aşezate una peste alta, stivă de monede, cărămizi, o cutie cu cămăşi, o stivă de cărţi, linia de manevrare a vagoanelor într-un depou etc. Stiva este utilă în situaţii în care necesară memorarea unor informaţii şi regăsirea acestora într-o anumită ordine, descrisă de principiul LIFO. Stiva este utilizată atunci când programul trebuie să amâne execuţia unor operaţii, pentru a le executa ulterior, în ordine inversă a apariţiei lor. Operaţia curentă este cea corespunzătoare vârfului stivei, în stivă fiind reţinute toate informaţiile necesare programului pentru a executa operaţiile respective

1. Operaţii specifice cu stive

Stivele pot fi implementate utilizând atât structuri statice de date (vectori) cât şi structuri dinamice de date deoarece numărul de componente se modifică în timpul execuţiei programului (dimensiunea stivei creşte sau descreşte). Aspectul dinamic al structurii determină apariţia în timp a unor noi componente, care trebuie legate în structura dinamică de celelalte componente. Structurile dinamice sunt mult mai flexibile decât cele statice şi extrem de avantajoase.

Stiva, după cum s-a menţionat mai sus, este o colecţie de elemente pentru care la un moment dat este “vizibil” un singur element, cel din vârful ei. Alegerea elementelor se face pe baza ordinii în care elementele au fost introduse în respectiva colecţie. Structura de date care implementează o stivă are un mecanism prin care se memorează această ordine. Pe baza acestei informaţii, se stabileşte elementul “vizibil” şi anume, pentru stivă acest element este cel mai recent introdus în structură. Ordinea elementelor din structură nu poate fi modificată, adică se poate utiliza un singur criteriu de alegere a elementului următor. Există două operaţii asociate acestor tipuri de structuri: introducerea şi, respectiv, extragerea unui element.

Operaţia de extragere are ca efect: obţinerea valorii elementului “vizibil”; eliminarea acestuia din structură.

Dacă în structură mai există elemente, în funcţie de ordinea de introducere a lor, este stabilit noul element care devine “vizibil”.

Vârf S T I V A

Bază

Push Pop

Fig. 1

Pentru stive, operaţiile de introducere, respectiv, extragere au nume utilizate în mod tradiţional şi anume PUSH pentru operaţia de introducere în stivă, respectiv, POP pentru operaţia de extragere din stivă.

În afară de aceste operaţii, pentru stivă se pot defini şi alte operaţii, ca de exemplu: operaţia de iniţializare a structurii; operaţia de obţinere a valorii elementului “vizibil”, fără eliminarea acestuia din stivă; operaţia de verificare dacă structura de tip stivă conţine sau nu elemente.

Unii autori includ în setul de operaţii admisibile cu stiva şi cele care permit introducerea şi extragerea elementelor din interiorul stivei, însă structura pentru care sunt posibile aşa operaţii nu corespunde definiţiei stivei.

SET DE OPERAŢII CU STIVAMod de acces: Elementele sunt adăugate şi eliminate prin vârful stivei.Operaţii specifice:INITSTACK(St)

Funcţia: Iniţializează stiva (starea - stiva vidă).Intrare: Stiva trebuie iniţializată.Precondiţie:Nici una.Ieşire: Stiva (iniţializată).Postcondiţie: Stiva este vidă.

EMPTYSTACK (St) Returnează o valoare de tip booleanFuncţia: Indică dacă stiva este vidă.Intrare: Stiva trebuie testată.Precondiţie:Nici unaIeşire: EmptyStack (fanion logic).Postcondiţie: EmptyStack = (stiva este vidă).

FULLSTACK (St) Returnează o valoare de tip booleanFuncţia: Indică dacă stiva este plină.Intrare: Stiva trebuie testată.Precondiţie:Nici unaIeşire: FullStack (fanion logic).Postcondiţie: FullStack = (stiva este plină).

PUSH(St, ElementNou)Funcţia: Adaugă un element în vârful stivei.Intrare: Stiva, ElementNou.Precondiţie:Stiva nu este plină.Ieşire: Stiva (Schimbată). Element pus.Postcondiţie: Stiva = Stiva originală cu ElementNou în vârf.

POP(St, ElementScos)Funcţia: Elimină elementul din vârful Stivei, şi-l returnează în ElementScos.Intrare: Stiva.Precondiţie:Stiva nu este vidă.Ieşire: Stiva (Schimbată). ElementScos.Postcondiţie: Stiva = Stiva originală cu elementul din vârf eliminat.

ElementScos = elementul din vârf al stivei originale

TOP(St, ElVarf)Funcţia: Returnează valoarea elementului din vârful stivei fără modificări.Intrare: Stiva.Precondiţie:Stiva nu este vidă.Ieşire: Valoarea din vârf (Stiva nemodificată)Postcondiţie: ElVarf = Valoarea din vârful stivei. Stiva nemodificată

2. Implementarea stivei. Soluţie statică

Pentru implementarea stivei se pot considera soluţii statice sau dinamice. Deoarece elementele stivei sunt de acelaşi tip, vectorul este cea mai rezonabilă structură de implementare a stivei.. În acest caz, numărul maxim de elemente ce pot fi memorate în structură este fixat.

Baza Elementele stivei Vârf Max

10 12 7 4 … …[0] [1] [2] [3] [4] [100]

Fig. 2 Stiva ca o structură statică

Pe lângă parametrii obişnuiţi ce descriu un vector, trebuie să avem şi o variabilă specială (indicator) care memorizează adresa vârfului stivei. Această variabilă o vom numi-o simplu "vârf". Acest indicator poate referi primul element liber al stivei sau ultimul element introdus în stivă (este indiferent ce luăm în calitate de vârf, principalul să ţinem minte lucrul acesta la prelucrarea ulterioară a elementelor stivei!). În cele ce urmează, vom considera că indicatorul vârfului stivei se referă la primul element liber şi creşte la introducerea noilor elemente în direcţia dimensiunii maxime a structurii.

a) Inserarea unui element în stivă

Atunci când introducem un element în stivă, el se înscrie în locul referit de indicatorul vârf, apoi acest indicator se modifică astfel ca să indice următoarea poziţie liberă (dacă indicatorul vârf arată la ultimul element introdus, atunci mai întâi se modifică el, apoi se realizează introducerea elementului în stivă). Modificarea indicatorului constă în incrementarea lui cu cu o unitate. Inserarea trebuie să fie însoţită de verificarea stării stivei – dacă stiva nu este plină (dacă "avem loc" pentru inserare).

Fig. 3 Stiva înainte şi după inserarea unui element

Algoritm Inserare în stivăDacă vârf=dimensiunea maximă a stiveiAtunci Scrie Eroare – stiva este plină!Altfel Incrementează vârful; Plasează elementul nou în poziţia vârfului;

b) Extragerea unui element din stivă

Operaţia de extragere din stivă presupune modificarea indicatorului vârf în direcţie inversă şi accesarea elementului din vârf pentru prelucrări ulterioare. Pentru a extrage un element dintr-o stivă, trebuie mai întâi să verificăm dacă există elemente în stivă (deci dacă stiva nu este vidă). Dacă există elemente, atunci memorizăm elementul din vârf într-o variabilă, după care decrementăm indicatorul vârf cu o unitate.

Fig. 4 Stiva înainte şi după extragerea unui element

93128 ...[4][3][2][1] Max...

Vârf

93128 ...7[4][3][2][1] Max...[5]

Vârf

93128 ...[4][3][2][1] Max...

Vârf

3128 ...[4][3][2][1] Max...[5]

Vârf

Datorită modului său restrictiv de funcţionare, stiva permite numai accesarea elementelor de la vârf. Dacă dorim să aflăm valoarea unui alt element al stivei, ar trebui să extragem succesiv elemente până la elementul de care avem nevoie şi să-l prelucrăm. Accesarea presupune determinarea valorii acestuia şi plasarea valorii lui într-o variabilă de lucru (de exemplu ElVârf:=St[varf]).

Algoritm Extragere din stivăDacă vârf=0 {stiva este vida }Atunci Scrie Eroare – stiva este vidă!Altfel Reţine elementul scos într-o variabilă Decrementează vârful stivei

În continuare este prezentat un Unit care realizează operaţiile specifice cu stive implementate static.

unit staticst;interfaceconst max=100; { dimensiunea maxima a stivei }type index=0..max;

tipelement=integer; { poate fi oricare }stiva=array[index] of tipelement;

var st:stiva;varf:index;

procedure initstack(var st:tipstiva);function emptystack(st:stiva):boolean;function fullstack(var st:stiva):boolean;procedure push(var st:stiva; elemnou:tipelement);procedure pop(var st:stiva; var elemscos:tipelement);procedure top(var st:stiva; var elvarf:tipelement);implementationprocedure initstack(var st:tipstiva);beginvarf:=0;

end;

function emptystack(st:stiva):boolean;beginemptystack:=varf=0;

end;

function fullstack(var st:stiva):boolean;beginfullstack:=varf=max;

end;

procedure push(var st:stiva; elemnou:tipelement);var plina:boolean;beginplina:=fullstack(st);if plinathen begin

writeln('stiva e plina, nu se pot pune elemente in ea!');halt

endelse begin

varf:=varf+1;st[varf]:=elemnou;

end;end;

procedure pop(var st:stiva; var elemscos:tipelement);var vida:boolean;begin vida:=emptystack(st); if vida then begin writeln('stiva e vida, nu se pot scoate elemente din ea!'); halt end else begin elemscos:=st[varf]; varf:=varf-1; end;end;

procedure top(var st:stiva; var elvarf:tipelement);begin if not emptystack(st)then elvarf:=st[varf];end;end.

Dacă intenţionăm să realizăm o stivă astfel ca indicatorul vârf să se schimbe în direcţia micşorării adreselor (indicatorul vârf arată la primul element liber), atunci operaţiile de bază se vor scrie astfel:procedure initstack(var st:tipstiva);beginvarf:=max;

end;function emptystack(st:stiva):boolean;begin emptystack:=varf=max;end;function fullstack(var st:stiva):boolean;begin fullstack:=varf=0;end;procedure push(var st:stiva; elemnou:tipelement);var plina:boolean;begin plina:=fullstack(st); if plina then begin writeln('stiva e plina, nu se pot pune elemente in ea!'); halt end

else beginst[varf]:=elemnou;

varf:=varf-1;end;

end;procedure pop(var st:stiva; var elemscos:tipelement);var vida:boolean;begin vida:=emptystack(st); if vida then begin writeln('stiva e vida, nu se pot scoate elemente din ea!'); halt end else begin

varf:=varf+1; elemscos:=st[varf]; end;end;procedure top(var st:stiva; var elvarf:tipelement);begin if not emptystack(st) then elvarf:=st[varf+1];end;

3. Implementarea stivei. Soluţie dinamică

Pentru implementarea stivelor se pot utiliza soluţii mai flexibile bazate pe structuri dinamice de date şi anume pe baza unei liste simplu înlănţuite.

Def. O stivă dinamică este o listă liniară simplu înlănţuită de un tip special, în care adăugarea sau scoaterea unui element se face la un singur capăt al listei, numit vârful stivei.

Elementul introdus primul în listă poartă numele de bază a stivei. Informaţia de legătură a fiecărui element din stivă reprezintă adresa elementului pus anterior în stivă, excepţie făcând baza a cărei informaţie de legătură este nil.

Operaţiile care se aplică stivelor sunt aceleaşi ca şi pentru soluţia statică bazată pe un tablou.

Efectele procedurilor şi funcţiilor prezentate în următoarea implementare dinamică sunt: Iniţializare stivă (clearstack) – Procedura iniţializează poziţia vârfului stivei într-o înregistrare

rezervată de către aplicaţie. Test stiva vidă (emptystack) – Funcţia verifică dacă mai există elemente în stivă. Introduce în stivă (push) – Procedura introduce un nou element în stivă. Extrage din stivă (pop) – Procedura extrage din stivă un element. Valoarea indicatorului

(referinţei) către elementul care a fost scos din stivă se salvează într-un argument al funcţiei. Valoare din vârf (top) – Procedura atribuie unui parametru valoarea pointerului către elementul

aflat în vârful stivei.

Unit dinamst;interfacetype tipelement=integer;

stiva=^nodst; nodst=record info:tipelement;

next:stiva;end;

var st:stiva;procedure initstack (var st:stiva);function emptystack (st:stiva):boolean;procedure push (var st:stiva; elemnou:tipelement);procedure pop (var st:stiva; var elemscos:tipelement);procedure top (var st:stiva; var virf:nod);implementationprocedure clearstack (var st:stiva);beginst:= nil;

end;

function emptystack (st:stiva):boolean;beginemptystack =(st=nil);

end;

procedure push (var st:stiva; elemnou:tipelement);var nodnou:stiva;beginnew(nodnou);nodnou^.info:=elemnou;nodnou^.next:=st;st:= nodnou;

end;

procedure pop (var st:stiva; var elemscos:tipelement);var temp:stiva; beginif not emptystack(st) then begin

elemscos:= st^.info;temp:=st;st:=st^.next;dispose(temp);

end;end;

procedure top (var st:stiva; var virf:nod);beginif not emptystack(st) then virf:= st^.info;

end;

end.

În figurile din continuare, se ilustrează operaţia de punere pe stivă a unui nod, respectiv scoaterea unui nod din stivă.

Efectul procedurii PUSH

Efectul procedurii POP

Vârf

4 3 2 1 NILSt

? ?NodNou 1. NEW(NodNou);

Vârf

4 3 2 1 NILSt

5 ?NodNou 2.

NodNou^.Info:=ElemNou;

Vârf

4 3 2 1 NILSt

5NodNou 3. NodNou^.Next:=St;

St:=NodNou;

2. Temp:=St;St:=St^.Next;Dispose(Temp)

;

Vârf

1. ElScos:=St^.Info;

Vârf

4 3 2 1 NILSt

5

ElScos

5

Temp

4 3 2 1 NILSt

5

4. Aspect aplicativ

Problemă: Se citeşte un şir de caractere de la tastatură, care se termină cu spaţiu liber (blanc). De afişat şirul de caractere în ordine inversă.

Algoritmul rezolvării poate fi implementat sub forma unei proceduri Revers în cadrul căreia se apelează procedurile descrise în unit-ul StaticSt (InitStack, Push, Pop şi funcţia EmptyStack).

procedure revers; { inverseaza un sir }const blanc=' ';var ch:char; stiva:tipstiva;

begininitstack(stiva);repeatread(ch);if ch<>blancthen push(stiva,ch);

until ch=blanc;while not emptystack(stiva) dobeginpop(stiva,ch);write(ch,' ');

end;end;