Implementarea stivei (cu vectori)

  

    Un aspect al programării care nu este deloc clar celor care sunt la început este acela că programarea nu înseamnă doar instrucțiuni prin care îi spui calculatorului ce acțiuni să efectueze.

    Bineînțeles că acesta este aspectul cel mai important și care e resonsabil de rezultatele pe care le vezi atunci când execuți un program.

    Dar asta nu e totul.  Programarea mai înseamnă și altceva. Un altceva foarte important, fără de care acțiunile de care vorbim nu ar avea putere.

    Acel altceva sunt structurile de date.

    Dacă ar fi să scriu într-un soi de formulă matematică simplă ce înseamnă un program, ar ieși ceva de genul:

       Program = Date + Instrucțiuni

(Am vorbit despre asta și în explicațiile de la jocul de labirint.)

 

    Deja ai lucrat cu structuri de date. Vectorii sunt cele mai simple structuri de date. (Iar matricile reprezintă de fapt generalizarea vectorilor pentru cazul bidimensional (adică în două dimensiuni: linii și coloane).)

    În articolul asta o să te joci cu o structura de date puțin mai restrictivă decât un vector, dar care poate fi implementată cu mare ușurință folosind un vector și o variabilă (simplă).


        Stivă

    Cu siguranță știi ce e o stivă. Dacă nu, ia o cutie de carton și pune în ea o carte. Apoi mai pune o carte peste prima carte. Și încă o carte peste a două.

    OK?

    Acum ai trei cărți (situate una peste altă) în stivă.

    Scoate o carte.

    Evident, vei scoate ultima carte pusă (adică cea care e situată în vârful stivei).

 

    Te-ai prins cum funcționează o stivă?

    (1) Poți pune elemente în ea doar în vârf (peste ultimul element pus).

    (2) Și poți scoate elemente din ea doar de la vârf.

    Ultimul element introdus în stivă este primul care va fi scos (atunci când va fi cazul să scoți un element din ea). În limba engleză la treaba asta îi zice LIFO (Last În, First Out).


        Cum se implementează o stivă

    Cel mai simplu poți implementa o stivă folosind un vector S (cu un număr de elemtne suficient de mare pentru a încăpea în el toate elementele care se vor adaugă în stivă la vreun moment dat) și o variabilă v (în care se va memora indicele poziției din vector de deasupra ultimului element din stivă).

    Desenul următor vrea să explice cele spuse în paragraful anterior.

    Prin urmare, atunci când vrei să adaugi un element în stivă faci așa:

       S[v] = element_nou;
       v = v+1;

    Iar atunci când vrei să scoți un element din stivă, faci așa:

       v = v-1;
       element_scos = S[v];

 

    Inițial, când stivă e goală, v va avea valoarea 0. (Adică vârful stivei va indică baza stivei.)

    Valoarea lui v poate fi interpretată și că fiind numărul de elemente existente în stivă.


Link articol: https://igotopia.ro/cum-implementezi-o-stiva-folosind-un-vector/

Mulțumim, Florin Bîrleanu



x
Acest website utilizează cookie-uri pentru a creea o experiență cât mai plăcută. Învață mai multe Acceptă