Zamiast używać tablicy, możemy również użyć listy połączonej do zaimplementowania stosu. Lista połączona dynamicznie przydziela pamięć. Jednak złożoność czasowa w obu scenariuszach jest taka sama dla wszystkich operacji, tj. Push, pop i peek.

W implementacji stosu z listą połączoną węzły są utrzymywane w pamięci w sposób nieciągły. Każdy węzeł zawiera wskaźnik do jego bezpośredniego następcy na stosie. Stos mówi się, że jest przepełniony, jeśli ilość wolnego miejsca na stercie pamięci jest niewystarczająca do utworzenia węzła.

Węzeł znajdujący się najwyżej na stosie zawsze zawiera wartość null w swoim polu adresu. Omówmy sposób, w jaki każda operacja jest wykonywana w implementacji stosu na liście połączonej.

lista tablic w Javie

Dodanie węzła do stosu (operacja Push)

Dodanie węzła do stosu nazywa się naciskać operacja. Wypychanie elementu na stos w implementacji listy połączonej różni się od implementacji tablicy. Aby wepchnąć element na stos, należy wykonać następujące kroki.

1. Najpierw utwórz węzeł i przydziel mu pamięć.
2. Jeżeli lista jest pusta to 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 wartości null do części adresowej węzła.
3. Jeśli na liście są już jakieś węzły, to musimy dodać nowy element na początku listy (aby nie naruszyć właściwości stosu). W tym celu przypisz adres elementu początkowego do pola adresowego nowego węzła i uczyń nowy węzeł węzłem początkowym listy.

Złożoność czasowa: o(1)





Implementacja języka C:

 void push () { int val; struct node *ptr =(struct node*)malloc(sizeof(struct node)); if(ptr == NULL) { printf('not able to push the element'); } else { printf('Enter the value'); scanf('%d',&val); if(head==NULL) { ptr->val = val; ptr -> next = NULL; head=ptr; } else { ptr->val = val; ptr->next = head; head=ptr; } printf('Item pushed'); } } 

Usuwanie węzła ze stosu (operacja POP)

Usuwanie węzła ze szczytu stosu nazywa się Muzyka pop operacja. Usuwanie węzła z implementacji listy połączonej stosu różni się od usuwania węzła w implementacji tablicy. Aby zdjąć element ze stosu, musimy wykonać następujące kroki:

lista religii

Sprawdź stan niedomiaru:Warunek niedopełnienia występuje, gdy próbujemy wyskoczyć z już pustego stosu. Stos będzie pusty, jeśli wskaźnik nagłówka listy wskazuje wartość null.Dostosuj odpowiednio wskaźnik głowy:Na stosie elementy są wysuwane tylko z jednego końca, dlatego wartość przechowywana we wskaźniku nagłówka musi zostać usunięta, a węzeł musi zostać zwolniony. Następny węzeł węzła głównego staje się teraz węzłem głównym.

Złożoność czasowa: o(n)

aktor chiranjeevi

Implementacja języka C

 void pop() { int item; struct node *ptr; if (head == NULL) { printf('Underflow'); } else { item = head->val; ptr = head; head = head->next; free(ptr); printf('Item popped'); } } 

Wyświetl węzły (Przemierzanie)

Wyświetlenie wszystkich węzłów stosu wymaga przejścia przez wszystkie węzły połączonej listy zorganizowanej w formie stosu. W tym celu musimy wykonać następujące kroki.

1. Skopiuj wskaźnik głowy do wskaźnika tymczasowego.
2. Przesuń tymczasowy wskaźnik przez wszystkie węzły listy i wydrukuj pole wartości dołączone do każdego węzła.

Złożoność czasowa: o(n)

Implementacja C

 void display() { int i; struct node *ptr; ptr=head; if(ptr == NULL) { printf('Stack is empty
'); } else { printf('Printing Stack elements 
'); while(ptr!=NULL) { printf('%d
',ptr->val); ptr = ptr->next; } } } 

Program sterowany menu w C realizujący wszystkie operacje na stosie przy użyciu połączonej listy:

 #include #include void push(); void pop(); void display(); struct node { int val; struct node *next; }; struct node *head; void main () { int choice=0; printf('
*********Stack operations using linked list*********
'); printf('
----------------------------------------------
'); while(choice != 4) { printf('

Chose one from the below options...
'); printf('
1.Push
2.Pop
3.Show
4.Exit'); printf('
 Enter your choice 
'); scanf('%d',&choice); switch(choice) { case 1: { push(); break; } case 2: { pop(); break; } case 3: { display(); break; } case 4: { printf('Exiting....'); break; } default: { printf('Please Enter valid choice '); } }; } } void push () { int val; struct node *ptr = (struct node*)malloc(sizeof(struct node)); if(ptr == NULL) { printf('not able to push the element'); } else { printf('Enter the value'); scanf('%d',&val); if(head==NULL) { ptr->val = val; ptr -> next = NULL; head=ptr; } else { ptr->val = val; ptr->next = head; head=ptr; } printf('Item pushed'); } } void pop() { int item; struct node *ptr; if (head == NULL) { printf('Underflow'); } else { item = head->val; ptr = head; head = head->next; free(ptr); printf('Item popped'); } } void display() { int i; struct node *ptr; ptr=head; if(ptr == NULL) { printf('Stack is empty
'); } else { printf('Printing Stack elements 
'); while(ptr!=NULL) { printf('%d
',ptr->val); ptr = ptr->next; } } }