Stack (abstrakter Datentyp)

Für die Verwendung des Begriffs LIFO in Buchhaltung siehe LIFO (Buchhaltung). Für die Verwendung des Begriffs Pushdown im Krafttraining siehe Pushdown (Übung).
Für andere Verwendungen siehe Stack (Disambiguierung).
Ähnlich wie bei einem Stapel von Platten ist das Hinzufügen oder Entfernen nur oben möglich.
Einfache Darstellung einer Stack -Laufzeit mit drücken und Pop Operationen.

Im Informatik, a Stapel ist ein Zusammenfassung Datentyp das dient als a Sammlung von Elementen mit zwei Hauptleitungsvorgängen:

  • Drücken, was der Sammlung ein Element hinzufügt und
  • Pop, was das zuletzt hinzugefügte Element entfernt, das noch nicht entfernt wurde.

Die Reihenfolge, in der Elemente aus einem Stapel stammen, führt zu seinem alternativen Namen. LIFO (zuletzt rein, zuerst raus). Zusätzlich a spähen Der Betrieb kann Zugang zum Oberteil ermöglichen, ohne den Stapel zu ändern.[1] Der Name "Stapel" für diese Art von Struktur kommt von der Analogie zu einer Reihe von physischen Elementen, die übereinander gestapelt sind. Diese Struktur erleichtert es einfach, einen Gegenstand von der Oberseite des Stapels zu nehmen, während es möglicherweise zuerst mehrere andere Gegenstände ausziehen muss.[2]

Als a betrachtet Lineare Datenstrukturoder mehr abstrakt als sequentielle Sammlung, die Push- und Pop -Operationen treten nur an einem Ende der Struktur auf, die als die bezeichnet werden oben des Stapels. Diese Datenstruktur ermöglicht es, einen Stack als implementieren einzig verknüpfte Liste und ein Zeiger auf das obere Element. Ein Stapel kann implementiert werden, um eine begrenzte Kapazität zu haben. Wenn der Stapel voll ist und nicht genügend Platz enthält, um eine Entität zum Schieben zu akzeptieren, wird der Stapel dann als in einem angesehen Überlauf Zustand. Der Pop -Betrieb entfernt einen Artikel von der Oberseite des Stapels.

Für die Implementierung ist ein Stapel erforderlich Tiefe-First-Suche.

Geschichte

Siehe auch: Jan łukasiewicz § Arbeit

Stapel betraten 1946 in die Informatik -Literatur, wann Alan M. Turing verwendete die Begriffe "Bury" und "Ungebur" als Mittel zur Berufung und Rückkehr von Unterroutinen.[3][4] Unterroutinen war bereits umgesetzt in Konrad Zuse's Z4 1945.

Klaus Samelson und Friedrich L. Bauer von Technische Universität München schlug die Idee eines Stapels im Jahr 1955 vor[5][6] und reichte 1957 ein Patent ein.[7][8][9][10] Im März 1988, zu welchem ​​Zeitpunkt Samelson verstorben war, erhielt Bauer die IEEE Computer Pioneer Award zur Erfindung des Stapelprinzips.[11][6] Ähnliche Konzepte wurden unabhängig voneinander entwickelt von Charles Leonard Hamblin In der ersten Hälfte von 1954[12] und von Wilhelm Kämerer[DE] 1958.[13][14]

Stapel werden häufig unter Verwendung der Analogie eines federbelasteten Stapels von Platten in einer Cafeteria beschrieben.[15][2][16] Auf dem Stapel befinden sich saubere Platten und drücken alle bereits dort nach unten. Wenn eine Platte aus dem Stapel entfernt wird, wird der darunter aufgetaucht, um die neue obere Platte zu werden.

Nicht wesentliche Operationen

In vielen Implementierungen hat ein Stack mehr Operationen als die wesentlichen "Push" und "Pop" -Operationen. Ein Beispiel für eine nicht wesentliche Operation ist "Top of Stack" oder "Peek", das das obere Element beobachtet, ohne es aus dem Stapel zu entfernen.[17] Dies könnte mit einem "POP" erfolgen, gefolgt von einem "Druck", um dieselben Daten an den Stapel zurückzugeben, daher wird es nicht als wesentliche Operation angesehen. Wenn der Stapel leer ist, tritt bei der Ausführung der "Stack Top" oder "Pop" -Operationen eine Unterlaufbedingung auf. Darüber hinaus bieten viele Implementierungen eine Überprüfung, ob der Stapel leer ist und eine, die seine Größe zurückgibt.

Software -Stapel

Implementierung

Ein Stapel kann leicht über eine implementiert werden Array oder ein verlinkte Liste, wie Stapel nur besondere Fälle von Listen sind.[18] Was die Datenstruktur als Stapel identifiziert, ist in beiden Fällen nicht die Implementierung, sondern die Schnittstelle: Der Benutzer darf nur Elemente auf das Array oder die verknüpfte Liste mit wenigen anderen Helfervorgängen popieren oder schieben. Das Folgende zeigt beide Implementierungen, die mithilfe der Verwendung Pseudocode.

Array

Ein Array kann verwendet werden, um einen (begrenzten) Stapel wie folgt zu implementieren. Das erste Element, normalerweise am Null -Offset, ist der Boden, der dazu führt Array [0] Das erste Element war auf den Stapel und das letzte Element tauchte ab. Das Programm muss die Größe (Länge) des Stapels unter Verwendung einer Variablen verfolgen oben Dadurch wird die Anzahl der bisher gedrängten Elemente aufgezeichnet, wodurch auf die Stelle im Array hinweist, an der das nächste Element eingefügt werden soll (unter der Annahme einer Null-basierten Indexkonvention). Somit kann der Stapel selbst effektiv als Dreielementstruktur implementiert werden:

Struktur Stack: Maxsize: Ganzzahl Top: Ganzzahl Elemente: Array of Item
Verfahren initialisieren (STK: Stack, Größe: Ganzzahl): STK.Items ← Neu -Array von Größe Elemente, zunächst leer stk.maxSize ← Größe stk.top ← 0

Das drücken Der Betrieb fügt ein Element hinzu und erhöht die oben Index nach Überprüfung auf Überlauf:

Verfahren Push (STK: Stack, X: Element): wenn STK.TOP = STK.MAXSIZE: Überlauffehler Bericht anders: stk.items [stk.top] ← x stk.top ← stk.top + 1

Ähnlich, Pop verringert die oben Index nach dem Überprüfungen nach Unterlauf und gibt das zuvor die oberste Element zurück:

Verfahren Pop (STK: Stack): wenn stk.top = 0: Unterlauffehler melden anders: stk.top ← stk.top - 1 r ← stk.items [stk.top] Rückkehr r

Verwendung einer Dynamisches ArrayEs ist möglich, einen Stapel zu implementieren, der so weit wie erforderlich wachsen oder schrumpfen kann. Die Größe des Stapels hat einfach die Größe des dynamischen Arrays, was eine sehr effiziente Implementierung eines Stapels ist, da das Hinzufügen von Elementen zu Elementen vom Ende eines dynamischen Arrays addiert oder abgeleitet wird.

Verlinkte Liste

Eine weitere Option zur Implementierung von Stapeln ist die Verwendung a einzig verknüpfte Liste. Ein Stapel ist dann ein Zeiger auf den "Kopf" der Liste, mit vielleicht einem Zähler, um die Größe der Liste zu verfolgen:

Struktur Rahmen: Daten: Element Weiter: Frame oder NIL
Struktur Stack: Kopf: Rahmen oder Nullgröße: Ganzzahl
Verfahren initialisieren (STK: Stack): Stk.head ← nil stk.size ← 0

Das Schieben und Knallen von Gegenständen erfolgt am Kopf der Liste; Überlauf ist in dieser Implementierung nicht möglich (es sei denn, der Speicher ist erschöpft):

Verfahren Push (STK: Stack, X: Element): Newhead ← New Frame Newhead.Data ← x newhead.next ← Stk.head stk.head ← Newhead stk.size ← Stk.size + 1
Verfahren Pop (STK: Stack): wenn stk.head = nil: Unterlauffehler melden r ← stk.head.data stk.head ← stk.head.next stk.size ← stk.size - 1 Rückkehr r

Stapel und Programmiersprachen

Einige Sprachen, wie z. Perl, LISPELN, JavaScript und PythonLassen Sie die Stack -Operationen auf ihren Standardlisten-/Array -Typen vorhanden und Pop verfügbar. Einige Sprachen, insbesondere die in der Weiter Familie (einschließlich PostScript), sind auf sprachdefinierte Stapel ausgelegt, die vom Programmierer direkt sichtbar und manipuliert werden.

Das Folgende ist ein Beispiel für die Manipulation eines Stapels in Common Lisp ("">"Ist die Eingabeaufforderung des LISP -Interpreters; Linien beginnen nicht mit">"Sind die Antworten des Dolmetschers auf Ausdrücke):

> (setf Stapel (aufführen 'a 'b 'c))  ;; Stellen Sie die Variable "Stack" ein (A B C) > (Pop Stapel)  ;; Holen Sie sich das obere Element (links am weitesten), sollte den Stapel ändern A > Stapel  ;; Überprüfen Sie den Wert von Stack (B C) > (drücken 'Neu Stapel)  ;; Schieben Sie ein neues Oberteil auf den Stapel (NEU B C)

Einige der C ++ Standardbibliothek Containertypen haben push_back und Pop zurück Operationen mit LIFO -Semantik; Zusätzlich die Stapel Die Vorlagenklasse passt vorhandene Container an eine eingeschränkte Bereitstellung an API mit nur Push/Pop -Operationen. PHP hat an Splast Klasse. Javas Bibliothek enthält a Stapel Klasse, die eine Spezialisierung von ist Vektor. Im Folgenden finden Sie ein Beispielprogramm in Java Sprache, mit dieser Klasse.

importieren java.util.stack; Klasse Stackdemo {  Öffentlichkeit statisch Leere hauptsächlich(Saite[]Args) {  Stapel<Saite> Stapel = Neu Stapel<Saite>();  Stapel.drücken("EIN");  // In den Stapel "a" einfügen  Stapel.drücken("B");  // "B" in den Stapel einfügen  Stapel.drücken("C");  // "C" in den Stapel einfügen  Stapel.drücken("D");  // "D" in den Stapel einfügen  System.aus.println(Stapel.spähen());  // druckt die Oberseite des Stapels ("D")  Stapel.Pop();  // das Oberteil entfernen ("D")  Stapel.Pop();  // das nächste Top entfernen ("C")  } }

Hardware -Stack

Hauptartikel: Stackbasierte Speicherzuweisung

Eine häufige Verwendung von Stapeln auf Architekturebene ist ein Mittel zum Zuweisen und Zugriff auf Speicher.

Grundlegende Architektur eines Stapels

Ein typischer Stapel ist ein Bereich des Computerspeichers mit festem Ursprung und einer variablen Größe. Anfangs ist die Größe des Stapels Null. EIN Stapelzeiger, Normalerweise weist in Form eines Hardware -Registers auf den zuletzt verwiesenen Standort auf dem Stapel hin. Wenn der Stapel eine Größe von Null hat, zeigt der Stapelzeiger auf den Ursprung des Stapels.

Die beiden Operationen, die für alle Stapel gilt, sind:

  • a drücken Betrieb, in dem ein Datenelement an dem vom Stapelzeiger gerichteten Ort platziert wird, und die Adresse im Stapelzeiger wird durch die Größe des Datenelements angepasst.
  • a Pop oder ziehen Betrieb: Ein Datenelement am aktuellen Ort, auf den der Stapelzeiger hingewiesen wird, wird entfernt, und der Stapelzeiger wird durch die Größe des Datenelements angepasst.

Es gibt viele Variationen des Grundprinzips der Stapeloperationen. Jeder Stack hat einen festen Standort im Speicher, an dem er beginnt. Da Datenelemente zum Stapel hinzugefügt werden, wird der Stapelzeiger verschoben, um das aktuelle Ausmaß des Stapels anzuzeigen, der sich vom Ursprung ausdehnt.

Stapelzeiger können auf den Ursprung eines Stapels oder auf einen begrenzten Bereich von Adressen über oder unter dem Ursprung hinweisen (abhängig von der Richtung, in der der Stapel wächst); Der Stapelzeiger kann jedoch nicht den Ursprung des Stapels überqueren. Mit anderen Worten, wenn der Ursprung des Stapels an der Adresse 1000 liegt und der Stapel nach unten wächst (in Richtung der Adressen 999, 998 usw.), darf der Stapelzeiger niemals über 1000 (bis 1001, 1002 usw.) erhöht werden. Wenn ein Pop -Operation auf dem Stapel dazu führt, dass der Stapelzeiger den Ursprung des Stapels überwindet, a Stapelunterlauf tritt ein. Wenn ein Push -Betrieb den Stapelzeiger dazu bringt, über das maximale Ausmaß des Stacks hinaus zu erhöhen oder abzunehmen, a Paketüberfluss tritt ein.

Einige Umgebungen, die stark auf Stapel angewiesen sind, können zusätzliche Vorgänge liefern, beispielsweise:

  • Duplikat: Das obere Element wird geknallt und dann erneut (zweimal) gedrückt, so dass eine zusätzliche Kopie des ehemaligen Top -Elements jetzt oben ist und das Original darunter ist.
  • Spähen: Das oberste Element wird inspiziert (oder zurückgegeben), aber der Stapelzeiger und die Stapelgröße ändert sich nicht (dh, das Element bleibt auf dem Stapel verbleibt). Dies wird auch genannt oben Betrieb in vielen Artikeln.
  • Tausch oder Austausch: Die beiden obersten Artikel an den Stapelaustauschplätzen.
  • Drehen (oder rollen): das n Die obersten Gegenstände werden auf rotierende Weise auf dem Stapel bewegt. Zum Beispiel wenn n = 3Die Punkte 1, 2 und 3 auf dem Stapel werden in die Positionen 2, 3 und 1 auf dem Stapel bewegt. Viele Varianten dieser Operation sind möglich, wobei die häufigsten genannt werden links drehen und Rechte drehen.

Stapel werden oft von unten nach oben (wie reale Stapel) Visualisiert. Sie können auch von links nach rechts wachsen, so dass "oberste" "ganz rechts" oder sogar von oben nach unten wächst. Das wichtige Merkmal ist, dass sich der Boden des Stapels in einer festen Position befindet. Die Abbildung in diesem Abschnitt ist ein Beispiel für eine Wachstumsvisualisierung von Top-bis-Boden-Wachstum: Der obere (28) ist der Stapel "Bottom", da der Stapel "Top" (9) die Elemente gedrückt oder geknallt werden.

A Rechte drehen verschiebt das erste Element auf die dritte Position, das zweite zum ersten und dritten zum zweiten. Hier sind zwei äquivalente Visualisierungen dieses Prozesses:

Apple Banana Banane === Richtig Dreh ==> Gurkengurke Apple Apple
Gurke Apple Banane === Links drehen ==> Gurken Apple Banane

Ein Stapel wird normalerweise in Computern durch einen Block aus Speicherzellen dargestellt, wobei der "Boden" an einem festen Ort und der Stapelzeiger die Adresse der aktuellen "oberen" Zelle im Stapel hält. Die obere und untere Terminologie wird unabhängig davon verwendet, ob der Stapel tatsächlich zu niedrigeren Speicheradressen oder zu höheren Speicheradressen wächst.

Das Drücken eines Elements zum Stapel passt den Stapelzeiger anhand der Größe des Elements an (entweder ab oder inkrementiert, abhängig von der Richtung, in der der Stapel im Speicher wächst), auf die nächste Zelle hinweisen, und kopiert den neuen oberen Element auf der Stapelbereich. Abhängig von der genauen Implementierung kann der Stapelzeiger am Ende eines Push -Betriebs auf den nächsten nicht verwendeten Standort im Stapel verweisen oder auf das oberste Element im Stapel hinweisen. Wenn der Stapel auf das aktuelle oberste Element zeigt, wird der Stapelzeiger aktualisiert, bevor ein neuer Artikel auf den Stapel gedrückt wird. Wenn es auf den nächsten verfügbaren Standort im Stapel zeigt, wird es aktualisiert nach Der neue Artikel wird auf den Stapel gedrückt.

Das Stapeln des Stapels ist einfach die Umkehrung des Drückens. Das oberste Element im Stapel wird entfernt und der Stapelzeiger in der entgegengesetzten Reihenfolge der im Push -Operation verwendeten Reihenfolge aktualisiert.

Stapel im Hauptspeicher

Viele CISC-Typ Zentralprozessor Entwürfe, einschließlich der x86, Z80 und 6502haben ein dediziertes Register für die Verwendung als die Rufen Sie Stack an Stapelzeiger mit dedizierten Anweisungen für Anrufe, Rückgabe, Pushen und POP, die das dedizierte Register implizit aktualisieren und so erhöhen und somit zunimmt Code Dichte. Einige CISC -Prozessoren, wie die PDP-11 und die 68000, hat auch Sonderadresungsmodi zur Implementierung von Stapelnnormalerweise auch mit einem halbdedizierten Stapelzeiger (wie A7 im 68000). Im Gegensatz dazu die meisten RISC CPU -Designs haben keine dedizierten Stack -Anweisungen, und daher können die meisten, wenn nicht alle Register bei Bedarf als Stack -Zeiger verwendet werden.

Stapel in Registern oder speziellen Speicher

Hauptartikel: Stapelmaschine

Einige Maschinen verwenden einen Stapel für arithmetische und logische Operationen. Operanden werden auf den Stapel gedrückt, und arithmetische und logische Operationen wirken auf den oberen oder mehreren Elementen auf dem Stapel, wobei sie vom Stapel gestapelt und das Ergebnis auf den Stapel geschoben werden. Maschinen, die auf diese Weise funktionieren, werden genannt Stapelmaschinen.

Eine Anzahl von Mainframes und Minicomputer waren Stack -Maschinen, das berühmteste war das Burroughs große Systeme. Andere Beispiele sind die CISC HP 3000 Maschinen und die CISC -Maschinen von Tandem -Computer.

Das x87 schwimmender Punkt Architektur ist ein Beispiel für eine Reihe von Registern, die als Stapel organisiert sind, bei dem auch direkter Zugang zu einzelnen Registern (im Vergleich zur aktuellen Oberseite) möglich ist.

Das Top-of-Stapel als implizites Argument ermöglicht eine kleine Maschinensprache Fußabdruck mit einer guten Verwendung von Bus Bandbreite und Code Caches, aber es verhindert auch einige Arten von Optimierungen, die für die zulässigen Prozessoren möglich sind Zufallszugriff zum Datei registrieren Für alle (zwei oder drei) Operanden. Eine Stapelstruktur macht auch Superscalar Implementierungen mit Umbenennen registrieren (zum Spekulative Ausführung) etwas komplexer zu implementieren, obwohl es immer noch machbar ist, wie von modern veranschaulicht x87 Implementierungen.

Sonne Sparc, AMD AM29000, und Intel i960 sind alle Beispiele für Architekturen mit Registrieren Sie Windows Innerhalb eines Registerstapels als eine andere Strategie, um die Verwendung des langsamen Hauptspeichers für Funktionsargumente und Rückgabeteile zu vermeiden.

Es gibt auch eine Reihe kleiner Mikroprozessoren, die einen Stapel direkt in Hardware und einige implementieren Mikrocontroller Haben Sie einen Stapel mit fester Tiefe, der nicht direkt zugänglich ist. Beispiele sind die PIC -Mikrocontroller, der Computer Cowboys MUP21, der Harris RTX Zeile und Novix NC4016. Viele Stack-basierte Mikroprozessoren wurden verwendet, um die Programmiersprache zu implementieren Weiter Bei der Mikrocode eben.

Anwendungen von Stapeln

Expressionsbewertung und Syntax -Parsen

Taschenrechner einsetzen Polnische Notation umgekehrt Verwenden Sie eine Stapelstruktur, um Werte zu halten. Ausdrücke können in Präfix-, Postfix- oder Infix -Notationen dargestellt werden, und die Konvertierung von einer Form zu einem anderen kann mit einem Stapel erreicht werden. Viele Compiler verwenden einen Stapel, um die Syntax von Ausdrücken, Programmblöcken usw. zu analysieren, bevor sie in Code mit niedrigem Niveau übersetzen. Die meisten Programmiersprachen sind Kontextfreie Sprachenund erlauben, dass sie mit Stack-basierten Maschinen analysiert werden.

Backtracking

Hauptartikel: Backtracking

Eine weitere wichtige Anwendung von Stapeln ist Backtracking. Betrachten Sie ein einfaches Beispiel, um den richtigen Weg in einem Labyrinth zu finden. Es gibt eine Reihe von Punkten vom Ausgangspunkt bis zum Ziel. Wir beginnen von einem Punkt. Um das endgültige Ziel zu erreichen, gibt es mehrere Wege. Angenommen, wir wählen einen zufälligen Pfad. Nachdem wir einem bestimmten Weg gefolgt sind, erkennen wir, dass der von uns gewählte Weg falsch ist. Wir müssen also einen Weg finden, wie wir zum Beginn dieses Weges zurückkehren können. Dies kann mit Stapeln erfolgen. Mit Hilfe von Stapeln erinnern wir uns an den Punkt, an dem wir erreicht haben. Dies geschieht, indem dieser Punkt in den Stapel geschoben wird. Falls wir auf dem falschen Weg enden, können wir den letzten Punkt aus dem Stapel herausholen und somit zum letzten Punkt zurückkehren und unsere Suche nach dem richtigen Weg fortsetzen. Dies wird Backtracking genannt.

Das prototypische Beispiel eines Backtracking -Algorithmus ist Tiefe-First-Suche, der alle Scheitelpunkte eines Diagramms findet, die aus einem angegebenen Startscheitel erreicht werden können. Andere Anwendungen der Rückverfolgung beinhalten die Suche durch Räume, die potenzielle Lösungen für ein Optimierungsproblem darstellen. Zweig und gebunden ist eine Technik zur Durchführung solcher Backtracking -Suchanfragen, ohne alle potenziellen Lösungen in einem solchen Raum ausführlich zu durchsuchen.

Kompilierungszeitspeicherverwaltung

Hauptartikel: Stackbasierte Speicherzuweisung und Stapelmaschine
Ein typischer Anrufstack, der lokale Daten und Anrufinformationen für mehrere Ebenen von Verfahrensaufrufen speichert. Dieser Stapel wächst von seinem Ursprung nach unten. Der Stapelzeiger zeigt auf die aktuelle oberste Datum auf dem Stapel. Ein Push -Betrieb verringert den Zeiger und kopiert die Daten in den Stapel. Ein Pop -Betrieb kopiert Daten aus dem Stapel und erhöht dann den Zeiger. Jedes im Programm aufgerufene Verfahren speichert die Verfahren zur Rückgabe von Informationen (in Gelb) und lokalen Daten (in anderen Farben), indem sie sie auf den Stapel drücken. Diese Art der Stapelimplementierung ist äußerst häufig, ist jedoch anfällig für Pufferüberlauf Angriffe (siehe Text).

Eine Anzahl von Programmiersprachen sind stapelorientiertDies bedeutet, dass sie die meisten grundlegenden Operationen definieren (hinzuzufügen, zwei Zahlen hinzufügen, einen Charakter drucken), um ihre Argumente aus dem Stapel zu entnehmen und alle Rückgabeteile wieder auf den Stapel zu platzieren. Zum Beispiel, PostScript Hat einen Rückkehrstack und einen Operand -Stack und hat auch einen Grafikstaatsstapel und einen Wörterbuchstapel. Viele virtuelle Maschinen sind auch stapelorientiert, einschließlich der P-Code-Maschine und die Java virtuelle Maschine.

Fast alles Konventionen anrufen‍ - ‌Die Wege, in denen Unterroutinen Erhalten Sie ihre Parameter und geben Sie Ergebnisse zurück.Rufen Sie Stack an") Um Informationen über das Aufrufen und Verschachteln von Verfahren/Funktionen zu halten, um zum Kontext der aufgerufenen Funktion zu wechseln und bei der Aufrufs zu der Anruferfunktion wiederherzustellen. auf dem Stapel. Stapel sind eine wichtige Möglichkeit, verschachtelt zu werden oder rekursiv Funktionsaufrufe. Diese Art von Stapel wird implizit vom Compiler verwendet, um Anrufe und Rückgabeanweisungen (oder deren Äquivalente) zu unterstützen und vom Programmierer nicht direkt manipuliert zu werden.

Einige Programmiersprachen verwenden den Stapel, um Daten zu speichern, die lokal für eine Prozedur sind. Der Platz für lokale Datenelemente wird aus dem Stapel beim Eingeben des Verfahrens zugewiesen und wird beim Ablauf des Verfahrens ausgeführt. Das C Programmiersprache wird normalerweise auf diese Weise implementiert. Die Verwendung des gleichen Stacks für Daten und Verfahrensanrufe hat wichtige Sicherheitsauswirkungen (siehe unten) von denen ein Programmierer bekannt sein muss, um zu vermeiden, dass ernsthafte Sicherheitsfehler in ein Programm eingeführt werden.

Effiziente Algorithmen

Mehrere Algorithmen Verwenden Sie einen Stapel (getrennt vom üblichen Funktionsaufrufstapel der meisten Programmiersprachen) als Schulleiter Datenstruktur mit denen sie ihre Informationen organisieren. Diese beinhalten:

  • Graham -Scanein Algorithmus für die konvexer Rumpf eines zweidimensionalen Systems von Punkten. Ein konvexer Rumpf einer Untergruppe des Eingangs wird in einem Stapel gehalten, der verwendet wird, um Konkavitäten in der Grenze zu finden und zu entfernen, wenn dem Rumpf ein neuer Punkt hinzugefügt wird.[19]
  • Teil von Smawk -Algorithmus Für das Finden der Zeilenminima einer monotonischen Matrix verwendet Stapel in ähnlicher Weise wie Graham Scan.[20]
  • Alle nächsten kleineren Werte, Das Problem des Findens für jede Zahl in einem Array, der engsten vorhergehenden Zahl, die kleiner ist als sie. Ein Algorithmus für dieses Problem verwendet einen Stapel, um eine Sammlung von Kandidaten für den nächsten kleineren Wert zu erhalten. Für jede Position im Array wird der Stapel geknallt, bis ein kleinerer Wert auf seiner Oberseite gefunden wird und der Wert in der neuen Position auf den Stapel gedrückt wird.[21]
  • Das Kettenalgorithmus der nächsten Nachbarneine Methode für Agglomerative hierarchische Clusterbildung Basierend auf der Aufrechterhaltung eines Stapels Cluster, von denen jeder der nächste Nachbar seines Vorgängers auf dem Stapel ist. Wenn diese Methode ein Paar Cluster findet, die gegenseitige Nachbarn sind, werden sie geknallt und verschmolzen.[22]

Sicherheit

Einige Computerumgebungen verwenden Stapel auf eine Weise, die sie möglicherweise anfällig machen kann Sicherheitsverstoss und Angriffe. Programmierer, die in solchen Umgebungen arbeiten, müssen besondere Vorsicht machen, um die Fallstricke dieser Implementierungen zu vermeiden.

Beispielsweise verwenden einige Programmiersprachen einen gemeinsamen Stapel, um sowohl Daten lokal in einem genannten Prozedur als auch die Verknüpfungsinformationen zu speichern, mit denen das Prozedur an seinen Anrufer zurückkehrt. Dies bedeutet, dass das Programm Daten in denselben Stapel und aus demselben Stapel verschiebt, der kritische Rückgabedressen für die Prozeduranrufe enthält. Wenn Daten an den falschen Standort im Stapel verschoben werden oder ein übergroßes Datenelement an einen Stapelort verschoben wird, der nicht groß genug ist, um sie enthalten, können Informationen für Verfahrensanrufe beschädigt werden, wodurch das Programm fehlschlägt.

Böswillige Parteien können versuchen Stapel zerschlagen Angriff, der diese Art der Implementierung nutzt, indem ein Programm übergroße Dateneingaben für ein Programm bereitgestellt wird, das die Eingabedauer nicht überprüft. Ein solches Programm kann die Daten vollständig an einen Ort auf dem Stapel kopieren und damit die Rückgabedressen für die genannten Verfahren ändern. Ein Angreifer kann experimentieren, um eine bestimmte Art von Daten zu finden, die einem solchen Programm so bereitgestellt werden können, dass die Rückgabeadresse des aktuellen Prozedur zurückgesetzt wird, um auf einen Bereich innerhalb des Stapels selbst (und innerhalb der vom Angreifer bereitgestellten Daten) zu verweisen. was wiederum Anweisungen enthält, die nicht autorisierte Operationen ausführen.

Diese Art von Angriff ist eine Variation der Pufferüberlauf Angriff und eine äußerst häufige Quelle für Sicherheitsverletzungen in der Software, vor allem, weil einige der beliebtesten Compiler einen gemeinsam genutzten Stack für Daten- und Verfahrensanrufe verwenden und nicht die Dauer der Datenelemente überprüfen. Häufig schreiben Programmierer keinen Code, um die Größe der Datenelemente zu überprüfen, und wenn ein übergroßes oder untergroßes Datenelement in den Stapel kopiert wird, kann ein Sicherheitsverstoß auftreten.

Siehe auch

Verweise

  1. ^ Im Gegensatz dazu arbeitet eine einfache Warteschlange FIFO (als Erster rein, als erster raus).
  2. ^ a b Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Einführung in Algorithmen (3. Aufl.). MIT Press und McGraw-Hill. S. 232–233. ISBN 0-262-03384-4.
  3. ^ Turing, Alan Mathison (1946-03-19) [1945], Entwicklungsvorschläge in der Mathematikabteilung einer automatischen Computermotor (ACE) (NB. Vor dem Exekutivkomitee des National Physical Laboratory (Großbritannien) vorgestellt.)
  4. ^ Zimmermann, Brian Edward; Doran, Robert William (1977-01-01) [Oktober 1975]. "Die andere Turing -Maschine". Das Computerjournal. 20 (3): 269–279. doi:10.1093/comjnl/20.3.269. (11 Seiten)
  5. ^ Samelson, Klaus (1957) [1955]. Geschrieben bei Internationales Kolloquium über Probleme der Revhentechnik, Dresden, Deutschland. Problem der Programmierungstechnik (auf Deutsch). Berlin, Deutschland: Veb Deutscher Verlag der Wissenschaften. S. 61–68. (Nb. Dieses Papier wurde erstmals 1955 vorgestellt. Es beschreibt einen Zahlenstapel (Zahlenkeller), aber nennt es linearer Hilfsspeicher (linearer Hilfsspeicher).).)
  6. ^ a b Fothe, Michael; Wilke, Thomas, Hrsg. (2015). Keller, Stack und Automatische Gedächtnis - Ein Struktur mit Potensial (PDF) (Tagungsband Zumolloquium 14. November 2014 in Jena). GI -Serie: Vorlesungsnotizen in Informatik (LNI) - Thematik (auf Deutsch). Vol. T-7. Bonn, Deutschland: Gesellschaft für Informatik (GI) / Kölllen Druck + Verlag GmbH. ISBN 978-3-88579-426-4. Archiviert (PDF) vom Original am 2020-04-12. Abgerufen 2020-04-12. (77 Seiten)
  7. ^ Bauer, Friedrich Ludwig; Samelson, Klaus (1957-03-30). "VERFAREN ZUR AUTOMATISCHEN VERARBEITUNG von Kodierten daten und revhenmaschine Zurübung des Veravahrens" (auf Deutsch). München, Deutschland: Deutsche Patentamt. DE-PS 1094019. Abgerufen 2010-10-01.
  8. ^ Bauer, Friedrich Ludwig; Goos, Gerhard (1982). Informatik - Einen (auf Deutsch). Vol. Teil 1 (3 ed.). Berlin: Springer-Verlag. p. 222. ISBN 3-540-11722-9. Die Bezeichung 'Keller' Hierfür Wurde von Bauer und Samelson in Einer Deutschen Patentanmeldung von 30. Märrz 1957 EINGEFÜHRT.
  9. ^ Samelson, Klaus; Bauer, Friedrich Ludwig (1959). "Sequentielle Formelüberetzung" [Sequent -Formel -Translation]. Elektronische Readenanlagen (auf Deutsch). 1 (4): 176–182.
  10. ^ Samelson, Klaus; Bauer, Friedrich Ludwig (1960). "Sequentielle Formelübersetzung". Kommunikation der ACM. 3 (2): 76–83. doi:10.1145/366959.366968. S2CID 16646147.
  11. ^ "IEEE-Computer-Pioneer-Preis-Bauer, Friedrich L." Technische Universität München, Fakultät für Informatik. 1989-01-01. Archiviert von das Original Am 2017-11-07.
  12. ^ Hamblin, Charles Leonard (Mai 1957). Ein adressloses Codierungsschema, das auf mathematischer Notation basiert (PDF) (Typoskript). N.S.W. Universität für Technologie. S. 121-1–121-12. Archiviert (PDF) vom Original am 2020-04-12. Abgerufen 2020-04-12. (12 Seiten)
  13. ^ Kämerer, Wilhelm (1958). Zifferg-Rillenautomat mit Programmierung Nachmathematischem Formelbild (Habilitationsarbeit) (auf Deutsch). Friedrich-Schiller-universität, Jena, Deutschland.
  14. ^ Kämerer, Wilhelm (1960). Ziffergruschenautomaten. Elektronische Recuren und Regeln (auf Deutsch). Vol. 1. Berlin, Deutschland: Akademie-Verlag.
  15. ^ Ball, John A. (1978). Algorithmen für RPN -Taschenrechner (1 ed.). Cambridge, Massachusetts, USA: Wiley-Interscience, John Wiley & Sons, Inc. ISBN 978-0-471-03070-6.
  16. ^ Godse, Atul P.; Godse, Deepali A. (2010-01-01). Rechnerarchitektur. Technische Veröffentlichungen. S. 1–56. ISBN 978-8-18431534-9. Abgerufen 2015-01-30.
  17. ^ Horowitz, Ellis: "Grundlagen der Datenstrukturen in Pascal", Seite 67. Informatik Press, 1984
  18. ^ Pandey, Shreesham (2020-06-07). "Datenstrukturen auf den Punkt gebracht". Rochester, NY. {{}}: Journal zitieren erfordert |journal= (Hilfe)
  19. ^ Graham, R. L. (1972). Ein effizienter Algorithmus zur Bestimmung des konvexen Rumpfes eines endlichen planaren Satzes. Informationsverarbeitungsbuchstaben 1, 132-133
  20. ^ Aggarwal, Alok; Klawe, Maria M.; Moran, Shlomo; Küste, Peter; Wilber, Robert (1987), "Geometrische Anwendungen eines Matrixsuchalgorithmus", Algorithmus, 2 (1–4): 195–208, doi:10.1007/bf01840359, HERR 0895444, S2CID 7932878.
  21. ^ Berkman, Omer; Schieber, Baruch; Vishkin, Uzi (1993), "optimale doppelt logarithmische parallele Algorithmen basierend auf der Suche nach allen nächsten kleineren Werten", Journal of Algorithmen, 14 (3): 344–370, Citeseerx 10.1.1.55.5669, doi:10.1006/jagm.1993.1018.
  22. ^ Murtagh, Fionn (1983), "Eine Übersicht über die jüngsten Fortschritte in hierarchischen Clustering -Algorithmen" (PDF), Das Computerjournal, 26 (4): 354–359, doi:10.1093/comjnl/26.4.354.

Weitere Lektüre

Externe Links