Structura de tip stiva

Structura de tip stiva

Definitie: Prin stive (in limba engleza stack) se intelege o lista liniara care are proprietatea ca toate operatiile de introducere si extragere din stiva a elementelor se fac la un singur capat al listei, numit virful stivei.

Pentru intelegerea mecanismului unei stive, ajuta foarte mult reprezentarea (atribuita lui Dijkstra) sub forma manevrarii intr-un depou a vagoanelor de cale ferata.

O stiva fara nici un element se numeste stiva vida.

Indiferent de implementarea fizica a stivelor (secventiala sau inlantuita) o caracteristica a acestora o constituie faptul ca numarul maxim al elementelor componente este limitat. Cind s-a completat acest numar maxim, se spune ca stiva este plina.

In reprezentarea inlantuita a stivelor sunt doua lucruri caracteristice acestora: - adresa unde se afla primul element, si numarul maxim de elemente al unei stive.

Aceste structuri de date au primit diverse denumiri in afara de stive: - liste cu deplasare in jos ('push-down list'), memorii 'cuib' ('nesting stores') sau liste tip 'ultimul sosit-primul iesit (LIFO = 'last in-first out').

Stivele apar destul de frecvent in practica de toate zilele.

Un exemplu simplu il constituie cazul cind se parcurge un set de date si se elaboreaza o lista de cazuri de exceptie ce vor fi prelucrate ulterior. Dupa parcurgerea setului initial de date se revine la pasul anterior pentru efectuarea prelucrarilor care urmeaza, extragind pe rind elementele listei pina aceasta devine vida. Similar problema intrarii in subrutine si revenirii din acestea, in timpul executiei unui program de catre un calculator are un comportament de tip stiva.

Stivele sunt deosebit de utile in prelucrarea limbajelor cu o structura recursiva, cum sunt limbajele de programare si expresiile aritmetice. In general stivele apar cel mai frecvent in legatura cu algoritmii explicit sau implicit recursivi.

Unii autori se exprima ca un element la introducerea in stiva deplaseaza in jos elementele existente in stiva, iar la extragere ele sint deplasate in sus, analog cu un pachet de cartele perforate dintr-un perforator de cartele. Utilizarea prescurtata de impingere in sus, sau in jos are avantajele sale, dar creeaza in mod fals impresia de deplasare a listelor in cadrul memoriei calculatorului. Fizic nu se deplaseaza nimic, elementele sunt doar adaugate, sau extrase din virful stivei, pe cind ultimul element ramine tot timpul fix.

Reprezentarea grafica a unei stive:

Nemaipunindu-se probleme de cautare a unui element intr-o stiva, se poate renunta la cimpul cheie de identificare, asa ca structura elementelor unei stive se poate defini astfel:

typedef struct stack

pstack;

unde cimpul 'next' este pointerul catre urmatorul element al stivei.

Ultimul element al stivei, baza ('bottom') va avea cimpul 'next' incarcat cu valoarea NIL, (respectiv NULL in 'C'). Primul element al stivei varful ('top') va fi referit de un pointer (numit de noi 'ps') si el va fi acela care se va modifica urmarind adresa virfului stivei.

Operatii asupra stivelor

a) Crearea unei stive vide

Este o operatie foarte simpla si nu implica decit initializare avirfului stivei 'ps' cu valoarea NIL, sau NULL (depinde de limbaj).

b) Introducerea unui element intr-o stiva

Daca intr-un program nu trebuie sa se tina cont de lungimea maxima a unei stive (de exemplu, in cazul implementarii dinamice a stivelor), introducerea unui element este asemanatoare cu operatia echivalenta de la listele liniare simplu inlantuite.

Fie 'p' un pointer spre aceeasi structura a stivei.

p=(tstack *)malloc(sizeof(tstack));

p->inf=..(inf utila);

p->next=ps;

ps=p;

Daca lungimea maxima a unei stive este predeterminata sunt doua variante de realizat a introducerii unui element.

Prima ar fi aceea in care o variabila globala a sistemului 'ne', de exemplu, de tip intreg memoreaza tot timpul numarul de elemente ale stivei. La crearea stivei vide, ne:=0 si odata cu introducerea unui nou element 'ne' se incrementeaza cu 1.

ne=ne+1;

if (ne>nmax) printf('Depasire lungime stiva!');

else

O a doua varianta, care necesita mai multa memorie, ar fi aceea in care s-ar pastra cimpul 'key' in articolul aferent unui element al stivei si in care s-ar scrie numarul de ordine al fiecarui element.

if (ps->key==nmax) printf('Depasire lungime stiva!');

else

In acest caz la introducerea primului element intr-o stiva cimpul key trebuie initializat cu valoarea 1.

if (ps->key==nmax) printf('Depasire lungime stiva!');

else

c) Extragerea unui element dintr-o stiva

Si aceasta operatie e similara cu aceea de la liste liniare simplu inlantuite. Trebuie detectat insa momentul in care stiva devine vida, caz in care nu se mai pot face extrageri.

De asemenea, in cazul stivelor (desi nu numai in acest caz) este esentiala folosirea memoriei cit mai economicos. Se recomanda ca odata cu extragerea unui element din stiva, zona de memorie alocata acestuia sa fie eliberata.

Acest lucru se realizeaza folosind functia FREE(). In continuare presupunem folosirea unei variabile intregi care da numarul de ordine al ultimului element introdus in stiva, cu ajutorul caruia putem detecta o stiva vida.

if (ne==0) printf('Stiva vida!');

else

O varianta mai simpla ce nu mai presupune folosirea variabilei 'ne' este urmatoarea:

if (ps==NULL) printf('Stiva vida!');

else

Problema rezolvata

Dandu-se o matrice de numere reale, sa se determine punctele 'sa' ale matricei (un element

a[i, j] este punct 'sa' daca el este minim pe linia 'i' si maxim pe coloana 'j').

Se va parcurge matricea pe linii si pentru fiecare linie se va calcula minimul. Elementul respectiv se va introduce intr-o stiva (se memoreaza coloana si valoarea efectiva a elementului).

Se vor scoate apoi elementele din stiva si se va testa daca fiecare element este si maxim pe coloana respectiva.

#include <stdlib.h>

#include <alloc.h>

#include <conio.h>

#include <stdio.h>

typedef struct stack

pstack;

void main()

}

p = (pstack *)malloc(sizeof(pstack));

p->col = k;

p->val = min;

p->next = ps;

ps = p;

}

p = ps;

while (p->next!=NULL)

Probleme propuse

1. Pe calea ferata de intrare exista 6 vagoane 1, 2, 3, 4, 5, 6. Pot fi ele permutate in ordinea 3, 2, 5, 6, 4, 1? Daca da, scrieti un program care simuleaza acest lucru.

2. Fie doua podete de jetoane cu numere pare si impare. Sa se scrie un program care sa extraga trei jetoane din primul podet cu numere pare si sa se introduca in cel de-al doilea dupa numere impare.

3. Sa se scrie o colectie de proceduri pentru gestiunea a N stive intr-un masiv unidimensional V[1..m]. Se presupune ca zonele alocate celor N stive au lungimi egale cu M/N (unde M/N reprezinta partea intreaga minorata). Se vor scrie proceduri pentru:

a) Depunerea unui termen intr-una din stive;

b) Extragerea unui termen dintr-o stiva;

c) Testarea faptului ca stiva I este vida;

d) Testarea faptului ca stiva I este plina.

4. Sa se scrie o colectie de proceduri pentru gestiunea a 2 stive intr-un masiv unidimensional V[1..m]. Una din stive va creste de la 1 in sus si cealalta de la m in jos.

5. Sa se scrie o colectie de proceduri pentru gestiunea a 2 stive si a unei cozi intr-un masiv unidimensional V[1..m].

6. O strategie de testare daca stiva "i" este plina este redistribuirea intregului spatiu disponibil in proportie cu rata de crestere a fiecarei stive individuale, de la ultimul apel al procedurii de testare daca o stiva este plina. Acest lucru necesita utilizarea unui alt masiv LT[1..n], unde LT[j] este valorea lui t[j] de la ultimul apel al procedurii de testare daca stiva este plina. Atunci cantitatea cu care fiecare stiva a crescut va fi t[i]-LT[j], j<>i; si pentru stiva "i", t[i]-LT[i]+1 deoarece momentan se incearca o noua depunere in stiva "i". (t[i] reprezinta pozitia virfului stivei i).

Sa se scrie o procedura de testare, daca stiva "i" este plina, astfel incit sa se redistribuie toate stivele astfel incit spatiul liber dintre stivele "j" si j+1 sa fie proportional cu cresterea stivei "j" si sa se aloce cel putin o locatie libera pentru stiva "i".

7. Sa se scrie o colectie de proceduri pentru gestiunea a N obiecte de tip stiva, sau coada, dintre care N1 stive si N2=N-N1 cozi intr-un masiv unidimensional V[1..m]. Se va considera ca un obiect de tip coada cu "r" locatii poate memora doar (r-1) elemente.

8. Sa se implementeze o structura de tip stiva utilizind o lista liniara simplu legata, scriind proceduri pentru adaugarea si eliminarea unui element si a unei functii de testare daca stiva este vida.

9. Sa se scrie un program care transforma o expresie corecta sintactic dintr-un limbaj L1 intr-un limbaj L2. Expresia este compusa in ambele limbaje din operanzi exprimati prin identificatori, operatori binari si paranteze rotunde inchise si deschise. Programul primeste numarul de operanzi, operatorii (aceeasi in ambele limbaje) si prioritatile fiecarui operator in fiecare din cele doua limbaje precum si expresia in L1. Se cere sa se tipareasca expresia corespunzatoare din L2, fara paranteze redundante.

Observatii:

- cele 2 limbaje difera exclusiv prin prioritatile asociate operatorilor;

- expresiile din L1 si L2 sint echivalente daca dupa evaluare produc acelasi rezultat;

- identificatorul este o succesiune de litere si cifre care incepe cu o litera;

- expresia nu contine blancuri si se termina cu primul blanc intilnit;

- operatorii sint reprezentati prin caractere diferite de litere, cifre si paranteze. Prioritatile lor in cele doua limbaje sint date ca numere naturale in ordine crescatoare;

- operatiile au aceeasi asociativitate in ambele limbaje.

Exemplu:

Setul operatorilor: + , * , / ;

Prioritatile operatorilor :

- in L1: 1, 2, 3;

- in L2: 2, 1, 3; (prioritatile sint asociate in ordinea operatorilor);

Expresia in L1: (A + X53)* RAZA2/ALFA;

in L2: A + X53 * RAZA2/ALFA;

10. Se considera un sir arbitrar de caractere care contine, printre alte caractere si paranteze rotunde. Sirul se considera corect daca parantezele inchise si deschise sint corect imperecheate. Spre exemplu sirul: A (B (C) D % ( ) ) este corect, dar sirul: (A ( ) ) (Z nu este corect. Sa se conceapa si sa se implementeze un algoritm care testeaza daca un sir de caractere este corect folosind o structura de date auxiliare de tip stiva.

11. Se considera "n" perechi de caractere (Li, Ri), Li numite caractere stinga si Ri caractere dreapta, oricare 2 caractere dintre cele 2N caractere diferite.

Se considera un sir de caractere care contine printre alte caractere si caractere Li sau Ri. Sirul se considera corect daca:

(i) Fiecare caracter stinga Li se poate imperechea cu caracterul dreapta Ri corespunzator;

(ii) Fiecare caracter stinga (dreapta) face parte din exact o singura pereche;

(iii) Subsirul cuprins intre un caracter stinga si un caracter dreapta imperecheate satisface de asemenea (i) si (ii);

Spre exemplu pentru N=4 se considera urmatoarele perechi de caractere stinga-dreapta: A , Z ; [ , ] ; ( , ) ; L , R.

Sirul de caractere: A L U 2 ( 1 ) L R 1 C R 6 Z [ % ] este corect, dar sirul: A B ( [ 2 A ] ) 1 L @ R Z Z nu este corect.

Sa se conceapa si sa se implementeze un algoritm care testeaza daca un sir de caractere este corect, folosind o structura de date auxiliara de tip stiva.

12. S-a observat experimental ca majoritatea programelor care tind sa foloseasca tot spatiul de memorie disponibil au sanse maxime sa depaseasca acest spatiu.

In lumina acestei observatii pare rezonabil ca in acest caz sa se deplaseze stivele pentru a crea spatiu pentru alte stive numai daca, cantitatea de spatiu liber ramasa nu este prea mica. Sa se scrie procedura de testare daca o stiva "i" este plina, astfel incit sa se tina cont de faptul ca daca exista mai putin de "c" locatii libere ("c" este o constanta determinata empiric), stiva sa se considere plina si algoritmul sa se termine.