Anstelle von array können wir auch verknüpfte Listen verwenden, um stack zu implementieren. Verknüpfte Liste weist den Speicher dynamisch zu. Die Zeitkomplexität in beiden Szenarien ist jedoch für alle Vorgänge, dh Push, Pop und Peek, gleich.
Bei der Implementierung einer verknüpften Liste von stack werden die Knoten nicht zusammenhängend im Speicher verwaltet. Jeder Knoten enthält einen Zeiger auf seinen unmittelbaren Nachfolgeknoten im Stapel. Stack wird als überflogen bezeichnet, wenn der im Speicherheap verbleibende Speicherplatz 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 diskutieren, in der jede Operation in der verknüpften Listenimplementierung von stack ausgeführt wird.
Hinzufügen eines Knotens zum Stapel (Push-Operation)
Das Hinzufügen eines Knotens zum Stapel wird als Push-Operation bezeichnet. 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.
- Erstellen Sie zuerst einen Knoten und weisen Sie ihm Speicher zu.
- Wenn die Liste leer ist, wird das Element als Startknoten der Liste verschoben. Dies beinhaltet das Zuweisen von value zum Datenteil des Knotens und das Zuweisen von null zum Adressteil des Knotens.
- 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 dem Adressfeld des neuen Knotens die Adresse des Startelements zu und machen Sie den neuen Knoten zum Startknoten der Liste.
- Ü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: In stack werden die Elemente nur von einem Ende aus angezeigt, daher muss der im Kopfzeiger gespeicherte Wert gelöscht und der Knoten freigegeben werden. Der nächste Knoten des Kopfknotens wird nun zum Kopfknoten.
- Kopieren Sie den Kopfzeiger in einen temporären Zeiger.
- Bewegen Sie den temporären Zeiger durch alle Knoten der Liste und drucken Sie das an jeden Knoten angehängte Wertefeld aus.
Zeitkomplexität : o(1)
C Implementierung:
Löschen eines Knotens vom Stapel (POP-Operation)
Das Löschen eines Knotens vom oberen Rand des Stapels wird als Pop-Operation bezeichnet. Das Löschen eines Knotens aus der verknüpften Listenimplementierung von stack unterscheidet sich von dem in der Array-Implementierung. Um ein Element aus dem Stapel zu entfernen, müssen wir die folgenden Schritte ausführen :
Zeitkomplexität : o (n)
C Implementierung
Anzeige der Knoten (Durchlaufen)
Anzeige aller Knoten eines Stapels>Durchlaufen aller Knoten der verknüpften Liste in Form eines Stapels. Zu diesem Zweck müssen wir die folgenden Schritte ausführen.
Zeitkomplexität : o (n)