Wie kommt es zu einem Stack Overflow, wenn wir die verkettete Liste für die Stack-Implementierung verwenden?

Question

Ich bin neu in Stacks. Wie wir wissen, wenn nicht genug Platz im Stapel vorhanden ist und wir ein Element in den Stapel schieben wollen, dann ist der Stapel in Überlauf Zustand. Dies wird auftreten, wenn wir die Array-basierte Implementierung des Stacks verwenden, da wir die Kapazität des Arrays definieren müssen. Wenn wir ein Element über die Kapazität hinaus schieben wollen, wird der Überlauf auftreten, aber Wenn wir die verkettete Liste für die Stack-Implementierung verwenden, dann wie wird der Stack-Overflow auftreten? In der verketteten Liste müssen wir keine Kapazität definieren, sie ordnen dynamisch Speicher für Knoten zu. Bitte helfen Sie mir, das Problem zu erkennen. Danke im Voraus.

Answer 1

Sie haben recht, dass es bei der verketteten Liste nicht notwendig ist, ihre Kapazität in Bezug auf die Anzahl der Elemente zu definieren. Aber für die Elemente wird immer noch Speicher benötigt - und Gedächtnismüdigkeit kann passieren.

Das Ausführen einer Stapelimplementierung als Liste würde zu einer langsameren Leistung führen (weil Zuweisungen/Aufteilungen häufiger durchgeführt werden müssen), noch mehr verschachtelt, wenn Sie berücksichtigen, dass Speicherblöcke mit unterschiedlicher Größe auf Stapel zugeordnet werden müssen. Der Stack wird so umfassend genutzt, dass eine Verlangsamung seiner Implementierung wahrscheinlich prohibitiv wäre.

Auch Verwaltung von Listen ist schwieriger - und Sie müssen Stack z. fügen Sie mehr als ein Element gleichzeitig hinzu, oder "verkürzen" Sie den Stapel in einer Operation (mehrere Elemente darauf übernehmen/vergessen, z. B. wenn Sie von einem Funktionsaufruf zurückkehren) usw. Unidirektionale Listen eignen sich nur gut zum Anhängen/Entfernen eines Elements an deren Ende.

Gibt es ein bestimmtes Problem, das Sie lösen werden? Bedenken Sie, dass ein Stack-Überlauf nicht nur bei großen Datenstrukturen auftreten kann, sondern auch bei einer zu tiefen Rekursion.

Answer 2

Ich empfehle, Linked List zu verwenden. Wie ich weiß, gibt es keine Stack Overflows in Linked List. Aus diesem Grund verwenden wir diese Datenstruktur anstelle von Array-Implementierungen wie Listen, Stacks. Die Implementierung der verknüpften Liste ist langwierig (Sie können jedoch vordefinierte Bibliotheken verwenden) und eine hohe Cache-Nutzung. Aber es ist geeignet für die Speicherung von Daten auf dynamischen Größen, da es die Eigenschaft hat, Speicher für die Knoten dynamisch zuzuweisen, wie Sie oben erwähnt haben.
Hoffe das hilft!