zamiast używać tablicy, możemy użyć linked list do implementacji stosu. Lista powiązana przydziela pamięć dynamicznie. Jednak złożoność czasowa w obu scenariuszach jest taka sama dla wszystkich operacji tj. push, pop i peek.
w linked list implementacja stosu, węzły są utrzymywane w pamięci non-contiguously. Każdy węzeł zawiera wskaźnik do jego bezpośredniego następcy w stosie. Mówi się, że stos jest przepełniony, jeśli przestrzeń pozostawiona w stosie pamięci nie wystarcza do utworzenia węzła.
najwyższy węzeł w stosie zawsze zawiera null w polu adresu. Omówmy sposób, w jaki każda operacja jest wykonywana w linked list implementacji stosu.
dodawanie węzła do stosu (operacja Push)
dodawanie węzła do stosu jest określane jako operacja push. Wypychanie elementu do stosu w implementacji list połączonych różni się od implementacji tablic. Aby wcisnąć element na stos, należy wykonać następujące kroki.
- najpierw Utwórz węzeł i przydziel mu pamięć.
- jeżeli lista jest pusta, wtedy element ma zostać wypchnięty jako węzeł początkowy listy. Obejmuje to przypisanie wartości do części danych węzła i przypisanie null do części adresowej węzła.
- jeśli na liście są już jakieś węzły, to musimy dodać nowy element na początku listy (aby nie naruszać właściwości stosu). W tym celu Przypisz adres elementu startowego do pola adresu nowego węzła i utwórz nowy węzeł, węzeł początkowy listy.
- Sprawdź warunek underflow: warunek underflow występuje, gdy próbujemy wyskoczyć z już pustego stosu. Stos będzie pusty, jeśli wskaźnik head na liście wskazuje na null.
- Dostosuj wskaźnik head odpowiednio: w stosie elementy są wyskakiwane tylko z jednego końca, dlatego wartość zapisana w wskaźniku head musi zostać usunięta, a węzeł musi zostać uwolniony. Następny węzeł węzła głównego staje się węzłem głównym.
- skopiuj wskaźnik head do wskaźnika tymczasowego.
- przesuń wskaźnik tymczasowy przez wszystkie węzły listy i wydrukuj pole wartości dołączone do każdego węzła.
złożoność czasowa: o(1)
implementacja C :
usuwanie węzła ze stosu (operacja POP)
usuwanie węzła z góry stosu jest określane jako operacja pop. Usunięcie węzła z listy powiązanej implementacja stosu różni się od implementacji tablicy. Aby usunąć element ze stosu, musimy wykonać następujące kroki :
Złożoność Czasowa : O (N)
C implementacja
wyświetlanie węzłów (trawersowanie)
wyświetlanie wszystkich węzłów stosu wymaga trawersowania wszystkich węzłów połączonej listy zorganizowanej w formie stosu. W tym celu musimy wykonać następujące kroki.
Złożoność Czasowa : O (N)