Ein Stapel ist eine der grundlegenden Datenstrukturen, die in der Programmierung verwendet wird. Aber was ist eigentlich ein Stapel? Stellen wir uns vor, wir sind in der realen Welt und wir haben einen Stapel Teller. Wenn wir einen neuen Teller an die Spitze des Stapels legen, wird er aktuell. Wenn wir auf einen Teller zugreifen wollen, der sich irgendwo in der Mitte des Stapels befindet, müssen wir zuerst alle Teller, die sich oben befinden, entfernen.
Hier ist die Idee eines Stapels sehr ähnlich wie der Speicher in einem Computer funktioniert. Wenn das Programm gestartet wird, weist der Computer einen Speicherbereich zu, der als "Stack" bezeichnet wird. In diesem Speicherbereich speichert es alle Variablen und Funktionen, die im Programm verwendet werden.
Wenn eine Funktion aufgerufen wird, fügt der Computer sie dem Stapel hinzu. Dies bedeutet, dass das Programm vorübergehend zur Ausführung dieser Funktion wechselt. Alle Funktionsvariablen und Parameter werden ebenfalls auf dem Stapel gespeichert. Wenn die Funktion beendet wird, entfernt der Computer sie vom Stapel und setzt die Ausführung des Programms an der Stelle fort, an der es angehalten hat.
Daher spielt der Stapel eine wichtige Rolle bei der Organisation der Programmausführung. Es ermöglicht Ihnen, Informationen über aufgerufene Funktionen und deren Variablen zu speichern und deren Ausführung zu steuern. Wenn Sie die Arbeit des Stapels untersuchen, können Sie besser verstehen, wie Programme funktionieren und die verfügbaren Ressourcen so effizient wie möglich nutzen.
Was ist ein Stapel
Der Stapel kann sich als ein Tellerstapel vorstellen, auf dem nur die obere Platte entfernt oder hinzugefügt werden kann. Die erste Platte, die auf den Stapel gelegt wurde, wird als letzte entfernt (Prinzip LIFO - Last In, First Out).
Die grundlegenden Operationen, die Sie mit einem Stapel ausführen können, sind:
- push - Hinzufügen eines Elements an die Spitze des Stapels;
- pop - Entfernt ein Element von der Spitze des Stapels;
- peek - Abrufen des Werts eines Elements an der Spitze des Stapels, ohne ihn zu entfernen;
- isEmpty - Überprüfen, ob der Stapel leer ist;
- size - Ruft die Anzahl der Elemente auf dem Stapel ab.
Stacks werden häufig in der Programmierung verwendet, um verschiedene Aufgaben wie das Durchforsten von Bäumen, das Suchen in die Tiefe, die Speicheroperationen und viele andere zu lösen. Sie helfen bei der Verwaltung der Abfolge von Operationen und sorgen für Effizienz in verschiedenen Algorithmen.
Funktionsweise des Stapels
Wenn ein Element dem Stapel hinzugefügt wird, wird es oben auf dem Stapel platziert, und wenn das Element entfernt wird, wird nur das oberste Element des Stapels entfernt. Die übrigen Elemente verbleiben in der Reihenfolge auf dem Stapel, in der sie hinzugefügt wurden.
Das Prinzip des Stapels kann durch ein Beispiel aus dem Leben veranschaulicht werden: ein Stapel von Tellern. Wenn wir einen Teller auf die Oberseite des Stapels legen, wird er zur oberen Platte, und wir können nur diesen Teller verwenden oder entfernen. Die übrigen Teller bleiben so lange stehen, bis die obere Platte entfernt ist.
Der Stapel wird in vielen Algorithmen und Softwaredesigns verwendet, z. B. inverse polnische Schreibvorgänge, die Verarbeitung rekursiver Aufrufe und die Speicherverwaltung im Computer. Es ermöglicht Ihnen, Daten effizient zu verwalten und Elemente in konstanter Zeit hinzuzufügen und zu entfernen.
Grundlegende Stapeloperationen
Grundlegende Operationen, die mit einem Stapel ausgeführt werden können:
| Titel | Die Beschreibung |
|---|---|
| Push | Fügt ein Element an die Spitze des Stapels an. |
| Pop | Ruft ein Element von der Spitze des Stapels ab und gibt seinen Wert zurück. |
| Peek | Gibt den Wert des Elements an der Spitze des Stapels zurück, ohne es zu löschen. |
| IsEmpty | Überprüft, ob der Stapel leer ist. |
| IsFull | Überprüft, ob der Stapel voll ist. |
Mit dem Push-Vorgang können Sie neue Elemente an die Spitze des Stapels hinzufügen. Sie werden zu einem neuen Scheitelpunkt und verschieben den vorherigen Scheitelpunkt um eine Position nach unten. Auf diese Weise können Stapelelemente nur von oben hinzugefügt werden.
Mit dem Pop-Vorgang können Sie ein Element aus dem Scheitelpunkt des Stapels abrufen. Dadurch wird der Scheitelpunkt abgerufen und zurückgegeben, und das vorherige Element wird zum neuen Scheitelpunkt.
Mit dem Peek-Vorgang können Sie den Wert eines Elements abrufen, das sich oben auf dem Stapel befindet, ohne es zu löschen. Als Ergebnis der Operation bleibt der Stapel unverändert.
Die Operationen isEmpty und IsFull bestimmen, ob der Stapel leer oder bis zur maximalen Kapazität gefüllt ist. Diese Vorgänge können bei der Validierung nützlich sein, bevor Push- und Pop-Vorgänge ausgeführt werden.
Beispiel für die Verwendung eines Stapels
Stellen wir uns vor, wir haben die Aufgabe, eine Liste der Waren des Ladens zu erstellen, und wir möchten dies mit einem Stapel erreichen. In diesem Beispiel verwenden wir einen Stapel, um die Produktinformationen in der Reihenfolge zu speichern und zu verarbeiten, in der sie hinzugefügt werden.
Zuerst erstellen wir einen leeren Stapel. Jedes Mal, wenn wir Informationen über ein neues Produkt erhalten, werden wir es an die Spitze des Stapels legen. Der letzte hinzugefügte Artikel wird also immer oben auf dem Stapel sein, und der erste hinzugefügte Artikel befindet sich ganz unten.
Wenn wir eine Liste von Artikeln anzeigen müssen, können wir einfach alle Elemente des Stapels durchlaufen, beginnend mit dem oberen Element und endend mit dem unteren Element. Auf diese Weise werden die Produkte in der Reihenfolge angezeigt, in der sie hinzugefügt wurden.
Wenn wir einen Artikel aus der Liste entfernen müssen, entfernen wir ihn einfach vom oberen Rand des Stapels. Dadurch wird das nächste Produkt auf dem Stapel zum neuen oberen Element.
Die Verwendung eines Stapels zum Speichern einer Produktliste kann nützlich sein, wenn wir mit Daten arbeiten, die sich im Laufe der Zeit ändern oder aktualisieren können. Der Stapel ermöglicht es uns, Daten einfach hinzuzufügen, zu löschen und in der Reihenfolge anzuzeigen, die ihrer zeitlichen Reihenfolge entspricht, in der sie hinzugefügt werden.
| Ware | Preis |
|---|---|
| Milch | 50 griwna |
| Brot | 30 griwna |
| Die Eier | 40 griwna |
Erstellen eines Stapels
Eine einfache Möglichkeit, einen Stapel zu erstellen, besteht darin, ein Array zu verwenden. Dazu müssen Sie ein Array mit fester Größe deklarieren und eine Variable festlegen, die auf die Spitze des Stapels zeigt - also auf das zuletzt hinzugefügte Element.
In der Programmiersprache C++ könnte die Stapelerstellung beispielsweise folgendermaßen aussehen:
const int MAX_SIZE = 100;int stack[MAX_SIZE];int top = -1;In diesem Beispiel ein Array stack speichert Stapelelemente und eine Variable top zeigt auf die Spitze des Stapels. Der ursprüngliche Wert der Variablen top wird auf -1 gesetzt, da der Stapel leer ist.
Wenn dem Stapel ein neues Element hinzugefügt wird, ist der Wert der Variablen top erhöht sich um 1, und das neue Element wird an der entsprechenden Position des Arrays platziert. Wenn Sie ein Element aus dem Stapel entfernen, ist der Wert der Variablen top wird um 1 verkleinert, und das Element bleibt im Array und ist nicht verfügbar.
Dadurch können Sie die Daten effizient speichern und verwalten, sodass Sie in konstanter Zeit auf das zuletzt hinzugefügte Element zugreifen können.
Hinzufügen von Elementen zum Stapel
Mit der push() -Operation können Sie ein Element an die Spitze des Stapels hinzufügen. Das neue Element wird zum Scheitelpunkt des Stapels, und alle vorherigen Elemente bleiben an ihren Plätzen.
Das Hinzufügen eines Elements zum Stapel kann folgendermaßen dargestellt werden:
| Stapel vor dem Hinzufügen | Stapel nach dem Hinzufügen |
|---|---|
| Element N | Scheitelpunkt -> Element N |
| Element N-1 | Element N Scheitelpunkt -> Element N-1 |
| . | . |
| Element 2 | Element N Element N-1 . |
| Element 1 | Element N Element N-1 . Element 1 Scheitelpunkt -> Element 1 |
Wenn Sie dem Stapel also ein neues Element hinzufügen, wird es zum oberen Ende des Stapels, und alle vorherigen Elemente bleiben an ihren Plätzen und werden nach unten verschoben.
Elemente aus dem Stapel extrahieren
Zum Abrufen von Elementen aus dem Stapel wird der Vorgang "Auswerfen" oder "Löschen" verwendet. Mit der Auswurfoperation können Sie ein Element von der Oberseite des Stapels abrufen und daraus entfernen. Dies bedeutet, dass der Stapel nach Abschluss der Operation um ein Element kürzer wird.
Die Auswurfoperation ist die Hauptoperation, wenn Sie mit einem Stapel arbeiten. Wenn sich beispielsweise die Elemente 4, 3, 2, 1 auf dem Stapel befinden (wobei 1 das oberste Element ist), wird der Stapel beim Auswerfen in 4, 3, 2 geändert.
Wenn Sie ein Element aus dem Stapel extrahieren, müssen Sie den Typ des Elements im Auge behalten und entsprechend verwenden. Wenn beispielsweise ein Stapel ganze Zahlen enthält, muss das extrahierte Element als ganze Zahl verwendet werden.
Der Pull-Vorgang kann auch den Wert eines gelöschten Elements zurückgeben, sodass Sie ihn bei Bedarf später verwenden können.
Ein Beispiel: extrahieren von Elementen aus dem Stapel mithilfe der Auswurfoperation.
Stack stack = new Stack(); // Создание стека// Добавление элементов в стекstack.push("element 1");stack.push("element 2");stack.push("element 3");// Извлечение элементов из стекаSystem.out.println(stack.pop()); // "element 3"System.out.println(stack.pop()); // "element 2"System.out.println(stack.pop()); // "element 1"Praktisches Beispiel
Zum besseren Verständnis betrachten wir ein praktisches Beispiel mit einem Stack.
Stellen wir uns vor, wir haben einen Stapel von Tellern, die als Stapel angeordnet sind. Das Hinzufügen einer neuen Platte zum Stapel erfolgt von oben und das Herausnehmen von oben.
Nehmen wir an, wir möchten die Teller auf den Stapel legen: Zuerst legen wir Teller A auf den Tisch, dann Teller B und schließlich Teller C. Jetzt sieht unser Stapel wie folgt aus:
- Teller C (oben auf dem Stapel)
- Teller B
- Platte A (Stapelbasis)
Wenn wir die Platte aus dem Stapel entfernen wollen, werden wir die Teller in umgekehrter Reihenfolge entfernen, indem wir zuerst die Platte C, dann die Platte B und schließlich die Platte A entfernen.
Daher ermöglicht es uns ein Stapel mit seinem Arbeitsprinzip, Elemente nur von der Oberseite der Struktur in den Daten hinzuzufügen und zu extrahieren. Dies ist in vielen Fällen praktisch, in denen eine bestimmte Vorgehensweise befolgt werden muss.
Stack in der Programmierung
Ein Stapel in der Programmierung ist eine unidirektionale Kette von Datenelementen, wobei jedes Element einen Zeiger auf das nächste Element und die Daten enthält. Der Stapel kann als ein Turm aus Tellern dargestellt werden, wobei jede neue Platte oben hinzugefügt und von oben herausgenommen wird.
Stacks werden häufig in der Programmierung verwendet, um verschiedene Aufgaben zu lösen. Ein Beispiel für die Verwendung eines Stapels ist das Speichern von Rückgabeadressen in Funktionen. Wenn die Funktion aufgerufen wird, wird die Rückgabeadresse auf den Stapel gelegt, und wenn die Funktion beendet ist, wird die Adresse aus dem Stapel abgerufen und die Steuerung wird an den Aufrufpunkt zurückgegeben.
Der Stapel wird auch zum Ausführen von Speichervorgängen wie Speicherzuweisung und -freigabe verwendet. Wenn Speicher zugewiesen wird, wird der entsprechende Speicherblock dem Stapel hinzugefügt, und wenn der Speicher freigegeben wird, wird der Speicherblock vom Stapel abgerufen.
Das Verständnis der Arbeit eines Stapels in der Programmierung ist für Entwickler wichtig, da viele Algorithmen und Datenstrukturen (z. B. das Durchforsten eines Baumes in die Tiefe oder rekursive Algorithmen) auf der Verwendung des Stapels basieren. Durch die Verwendung eines Stapels können Sie Ihre Daten effizient verwalten und komplexe Aufgaben einfacher lösen.
