punerea în aplicare listă legată de stivă

în loc de a folosi matrice, putem folosi, de asemenea, lista legată de a pune în aplicare stivă. Lista legată alocă memoria dinamic. Cu toate acestea, complexitatea timpului în ambele scenarii este aceeași pentru toate operațiunile, adică push, pop și peek.

în punerea în aplicare listă legată de stivă, nodurile sunt menținute non-contiguously în memorie. Fiecare nod conține un pointer la nodul său succesor imediat în stivă. Se spune că stiva este suprasolicitată dacă spațiul rămas în heap-ul de memorie nu este suficient pentru a crea un nod.

cel mai mare nod din stivă conține întotdeauna null în câmpul său de adresă. Permite discuta modul în care, fiecare operație este efectuată în punerea în aplicare listă legată de stivă.

adăugarea unui nod la stivă (operație Push)

adăugarea unui nod la stivă este denumită operație push. Împingerea unui element într-o stivă în implementarea listei legate este diferită de cea a unei implementări matrice. Pentru a împinge un element pe stivă, sunt implicați următorii pași.

1. creați mai întâi un nod și alocați-i memorie.
2. dacă lista este goală, atunci elementul va fi împins ca nod de pornire al listei. Aceasta include atribuirea valorii părții de date a nodului și atribuirea null părții de adresă a nodului.
3. dacă există deja unele noduri în listă, atunci trebuie să adăugăm noul element la începutul listei (pentru a nu încălca proprietatea stivei). În acest scop, atribuiți adresa elementului de pornire câmpului de adresă al noului nod și faceți noul nod, nodul de pornire al listei.

complexitatea timpului: o(1)



c implementation:

ștergerea unui nod din stivă (POP operation)

ștergerea unui nod din partea de sus a stivei este denumită Pop operation. Ștergerea unui nod din lista legată implementarea stivei este diferită de cea din implementarea matricei. Pentru a scoate un element din stivă, trebuie să urmăm următorii pași :

1. verificați dacă există condiția underflow: condiția underflow apare atunci când încercăm să ieșim dintr-o stivă deja goală. Stiva va fi goală dacă indicatorul de cap al listei indică null.
2. reglați indicatorul capului în consecință: în stivă, elementele sunt afișate doar de la un capăt, prin urmare, valoarea stocată în indicatorul capului trebuie ștearsă și nodul trebuie eliberat. Următorul nod al nodului capului devine acum nodul capului.

Complexitatea Timpului : o (n)

implementarea C

afișarea nodurilor (Traversare)

afișarea tuturor nodurilor unei stive necesită traversarea tuturor nodurilor listei legate organizate sub formă de stivă. În acest scop, trebuie să urmăm următorii pași.

1. copiați indicatorul capului într-un indicator temporar.
2. mutați indicatorul temporar prin toate nodurile listei și imprimați câmpul de valoare atașat fiecărui nod.

Complexitatea Timpului : o(n)

implementarea C

programul condus de meniu în C implementarea tuturor operațiunilor de stivă utilizând lista legată :