Studium, Ausbildung und Beruf

web uni-protokolle.de
 powered by
NachrichtenLexikonProtokolleBücherForenSonntag, 20. Oktober 2019 

Stack


Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.

Inhaltsverzeichnis

Einleitung

Ein Stack manchmal auch Stapel Stapelspeicher oder Kellerspeicher genannt ist eine häufig (aber meist benutzte Datenstruktur in Computerprogrammen . Sie wird von den meisten Mikroprozessoren in der Hardware direkt unterstützt.

Funktionsprinzip

Ein Stack kann eine beliebige Menge Elementen aufnehmen. Es gibt im Wesentlichen zwei meist mit push und pop bezeichnet. Push legt ein Element auf den Stack pop holt ein Element vom Stack (und dieses).

Dabei wird nach dem LIFO-Prinzip ( l ast i n f irst o ut) gearbeitet d.h. es wird immer das zurückgegben welches als letztes auf dem Stack push abgelegt wurde.

Die Theoretische Informatik unterscheidet hierbei zwischen echten Stack bei dem kein Element außer Obersten gelesen werden kann und einem Stapel dem ohne Veränderung der Daten jedes Element werden kann (vergleichbar einem Lesezugriff auf einen Array ).

Diese Unterscheidung spielt jedoch in der keine Rolle beinahe jede Implementation ist ein Stapel daher werden die i. A. synonym verwendet.

Illustration

Man kann sich einen Stack wie Stapel von Umzugskisten vorstellen. Man kann immer neue Kiste oben auf den Stapel packen push ) oder eine Kiste von oben herunternehmen pop ).

Anwendungen

Funktionale Programmiersprachen

Stacks werden in funktionalen Programmiersprachen meist nur implizit benutzt ohne dass der Programmierer Gedanken darum machen muss beispielsweise rekursiven Funktionen . Will man eine rekursive Funktion in iterative umwandeln so muss man oft doch einen Stack programmieren.

Mikroprozessoren

In Mikroprozessoren gibt es dazu oft spezielles Register den Stackpointer. Dieses Register enthält eine die auf den gerade obersten Stackeintrag zeigt. mit der Operation push ein weiterer Wert auf dem Stack wird dann erhöht oder vermindert sich der des Stackpointers (je nach Prozesor) und zeigt auf die nächste Adresse in die der Stackeintrag geschrieben wird. Bei pop wird der Eintrag der Adresse gelesen anschließend der Stackpointer vermindert oder erhöht (wieder nach Prozessor aber diesmal genau umgekehrt) und so wieder auf den letzten Stackeintrag. Der des Mikroprozessors wird oft von diesem selbst Aufruf und Rücksprung von Subroutinen zur Speicherung Rücksprungadresse genutzt ohne dass ein zusätzliches push oder pop zum Ablegen oder Holen dieser Rücksprungadresse ist. Compiler für moderne funktionale Programmiersprachen erweitern diesen oft indem sie mit zusätzlichen push - und pop -Operationen vor dem Aufruf bzw. Rücksprung von Subroutine Parameter an diese übergeben oder Funktionswerte dieser zurückgeben.

Compiler

Zur Übersetzung des Quellcodes einer Formalen Sprache nutzen Compiler und Interpreter einen Parser der bei der Textanalyse Syntax -Regeln auf einem Stack ablegt und so dem nachfolgenden Textelement eine angenommene Bedeutung (das Stapelelement) zuordnen kann. Programmiersprachen die auf eine virtuelle Maschine aufsetzen (z. B. Java P-Code-Pascal) optimieren den kompilierten Zwischencode für die Verwendung eines um zur Laufzeit die Interpretation dieses Zwischencodes zu beschleunigen.

Siehe auch: Kellerautomat

Umgekehrte Polnische Notation

Zur Berechnung von Termen wird gelegentlich die Umgekehrte Polnische Notation (UPN) verwendet die mit Hilfe der eine Klammersetzung und Punkt-vor-Strich-Regeln überflüssig macht. Die werden auch hier nicht explizit angegeben sondern sich aus den Rechenvorschriften der UPN. Zahlwerte automatisch auf dem Stapel abgelegt Operatoren (+ * /) holen die oberen beiden Werte unitären Operatoren z.B. Vorzeichenwechel natürlich nur einen) Stack und legen anschließend das (Zwischen-)Ergebnis dort ab. Da hier der Operator als letztes wird (die Werte müssen zur Durchführung der bereits auf dem Stack vorliegen) spricht man von einer Postfix-Notation.

Infix-Notation

Bei der maschinengestützten Auflösung von arithmetischen in der so genannten Infix-Notation (der Operator zwischen den beteiligten Zahlwerten) werden zunächst vorrangige in einem Stack zwischengelagert und so faktisch Infix-Term schrittweise in einen UPN-Term umgewandelt bevor Ergebnis durch Abarbeiten des Stack errechnet wird. Umformung erfolgt auch hier wieder durch einen

Stapelorientierte Sprachen

Stapelorientierte Sprachen (z.B. Forth oder Postscript ) wickeln fast alle Variablen -Operationen über eine Stapel-Struktur ab und stellen den oben genannten Operatoren noch weitere zur Beispielsweise tauscht der Forth-Operator swap die obersten beiden Elemente des Stack. Operationen werden in der UPN notiert und damit ebenfalls den Stack.

Forth benutzt einen zweiten Stack (Return-Stapel) Zwischenspeicherung der Rücksprungadressen von Routinen während der Dieser Stapel wird auch während der Übersetzungsphase die Adressen der Sprungziele für die Kontrollstrukturen Die Übergabe und Rückgabe von Werten an geschieht über den ersten Stapel der zweite die Rücksprungadresse auf.

Programmiersprachen mit rekursiv aufrufbaren Unterprogrammen

Viele Programmiersprachen wie C Java (Programmiersprache) erlauben rekursive Unterprogramme . Hier wird ein Stack zur Zwischenspeicherung Rücksprungadressen lokalen Variablen und Funktionsergebnisse verwendet. Dieser wird in den meisten dieser Sprachen stets auch für nicht rekursive Unterprogramme.



Bücher zum Thema Stack

Dieser Artikel von Wikipedia unterliegt der GNU FDL.

ImpressumLesezeichen setzenSeite versendenSeite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/Stack.html">Stack </a>