TechCodeview

Anstatt ein Array zu verwenden, können wir auch eine verknüpfte Liste verwenden, um den Stapel zu implementieren. Die verknüpfte Liste weist den Speicher dynamisch zu. Allerdings ist die zeitliche Komplexität in beiden Szenarios für alle Vorgänge, d. h. Push, Pop und Peek, gleich.

Bei der Implementierung einer verknüpften Liste des Stapels werden die Knoten nicht zusammenhängend im Speicher verwaltet. Jeder Knoten enthält einen Zeiger auf seinen unmittelbaren Nachfolgerknoten im Stapel. Von einem Stack-Überlauf spricht man, wenn der verbleibende Speicherplatz im Speicher-Heap nicht ausreicht, um einen Knoten zu erstellen.

Der oberste Knoten im Stapel enthält immer Null in seinem Adressfeld. Lassen Sie uns die Art und Weise besprechen, wie jede Operation in der Implementierung einer verknüpften Liste des Stapels ausgeführt wird.

Hinzufügen eines Knotens zum Stapel (Push-Vorgang)

Das Hinzufügen eines Knotens zum Stapel wird als bezeichnet drücken Betrieb. Das Verschieben eines Elements auf einen Stapel in der Implementierung einer verknüpften Liste unterscheidet sich von dem einer Array-Implementierung. Um ein Element auf den Stapel zu schieben, sind die folgenden Schritte erforderlich.

1. Erstellen Sie zunächst einen Knoten und weisen Sie ihm Speicher zu.
2. Wenn die Liste leer ist, muss das Element als Startknoten der Liste verschoben werden. Dazu gehört die Zuweisung eines Werts zum Datenteil des Knotens und die Zuweisung von Null zum Adressteil des Knotens.
3. Wenn die Liste bereits einige Knoten enthält, müssen wir das neue Element am Anfang der Liste hinzufügen (um die Eigenschaft des Stapels nicht zu verletzen). Weisen Sie dazu die Adresse des Startelements dem Adressfeld des neuen Knotens zu und machen Sie den neuen Knoten zum Startknoten der Liste.

Zeitkomplexität: o(1)





C-Implementierung:

 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'); } } 

Einen Knoten vom Stapel löschen (POP-Vorgang)

Das Löschen eines Knotens von der Oberseite des Stapels wird als bezeichnet Pop Betrieb. Das Löschen eines Knotens aus der Linked-List-Implementierung des Stacks unterscheidet sich von dem in der Array-Implementierung. Um ein Element vom Stapel zu entfernen, müssen wir die folgenden Schritte ausführen:

Überprüfen Sie die Unterlaufbedingung:Die Unterlaufbedingung tritt auf, wenn wir versuchen, von einem bereits leeren Stapel zu springen. Der Stapel ist leer, wenn der Kopfzeiger der Liste auf Null zeigt.Passen Sie den Kopfzeiger entsprechend an:Im Stapel werden die Elemente nur von einem Ende entfernt, daher muss der im Kopfzeiger gespeicherte Wert gelöscht und der Knoten freigegeben werden. Der nächste Knoten des Kopfknotens wird nun zum Kopfknoten.

Zeitkomplexität: o(n)

C-Implementierung

 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'); } } 

Knoten anzeigen (Traversieren)

Um alle Knoten eines Stapels anzuzeigen, müssen alle Knoten der verknüpften Liste durchlaufen werden, die in Form eines Stapels organisiert ist. Zu diesem Zweck müssen wir die folgenden Schritte ausführen.

1. Kopieren Sie den Kopfzeiger in einen temporären Zeiger.
2. Bewegen Sie den temporären Zeiger durch alle Knoten der Liste und drucken Sie das an jeden Knoten angehängte Wertfeld aus.

Zeitkomplexität: o(n)

C-Implementierung

 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; } } } 

Menügesteuertes Programm in C, das alle Stapeloperationen mithilfe einer verknüpften Liste implementiert:

 #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; } } }