O stivă este o metodă de stocare a datelor în care elementul scris în depozitul de date este întotdeauna ultimul care urmează să fie recuperat mai întâi (disciplina LIFO este "ultima în - primul out"). Când eliminați un element, acesta este eliminat din stivă.
Luați în considerare cel mai simplu exemplu de utilizare a unui teanc. Să presupunem că există un șir constând doar din paranteze de deschidere și închidere. Este necesar să se stabilească dacă este vorba de o expresie validă a parantezei (adică pentru fiecare paranteză de deschidere trebuie să existe o expresie de încheiere). Zavedom matrice și o variabilă pentru a stoca numărul ultimului element semnificativ în matrice (adică, partea de sus a stivei), care va pune toate parantezele de deschidere (cu o creștere a numărului de top 1) atunci când trece pe linie, și la o întâlnire cu închidere va elimina deschiderea corespunzătoare (pur și simplu reduce numărul vârfului stivei). În cazul în care se dovedește că „a venit“ de închidere paranteze, iar stiva este goală (adică, numărul de sus este 0), expresia este greșită. Același lucru se poate spune și în cazul în care linia se termină și teancul nu este gol.
Evident, pentru a implementa un astfel de teanc, matricea nu este necesară pentru a fi utilizată, este suficient să se păstreze într-o variabilă numai numărul de paranteze de deschidere. Când o paranteză de închidere este primită de la variabila, se scade 1. Eroarea apare atunci când valoarea variabilei devine negativă sau când ajunge la capătul liniei, nu este zero.
Pentru datele de tip mai complex, stiva poate fi organizată utilizând o listă unidirecțională non-circulară. Pentru a pune un element pe stivă, trebuie să-l adăugați în partea de sus a listei pentru a extrage din stivă - obțineți datele primului element și apoi eliminați-l din listă.
Orice implementare de stive trebuie să conțină următoarele proceduri și funcții:
procedura InitStack - inițializați stiva;
procedură Push (d: tData) - puneți elementul pe teanc;
procedura Pop (var d: tData) - extrageți elementul din partea superioară a teancului;
function NotEmpty: boolean - verificati stiva pentru gol;
Coada diferă de stiva prin faptul că ultimul element care ajunge la acesta va fi extras ultimul, iar primul - primul ("FIFO"). Cu ajutorul listelor se poate organiza după cum urmează: vom stoca nu numai pointerul la "capul" listei, ci și "coada"; vom adăuga la "coada", și extrage - de la "cap".
Orice punere în aplicare a coadă (nu neapărat utilizarea listelor) ar trebui să fie "capabilă" să realizeze astfel de acțiuni:
procedura InitQueue - inițializarea coadă;
procedura AddQueue (d: tData) - pune elementul în coadă;
procedura SubQueue (var d: tData) - extrage elementul din coadă;
function NotEmpty: boolean - verificati coada pentru gol;
Articole similare
Trimiteți-le prietenilor: