Structuri de date – Stiva si Coada


1. Stiva

Stiva este o structura de date abstracta. Atat pentru operatia de inserare a unui element in aceasta structura, cat si operatia de extragere a unui element se realizeaza la un singur capat, denumit varf.

Stiva, structuri de date

Imaginea reprezentata mai sus este o stiva.

Ca sa ne imaginam mai bine functionarea unei stive, sa ne gandim cum lucreaza un ospatar cu un teanc de farfurii. Cand doreste sa puna o farfurie in teanc, o pune deasupra, peste toate celelalte. Iar cand doreste sa foloseasca o farfurie, o ia pe cea de deasupra (pe cea din varf). Ospatarul efectueaza aceste „operatii” pentru a nu sparge farfuriile. Daca ar lua o farfurie de la mijloc, toate de deasupra se vor sparge.

Acest mod de functionare face ca ultimul element inserat in stiva sa fie primul extras. Din acest motiv, stiva este definita ca o structura de date care functioneaza dupa principiul LIFO (Last In First Out – ultimul intrat, primul iesit).

Care este utilitatea stivelor?


In informatica, stiva joaca un rol fundamental. Pentru a intelege mecanismele programarii este necesara cunoasterea notiunii de stiva. Pe scurt, stiva este utila in sitatiile in care este necesara memorarea unor informatii si regasirea acestora intr-o anumita ordine, descrisa de principiul LIFO. Stiva este utilizata atunci cand programul trebuie sa amane executia unor operatii, pentru a le executa ulterior, in ordinea inversa a aparitiei lor. Operatia curenta este cea corespunzatoare varfului stivei, in stiva fiind retinute toate informatiile necesare programului pentru a executa operatiile respective.


Cum implementam o stiva?

Stiva este o structura de date abstracta, asa cum am specificat si la inceputul tutorialului. Astfel, ea poate fi implementata in diferite moduri. De exemplu, putem implementa o stiva ca un vector in care retinem elementele stivei. Pentru ca acest vector sa functioneze ca o stiva, singurele operatii permise sunt operatiile caracteristice stivei.


Crearea unei stive vide

Pentru a crea o stiva vida initializam varful stivei cu -1 (varful stivei indica intotdeauna pozitia ultimului element introdus in stiva. Elementele sunt memorate in vector incepand cu pozitia 0).


Inserarea unui element in stiva

Pentru a insera un element x in stiva S trebuie sa verificam in primul rand daca „avem loc”. Daca stiva este plina, inserarea nu se poate face, altfel vom mari varful stivei si vom plasa la varf noul element.

De exemplu, daca dorim sa inseram elementul x = 3 in stiva din figura urmatoare, obtinem:

stiva structuri de date

Extragerea unui element din stiva

Pentru a extrage un element dintr-o stiva S, trebuie sa verificam in primul rand daca exista elemente in stiva (daca stiva nu este vida). Daca da, retinem elementul de la varful stivei intr-o variabila (notam cu x), dupa care micsoram cu o unitate varful stivei.

De exemplu, daca extragem un element din stiva urmatoare, obtinem:

Extragere element din stiva

Prin modul sau restrictiv de functionare, stiva permite numai accesarea elementului de la varf. Daca dorim sa aflam valoarea unui alt element al stivei, ar trebui sa „golim” stiva (sa extragem succesiv elementele pana la elementul dorit).


2. Coada

La fel ca si stiva, coada este o structura de date abstracta. Insa, se diferentiaza de stiva prin modul sau prin care opereaza. Mai exact, operatia de inserare a unui element se realizeaza intr-un capat, pe cand operatia de extragere se realizeaza in celalalt capat.

Voi da un exemplu „real”, ca si la stiva. Toata lumea a stat la coada, macar o data. Orice situatie in care sunt mai multe cereri de acces la o resursa unica (mai multi clienti la o singura vanzatoare) necesita formarea unei „linii de asteptare”. Astfel, primul venit va fi primul care va plati produsele sau serviciile unei firme, iar ultimul venit va fi si ultimul care va plati produsele.

Coada, structuri de date

Executarea unor operatii asupra unei cozi presupune cunoasterea inceputului cozii, respectiv sfarsitul.

Fiecare introducere a unor elemente in coada se face, in mod logic, la sfarsitul cozii. Iar in cazul unei extrageri, primul element din coada va fi extras.


Care este utilitatea unei cozi?

Este necesara utilizarea unei cozi atunci cand informatiile trebuie prelucrate exact in ordinea in care „au sosit” si ele sunt retinute in coada pana cand pot fi prelucrate. In informatica, cozile sunt utilizate frecvent. De exemplu, sa consideram ca avem o retea de calculatoare si o singura imprimanta. Cand utilizatorii retelei vor da comenzi de tiparire, imprimanta nu poate raspunde tuturor comenzilor in acelasi timp. Prin urmare, comenzile de tiparire primite sunt inregistrate intr-o coada. Imprimanta va tipari documentele pe rand, in ordinea in care au fost inregistrate in coada. Un alt exemplu: pentru a mari viteza de executie, microprocesoarele Intel utilizeaza o coada de instructiuni in care sunt memorate instructiunile ce urmeaza a fi executate.


Cum implementam o coada?

Coada poate fi implementata in diferite moduri. Ca si in cazul stivei, coada poate fi implementata static, retinand elementele sale intr-un vector.

Sa consideram urmatoarele declaratii care reprezinta o coada cu elemente de tip int alocata static:

Crearea unei cozi vide

Pentru a crea o coada vida trebuie sa initializam variabilele Inceput si Sfarsit astfel:


Inserarea unui element in coada

Pentru a insera un element in coada trebuie sa verificam in primul rand daca „avem loc”, exact ca la stiva. Daca variabila Sfarsit nu depaseste dimensiunea maxima a vectorului, treaba e buna. Daca inserarea se poate face, vom mari valoarea variabilei Sf cu o unitate (coada „creste”) si vom plasa la sfarsit noul element.

De exemplu, daca inseram elementul x = 3 in coada vom obtine:

Adaugare element in coada

Extragerea unui element din coada

Pentru a extrage un element din coada trebuie sa verificam daca numarul de elemente din coada este diferit de 0 (coada nu este vida). Daca da, retinem elementul de la inceputul cozii intr-o variabila (notata x), dupa care marim cu o unitate inceputul cozii.

extragere element din coada

Concluzie stiva si coada

Cam asta este tot cu stiva si coada. La bacalaureat se da doar exercitii simple precum adaugarea/extragerea unui element din stiva/coada. La acest tip de exercitiu trebuie sa stii doar teoria, nu te va pune sa scrii cod. Insa, e bine ca pe viitor sa stii cum functioneaza stiva si coada si sa stii cum sa-i aplici.

Pentru nelamuriri, lasati un comentariu.

Vlad

Fac doar lucruri care-mi plac, care-mi aduc motivatie si fericire, nu material.

Lasă un răspuns

Adresa ta de email nu va fi publicată. Câmpurile obligatorii sunt marcate cu *