Clasa a IX-a lecția 15 - 15 feb 2020
Clasament teme lecțiile 1 - 14
Pe categorii
Divizori / Primalitate / Ciur
Sortari
Matrici
Cautare binara
Stivă
Generale
Concursuri
Lecție
Stivă
Am mai auzit de acest termen în lecțiile de la început, când v-am dat exemple de memoria "globală" versus cea de pe stivă. Pe lângă vectori, stiva este prima structură de date mai "specială" despre care învățăm.
Definiție
Stiva este o structură de date de tip LIFO (last in, first out). Asta înseamnă că elementele sunt adăugate în ordine (ca într-un vector obișnuit), dar ele trebuiesc scoase în ordinea inversă adăugării lor. Un exemplu bun de structură de stivă din viața reală este un teanc de farfurii: putem oricând să adăugăm o farfurie în teanc deasupra tuturor celorlalte, dar dacă vrem să începem să scoatem farfurii din teanc, va trebui să începem cu ultima farfurie adăugată (în practică putem să scoatem și farfurii care au fost adăugate mai devreme, dar de dragul teoriei vom presupune că acestea sunt foarte fragile și este interzis să facem asta).
Implementare
Având în vedere definiția stivei, în implementarea structurii de date de tip stivă sunt în general necesare următoarele operații:
- push(value) - inserează o valoare în capătul stivei
- pop - șterge valoarea din capătul stivei
- top - returnează valoarea din capătul stivei
- size - returnează numărul de elemente din stivă
Exemplu implementare (sursă IQAcademy):
#define MAXN 1000
int stack[MAXN]; // stocarea valorilor propriu-zise
int stack_pointer = 0; // indice la prima valoare nefolosita in vector (totuna cu numărul de elemente din stiva)
// adauga valoarea 'val' la stiva, daca aceasta nu este plina
// returneaza 1 in caz de succes, 0 in caz de stiva plina
int push( int val ) {
if ( stack_pointer >= MAXN ) // stiva este plina?
return 0; // returnam eroare
stack[stack_pointer++] = val; // adaugam valoarea in stiva
return 1; // returnam succes
}
// returnează valoarea aflată în virful stivei, dacă ea exista
// in caz contrar returneaza -1
int top() {
return stack_pointer > 0 ? stack[stack_pointer - 1] : -1;
}
// elimina ultimul element din stiva daca se poate
// returneaza 1 daca operatia a reusit, 0 in caz de eroare
int pop() {
if ( stack_pointer == 0 ) // testam cazul de eroare
return 0;
stack_pointer--; // daca avem elemente pe stiva, il eliminam pe ultimul
return 1;
}
// returneaza numarul de elemente din stiva
int size() {
return stack_pointer;
}Aplicații
paranteze1 - varena
parantezare - infoarena
Soluții aici [1]
Temă
paranteze1 - varena
parantezare - infoarena
bile2 - varena
turn - varena
trompeta - infoarena
