Stiva

În programare se lucrează cu date concrete. Avem tipuri de date (numere întregi, numere cu virgulă, caractere, etc.) și avem structuri de date ce  organizează aceste tipuri de date.

După cum se zice: unealta perfectă pentru o treabă bine făcută. Diferitele structuri de date se pretează pentru diferite obiective.

Stiva (cunoscută și ca Steven) este o structură de date de tip LIFO (Last In First Out) - Ultimul venit, primul ieșit.

În alte cuvinte avem o orânduire de informații (pot fi numere întregi, persoane sau mașini) unde ne interesează să lucrăm mereu cu ultima informație primită. Știu, statul la coadă ar fi extrem de enervant dacă mereu ultimul care vine este cel servit. S-ar duce pe apa Sâmbetei idea de a fi primul la coadă. Însă dacă avem de-a face cu situații în care știm că ce am făcut înainte este bine, atunci ne putem concentra pe ce trebuie făcut acum.

Un exemplu pentru o stivă ar fi ordonarea după înălțime. Presupunem că avem primii 3 aranjați corect și ne-au mai rămas doi. Alegem pe unul din ei, punem al patrulei și apoi îl adăugăm pe al cincilea. Dar nu e bine, trebuie inversați. Așa e când diferența e doar de un centimetru. Ce facem? Îi inversăm. Sau, dacă ar fi să ne luăm după operațiile permise pe o stivă, scoatem pe al V-lea, scoatem pe al IV-lea, și apoi îi punem înapoi în cealaltă ordine. Și avem o stivă.

Altfel o stivă ne-o putem imagina ca o serie de cărți (bolovani) puse una peste alta. Ca să o luăm pe a doua trebuie să dăm la o parte cele de deasupra. Dacă avem putere le ridicăm pe toate deodată, altfel luăm cât putem. O stivă este la fel cu un teanc.

Operații permise pentru o stivă

• adăugarea unui element
• ștergerea lui (extragerea sau scoaterea unui element din stivă)
• accesarea elementului curent
• verificare dacă stiva e goală

Nu e mare filozofie. Practic o stivă are o dimensiune (exact ca numărul de cărți puse una peste alta) și operațiile normale pe care orice le-ar face cu un astfel de teanc.

Implementarea

Stivele de obicei se bazează pe vectori (șiruri) căci e ușor să se adauge sau să se șteargă elemente dintr-una. Limbajele de programare toate oferă astfel de operații. Ba chiar mai mult, se poate și trișa căci într-o stivă implementată ca șir se pot accesa direct elementele sale, nu numai ultimul.

O altă implementare se bazează pe pointeri și liste înlănțuite. În acest caz e mai greu să trișăm fiindcă fiecare element va conține informația utilă cât și adresa elementului anterior. Primul element va avea adresa elementului nul, al doilea va avea adresa primului element și tot așa. Nu că e imposibil să trișăm și cu ele.

Utilizare

Stivele sunt folosite în primul rând în backtracking. Altfel spus, în probleme de genul: „Să se genereze toate soluțiile/numerele care/pentru...”. Ele mai sunt folosite în quicksort. Sau sunt folosite de procesor pentru a reține locul următoarei instrucțiuni la executarea unei subrutine.

Cum?

Într-un executabil instrucțiunile sunt succesive. Însă când se face apelul unei subrutine, pointerul care ține cont unde are următoarea instrucțiune în memorie sare în altă parte și pentru a ști unde să revină, procesorul are o stivă unde păstrează această valoare. Se adaugă un nou nivel în stivă cu prima instrucțiune din subrutină, se execută una după alta până la sfârșitul ei, ca apoi să se "scoată" ultimul nivel din stivă. Și pe nivelul anterior este fix adresa următoarei instrucțiuni după apelarea subrutinei. Șmecherie.

Stive.