WikiDer > Stapel (Computer)

Stack (informatica)
Stapel mit den Operationen drücken und Puppe.

EIN Stapel oder Stapel ist in der Informatik ein Datenstruktur zum Speichern einer unterschiedlichen Anzahl von Elementen, wobei wie bei einem regulären Stack das zuletzt hinzugefügte Element zuerst abgerufen wird. Dieses Prinzip wird auch genannt LIFO (Zuletzt rein, zuerst raus) erwähnt.

Das Gegenstück zum Stapel ist der Warteschlange, die nach FIFO (Als Erster rein, als erster raus) Prinzip funktioniert.

Datenstruktur

Die Operationen, die auf einen Stapel angewendet werden können, sind:

  • drücken: platziert das angegebene Element auf dem Stack.
  • Puppe: Nimmt das oberste Element des Stapels und gibt es zurück.

Andere Anweisungen, exklusiv für a Aufrufliste, sein:

  • Anruf: das Programm zähler wird auf den Stack gelegt und die Ausführung an anderer Stelle fortgesetzt.
  • Rückkehr: Puppe zum Programmzähler. Als Ergebnis wird es Anruf unterbrochenes Programm wird fortgesetzt.

Manchmal werden noch unterstützt:

  • ist leer oder Null: Vorräte wahr leuchtet, wenn der Stack leer ist und kann als Schutz für a . dienen Stapelunterlauf.
  • oben (oder spähen): gibt das oberste Element des Stapels zurück, ohne es zu subtrahieren; kann simuliert werden, wenn der Stack von jeweils einem Thread verwendet wird.

Ein Stapel kann mit einem Bretterstapel verglichen werden: Das letzte auf dem Stapel platzierte Brett wird zuerst genommen. Ein noch besserer Vergleich ist ein Stack wie in a Tellerwagen, wobei nur das obere Element sichtbar ist und der Rest im Innenraum verschwindet.

Ein Stack kann implementiert werden als a verlinkte Liste, oder, wenn die Größe begrenzt ist, als a Array, jetzt sofort Zeiger die auf das letzte Stapelelement zeigt.

Bei falscher Verwendung können zwei Fehler auftreten:

  • Stapelunterlauf: ein PuppeBetrieb auf einem leeren Stack. Das hätte der Anrufer vorhersehen müssen: Es deutet auf einen Programmierfehler hin.
  • Paketüberfluss: ein drückenBetrieb auf einem vollen Stack.

Stapel in der Programmausführung

sehen Aufrufliste für den Hauptartikel zu diesem Thema.

Ein sogenanntes Aufrufliste wird beim Anrufen verwendet Unterprogramme im Computer Programms. Das Programm zähler, das sich auf die nächste auszuführende Anweisung bezieht, ist eines der Elemente, die gespeichert und abgerufen werden. Der Stapelzeiger zeigt auf die Spitze des Stapels. Der Stack kann auch für lokale Variablen verwendet werden.

Beim Aufruf einer Prozedur passiert folgendes:

  1. die Aktualparameter werden auf den Stack gelegt.
  2. der aktuelle Programmzähler wird darauf gesetzt.
  3. darauf wird der Basiszeiger (auch Framezeiger genannt) gelegt. Dieser Basiszeiger wird verwendet, damit man weiß, wo der aktuelle Stapelrahmen beginnt.
  4. Der Stapelzeiger wird mit dem Basiszeiger gleichgesetzt, sodass sie auf dasselbe Element auf dem Stapel zeigen.
  5. Speicher wird frei (Stackspace) für die lokalen Variablen. Dies geschieht durch Verschieben des Stapelzeigers.

Nach der Durchführung des Verfahrens geschieht Folgendes:

  1. der Stapelzeiger wird dem Basiszeiger gleichgesetzt, wodurch alle lokalen Variablen 'entfernt' werden (sie sind noch da, werden aber später überschrieben).
  2. der Basiszeiger wird auf seinen vorherigen Stand zurückgesetzt (nämlich der Anfang des Stapelrahmens aus der vorherigen Prozedur).
  3. der alte Wert des Programmzählers (die Rücksprungadresse) wird vom Stack genommen und dort weiter ausgeführt.
Ein Schema des Stapels nach einer Prozedur DrawSquare() eine Prozedur DrawLine() hat genannt.

Der Stapelzeiger ist normalerweise einer der usually registriert von a Prozessor. Bei der Intel x86Architektur ist dies die (E)SP-Registry. Operationen mit Registern nehmen sehr wenig Zeit in Anspruch. Einige Mikroprozessoren haben mehrere Stapelzeiger.

Der Stack wird verwendet, um lokales zu speichern store Variablen und Prozedurparameter. Ein zusammenhängender Block von Stack-Daten mit Rücksprungadresse, Aufrufparameter und lokale Variablen werden Rahmen genannt.

Hardware-Stack

Moderne Prozessoren sind immer mit einem Hardware-Stack ausgestattet, dh ein Teil des Speichers kann für den Stack reserviert werden und es gibt Anweisungen zum Betrieb des Stack. Der Hardware-Stack existiert bereits auf dem PDP11. Das traditionell weit verbreitete IBM 360 hat noch keinen Hardware-Stack.

Stapelorientierte Programmierung

Biene Stack-orientierte Programmierung ein Programm ist als Ganzes in einem Stack. Die Ausführung erfolgt wie folgt:

  • Holen Sie sich das oberste Element des Stapels, das eine Funktion (Operation) sein soll;
  • Bestimmen Sie die Anzahl der Argumente, die die Funktion erwartet, und entfernen Sie diese ebenfalls vom Stapel;
  • Führen Sie die Funktion für die (0 oder mehr) Argumente aus;
  • platziere das Funktionsergebnis, falls vorhanden, oben auf dem Stapel;
  • Wiederholen Sie diese Schritte, bis der Stack leer ist, ein Fehler auftritt oder eine spezielle Funktion ausgeführt wird, die befiehlt, die Ausführung zu stoppen.

Es ist üblich, solche Programme darzustellen, indem man den Stackinhalt von unten nach oben notiert, was bedeutet, dass alle Operationen in umgekehrte polnische Notation aufgelistet werden (Englisch: Umgekehrte polnische Notation, RPN).

Viele wissenschaftliche Taschenrechner verwenden diese Technik und Art des Notierens, ebenso Programmiersprachen wie her und PostScript.

Es gibt noch Mikroprozessoren mit einem stapelorientierten Befehlssatz erstellt, zum Beispiel dem ST20 von ST Microelectronics. Aufgrund ihrer Einfachheit können mehrere Kerne pro Chip realisiert werden und dies scheint die höhere Taktrate, die mit einer Registerarchitektur möglich ist, aufzuwiegen.