In der Informatik ist ein Stapel ein letzter in, zuerst (LIFO) Auszug-Datentyp und geradlinige Datenstruktur. Ein Stapel kann jeden abstrakten Datentyp als ein Element haben, aber wird durch zwei grundsätzliche Operationen, genannt Stoß und Knall charakterisiert. Die Stoß-Operation fügt einen neuen Artikel zur Spitze des Stapels hinzu, oder initialisiert den Stapel, wenn es leer ist. Wenn der Stapel voll ist und genug Raum nicht enthält, um den gegebenen Artikel zu akzeptieren, wie man dann betrachtet, ist der Stapel in einem Überschwemmungsstaat. Die Knall-Operation entfernt einen Artikel von der Spitze des Stapels. Ein Knall entweder offenbart vorher verborgene Sachen, oder läuft auf einen leeren Stapel hinaus, aber wenn der Stapel dann leer ist, tritt es in Unterlauf-Staat ein (Es bedeutet, dass keine Sachen im Stapel da sind, der zu entfernen ist).

Ein Stapel ist eine eingeschränkte Datenstruktur, weil nur eine kleine Zahl von Operationen darauf durchgeführt wird. Die Natur des Knalls und der Stoß-Operationen bedeutet auch, dass Stapel-Elemente eine natürliche Ordnung haben. Elemente werden vom Stapel in der Rückordnung zur Ordnung ihrer Hinzufügung entfernt: Deshalb sind die niedrigeren Elemente diejenigen, die auf dem Stapel das längste gewesen sind.

Geschichte

Der Stapel wurde zuerst 1946, im Computerdesign von Alan M. Turing vorgeschlagen (wer die Begriffe "begräbst" gebraucht hat und "begraben Sie un") als ein Mittel des Benennens und Zurückbringens von Unterprogrammen. 1957 haben die Deutschen Klaus Samelson und Friedrich L. Bauer die Idee patentiert. Dasselbe Konzept wurde unabhängig vom Australier Charles Leonard Hamblin in der ersten Hälfte von 1957 entwickelt.

Abstrakte Definition

Ein Stapel ist eine Kerninformatik-Datenstruktur und kann auf eine abstrakte, Weise ohne Durchführungen, definiert werden

oder es kann allgemein als, definiert werden

Stapel ist eine geradlinige Liste von Sachen, in denen alle Hinzufügungen und Auswischen auf ein Ende eingeschränkt werden, das Spitze ist.

Das ist ein VDM (Wiener Entwicklungsmethode) Beschreibung eines Stapels:

Funktionsunterschriften:

init:-> Stapel

Stoß: N x Stack-> Stapel

Spitze: Stapel-> (N U FEHLER)

ziehen Sie um: Stapel-> Stapel

isempty: Stapel-> Boolean

(wo N ein Element (natürliche Zahlen in diesem Fall) anzeigt, und U Satz-Vereinigung anzeigt)

Semantik:

Spitze (init ) = FEHLER

Spitze (Stoß (ich, s)) = ich

ziehen Sie (init ) = init um

ziehen Sie (Stoß (ich, s)) = s um

isempty (init ) = wahrer

isempty (Stoß (ich, s)) = falscher

Unwesentliche Operationen

In vielen Durchführungen hat ein Stapel mehr Operationen als "Stoß" und "Knall". Ein Beispiel ist "Spitze des Stapels" oder "Piepsen", der Revers das höchste Element, ohne es vom Stapel zu entfernen. Da das mit einem "Knall" und einem "Stoß" mit denselben Daten getan werden kann, ist es nicht notwendig. Eine Unterlauf-Bedingung kann in der "Stapel" Spitzenoperation vorkommen, wenn der Stapel, dasselbe als "Knall" leer ist. Häufig haben Durchführungen eine Funktion, die gerade zurückkehrt, ob der Stapel leer ist.

Softwarestapel

Durchführung

Auf den meisten hohen Sprachen kann ein Stapel entweder durch eine Reihe oder durch eine verbundene Liste leicht durchgeführt werden. Was die Datenstruktur identifiziert, weil ein Stapel in jedem Fall nicht die Durchführung, aber die Schnittstelle ist: Dem Benutzer wird nur erlaubt, Sachen auf die Reihe oder verbundene Liste mit wenigen anderen Helfer-Operationen knallen zu lassen oder zu stoßen. Der folgende wird beide Durchführungen, mit C demonstrieren.

Reihe

Die Reihe-Durchführung hat zum Ziel, eine Reihe zu schaffen, wo das erste Element (gewöhnlich am Nullausgleich) der Boden ist. D. h. ist das erste auf den Stapel gestoßene Element, und das letzte Element ist plötzlich verschwunden. Das Programm muss die Größe oder die Länge des Stapels nachgehen. Der Stapel selbst kann deshalb als eine Zwei-Elemente-Struktur in C effektiv durchgeführt werden:

typedef struct {\

Size_t-Größe;

int Sachen [STACKSIZE];

} STAPEL;

</Quelle>

Die Operation wird verwendet, sowohl um den Stapel zu initialisieren, als auch Werte dazu zu versorgen. Es ist dafür verantwortlich (das Kopieren) des Werts in die Reihe einzufügen und für den Element-Schalter zu erhöhen. In einer verantwortlichen C Durchführung ist es auch notwendig zu überprüfen, ob die Reihe bereits voll ist, um einen überfluteten zu verhindern.

leerer Stoß (SCHOBERN *ps, interne Nummer x AUF)

{\

wenn (ps-> Größe == STACKSIZE) {\

fputs ("Fehler: Schobern Sie overflow\n", stderr auf);

Abbruch ;

} sonst

ps-> Sachen [ps-> Größe ++] = x;

}\</Quelle>

Die Operation ist dafür verantwortlich, einen Wert vom Stapel und decrementing der Wert dessen zu entfernen. Eine verantwortliche C Durchführung wird auch überprüfen müssen, dass die Reihe nicht bereits leer ist.

int Knall (SCHOBERN *ps AUF)

{\

wenn (ps-> Größe == 0) {\

fputs ("Fehler: Schobern Sie underflow\n", stderr auf);

Abbruch ; } sonst

kehren Sie ps-> Sachen [-ps-> Größe] zurück;

}\</Quelle>

Wenn wir eine dynamische Reihe verwenden, dann können wir einen Stapel durchführen, der wachsen oder so viel, wie erforderlich, zurückweichen kann. Die Größe des Stapels ist einfach die Größe der dynamischen Reihe. Eine dynamische Reihe ist eine sehr effiziente Durchführung eines Stapels, seit dem Hinzufügen von Sachen dazu, oder das Entfernen von Sachen vom Ende einer dynamischen Reihe wird O (1) Zeit amortisiert.

Verbundene Liste

Die Durchführung der verbundenen Liste ist ebenso einfach und aufrichtig. Tatsächlich ist eine einfache einzeln verbundene Liste genügend, um einen Stapel durchzuführen — sie verlangt nur, dass der Hauptknoten oder das Element entfernt oder knallen gelassen werden können, und ein Knoten nur durch das Werden der neue Hauptknoten eingefügt werden kann.

Verschieden von der Reihe-Durchführung entspricht unsere Struktur typedef nicht zur kompletten Stapel-Struktur, aber zu einem einzelnen Knoten:

typedef struct schobern {\auf

int Daten;

struct schobern *next auf;

} STAPEL;</Quelle>

Solch ein Knoten ist zu einem typischen einzeln verbundenen Listenknoten, mindestens zu denjenigen identisch, die in C durchgeführt werden.

Die Operation sowohl initialisiert einen leeren Stapel, als auch fügt einen neuen Knoten zu einem nichtleeren hinzu. Es arbeitet durch den Empfang eines Datenwerts, um auf den Stapel, zusammen mit einem Zielstapel, das Schaffen eines neuen Knotens durch das Zuteilen des Gedächtnisses dafür, und dann das Einfügen davon in eine verbundene Liste als der neue Kopf zu stoßen:

leerer Stoß (SCHOBERN ** Kopf, int Wert AUF)

{\

SCHOBERN SIE *node = malloc (sizeof (STAPEL)) AUF;/* schaffen einen neuen Knoten * /

wenn (Knoten == UNGÜLTIG) {\

fputs ("Fehler: kein für node\n verfügbarer Raum", stderr);

Abbruch ;

} sonst {initialisieren/* Knoten * /

Knoten-> Daten = Wert;

Knoten-> als nächstes = leer (*head)? UNGÜLTIG: *head;/* fügen neuen Kopf wenn irgendwelcher * / ein

*head = Knoten;

}\

}\</Quelle>

Eine Operation entfernt den Kopf von der verbundenen Liste, und teilt den Zeigestock zum Kopf zum vorherigen zweiten Knoten zu. Es überprüft, ob die Liste vor dem Knallen davon leer ist:

int Knall (SCHOBERN ** Kopf AUF)

{\

wenn (leer (*head)) {/* Stapel * / leer ist

fputs ("Fehler: Schobern Sie underflow\n", stderr auf);

Abbruch ;

} sonst {lassen/* einen Knoten * / knallen

SCHOBERN SIE *top = *head AUF;

int Wert = Spitze-> Daten;

*head = Spitze-> als nächstes;

frei (Spitze);

geben Sie Wert zurück;

}\}\</Quelle>

Stapel und Programmiersprachen

Einige Sprachen, wie LISPELN und Pythonschlange, verlangen nach Stapel-Durchführungen seit dem Stoß nicht und knallen Funktionen sind für jede Liste verfügbar. Alle Hervor werden Sprachen (wie Adobe PostScript) auch um sprachdefinierte Stapel entworfen, die dazu direkt sichtbar und durch den Programmierer manipuliert sind. Beispiele vom Allgemeinen Lispeln:

(setf Liste (haben ''b 'c) Schlagseite)

;  (EIN B C)

(lassen Sie Liste knallen)

;  Ein

Liste

;  (B C)

(stoßen Sie 'neue Liste)

;  (NEUER B C)

</Quelle>

C ++ 's Standardschablone-Bibliothek stellt "" templated Klasse zur Verfügung, die eingeschränkt wird, um nur Operationen zu stoßen/knallen zu lassen. Javas Bibliothek enthält eine Klasse, die eine Spezialisierung von---ist, konnte das als ein Designfehler betrachtet werden, da die geerbten kommen , ignoriert Methode davon die LIFO Einschränkung. PHP hat eine Klasse von SplStack.

Hardware-Stapel

Eine übliche Anwendung von Stapeln am Architektur-Niveau ist als ein Mittel des Zuteilens und Zugreifens auf Gedächtnis.

Grundlegende Architektur eines Stapels

Ein typischer Stapel ist ein Gebiet des Computergedächtnisses mit einem festen Ursprung und einer variablen Größe. Am Anfang ist die Größe des Stapels Null. Ein Stapel-Zeigestock, gewöhnlich in der Form eines Hardware-Registers, weist zur am meisten kürzlich Verweise angebrachten Position auf dem Stapel hin; wenn der Stapel eine Größe der Null hat, weist der Stapel-Zeigestock zum Ursprung des Stapels hin.

Die zwei auf alle Stapel anwendbaren Operationen sind:

• eine Stoß-Operation, in die ein Datenartikel an der Position gelegt wird, hat zu durch den Stapel-Zeigestock hingewiesen, und die Adresse im Stapel-Zeigestock wird durch die Größe des Datenartikels angepasst;
• ein Knall oder Ziehen-Operation: Ein Datenartikel an der aktuellen Position, die auf durch den Stapel-Zeigestock angespitzt ist, wird entfernt, und der Stapel-Zeigestock wird durch die Größe des Datenartikels angepasst.

Es gibt viele Schwankungen auf dem Kernprinzip von Stapel-Operationen. Jeder Stapel hat eine feste Position im Gedächtnis, an dem er beginnt. Da Datensachen zum Stapel hinzugefügt werden, wird der Stapel-Zeigestock versetzt, um das aktuelle Ausmaß des Stapels anzuzeigen, der sich weg vom Ursprung ausbreitet.

Stapel-Zeigestöcke können zum Ursprung eines Stapels oder zu einer beschränkten Reihe von Adressen entweder oben oder unter dem Ursprung hinweisen (je nachdem die Richtung, in der der Stapel wächst); jedoch kann der Stapel-Zeigestock nicht den Ursprung des Stapels durchqueren. Mit anderen Worten, wenn der Ursprung des Stapels an der Adresse 1000 ist und der Stapel abwärts wächst (zu Adressen 999, 998, und so weiter), muss der Stapel-Zeigestock darüber hinaus 1000 (zu 1001, 1002, usw.) nie erhöht werden. Wenn eine Knall-Operation auf dem Stapel den Stapel-Zeigestock veranlasst, sich vorbei am Ursprung des Stapels zu bewegen, kommt ein Stapel-Unterlauf vor. Wenn eine Stoß-Operation den Stapel-Zeigestock veranlasst zu erhöhen oder Verminderung außer dem maximalen Ausmaß des Stapels, kommt eine Stapel-Überschwemmung vor.

Einige Umgebungen, die sich schwer auf Stapel verlassen, können zusätzliche Operationen zum Beispiel zur Verfügung stellen:

• Duplikat: Der Spitzenartikel wird knallen gelassen, und dann wieder (zweimal) gestoßen, so dass eine zusätzliche Kopie des ehemaligen Spitzenartikels jetzt auf der Spitze, mit dem Original darunter ist.
• Piepsen: Der höchste Artikel wird untersucht (oder zurückgegeben), aber der Stapel-Zeigestock wird nicht geändert, und die Stapel-Größe ändert sich nicht (das Meinen, dass der Artikel auf dem Stapel bleibt). Das wird auch Spitzenoperation in vielen Artikeln genannt.
• Tausch oder Austausch: Die zwei höchsten Sachen auf dem Stapel tauschen Plätze aus.
• Rotieren Sie (oder Rolle): Die n höchsten Sachen werden auf dem Stapel auf eine rotierende Mode bewegt. Zum Beispiel, wenn n=3, Sachen 1, 2, und 3 auf dem Stapel zu Positionen 2, 3, und 1 auf dem Stapel beziehungsweise bewegt werden. Viele Varianten dieser Operation sind möglich, mit dem allgemeinsten, das verlassen wird nennt, rotieren, und Recht rotieren.

Stapel werden entweder vergegenwärtigt, von von unten nach oben (wie wirkliche Stapel), oder mit der Spitze des Stapels in einer festen Position wachsend (sieh Image [Zeichen im Image, die Spitze (28) ist der Stapel 'Boden', da der Stapel 'Spitze' ist, wo Sachen gestoßen oder von] knallen gelassen werden), ein Münzhalter, ein Automat von Pez, oder vom linken bis Recht wachsend, so dass "höchst" "niedrigstwertig" wird. Diese Vergegenwärtigung kann der wirklichen Struktur des Stapels im Gedächtnis unabhängig sein. Das bedeutet, dass ein Recht rotiert, wird das erste Element zur dritten Position, das zweite zum ersten und das dritte zum zweiten bewegen. Hier sind zwei gleichwertige Vergegenwärtigungen dieses Prozesses:

Apfelbanane

Banane === Recht rotiert ==> Gurke

Gurke-Apfel

Gurke-Apfel

Banane === verlassen rotiert ==> Gurke

Apfelbanane

Ein Stapel wird gewöhnlich in Computern durch einen Block von Speicherzellen, mit dem "Boden" an einer festen Position und dem Stapel-Zeigestock vertreten, der die Adresse der aktuellen "Spitzen"-Zelle im Stapel hält. Die Spitze und unterste Fachsprache werden ohne Rücksicht darauf verwendet, ob der Stapel wirklich zu niedrigeren Speicheradressen oder zu höheren Speicheradressen wächst.

Das Stoßen eines Artikels auf dem Stapel passt den Stapel-Zeigestock durch die Größe des Artikels an (entweder decrementing oder das Erhöhen, abhängig von der Richtung, in der der Stapel im Gedächtnis wächst) hinweisend kopiert es zur folgenden Zelle, und den neuen Spitzenartikel zum Stapel-Gebiet. Wieder von der genauen Durchführung am Ende einer Stoß-Operation abhängend, kann der Stapel-Zeigestock zur folgenden unbenutzten Position im Stapel hinweisen, oder es kann zum höchsten Artikel im Stapel hinweisen. Wenn der Stapel zum aktuellen höchsten Artikel hinweist, wird der Stapel-Zeigestock aktualisiert, bevor ein neuer Artikel auf den Stapel gestoßen wird; wenn es zur folgenden verfügbaren Position im Stapel hinweist, wird es aktualisiert, nachdem der neue Artikel auf den Stapel gestoßen wird.

Das Knallen des Stapels ist einfach das Gegenteil des Stoßens. Der höchste Artikel im Stapel wird entfernt, und der Stapel-Zeigestock, wird in der entgegengesetzten Ordnung davon aktualisiert, das in der Stoß-Operation verwendet ist.

Hardware-Unterstützung

Stapel im Hauptgedächtnis

Die meisten Zentraleinheiten haben Register, die als Stapel-Zeigestöcke verwendet werden können. Verarbeiter-Familien wie der x86, Z80, 6502, und haben viele andere spezielle Instruktionen, die implizit einen hingebungsvollen (Hardware) Stapel-Zeigestock verwenden, um opcode Raum zu erhalten. Einige Verarbeiter, wie der PDP-11 und die 68000, haben auch spezielle Wenden-Weisen für die Durchführung von Stapeln, normalerweise mit einem halbhingebungsvollen Stapel-Zeigestock ebenso (wie A7 in den 68000). Jedoch, in den meisten Verarbeitern, können mehrere verschiedene Register als zusätzliche Stapel-Zeigestöcke, wie erforderlich, verwendet werden (ob aktualisiert über das Wenden von Weisen oder darüber Instruktionen/U-Boot hinzufügen).

Stapel in Registern oder gewidmetem Gedächtnis

Der x87, der Punkt-Architektur schwimmen lässt, ist ein Beispiel von einer Reihe von als ein Stapel organisierten Registern, wo der direkte Zugang zu individuellen Registern (Verwandter die aktuelle Spitze) auch möglich ist. Als mit Stapel-basierten Maschinen, im Allgemeinen die Spitze des Stapels weil habend, berücksichtigt ein implizites Argument einen kleinen Maschinencodefußabdruck mit einem guten Gebrauch der Busbandbreite und geheimen Codelager, aber es verhindert auch einige Typen von Optimierungen, die auf Verarbeitern möglich sind, die zufälligen Zugang zur Register-Datei für alle (zwei oder drei) operands erlauben. Eine Stapel-Struktur macht auch Superskalardurchführungen mit der Register-Umbenennung (für die spekulative Ausführung) etwas komplizierter, um durchzuführen, obwohl es noch, wie veranschaulicht, durch moderne x87 Durchführungen ausführbar ist.

Sonne SPARC, AMD Am29000, und Intel i960 ist alle Beispiele von Architekturen mit Register-Fenstern innerhalb eines Register-Stapels als eine andere Strategie, den Gebrauch des langsamen Hauptgedächtnisses für Funktionsargumente und Rückwerte zu vermeiden.

Es gibt auch mehrere kleine Mikroprozessoren, der einen Stapel direkt in der Hardware durchführt und einige Mikrokontrolleure einen Stapel der festen Tiefe haben, der nicht direkt zugänglich ist. Beispiele sind die FOTO-Mikrokontrolleure, die Computercowboys MuP21, der Harris RTX Linie und der Novix NC4016. Viele Stapel-basierte Mikroprozessoren wurden verwendet, um die Programmiersprache Hervor am Mikrocodeniveau durchzuführen. Stapel wurden auch als eine Basis mehrerer Großrechner und Minicomputer verwendet. Solche Maschinen wurden Stapel-Maschinen, das berühmteste Wesen der Burroughs B5000 genannt.

Anwendungen

Stapel haben zahlreiche Anwendungen. Wir sehen Stapel im täglichen Leben aus den Büchern in unserer Bibliothek zum Bündel von Papieren, die wir in unserem Drucker-Tablett behalten. Sie alle folgen der Logik von Last In First Out (LIFO), dieser ist, wenn wir ein Buch zu einem Stapel von Büchern hinzufügen, fügen wir es zur Spitze des Stapels hinzu, wohingegen, wenn wir ein Buch vom Stapel entfernen, wir es allgemein von der Spitze des Stapels entfernen.

Gegeben unten sind einige Anwendungen von Stapeln in der Welt von Computern:

Das Umwandeln einer Dezimalzahl in eine Binärzahl

Die Logik, für eine Dezimalzahl in eine Binärzahl umzugestalten, ist wie folgt:

1. Lesen Sie eine Zahl
2. Wiederholung (während Zahl größer ist als Null)
3. Finden Sie den Rest nach dem Teilen der Zahl durch 2 heraus
4. Drucken Sie den Rest
5. Teilen Sie die Zahl durch 2
6. Beenden Sie die Wiederholung

Jedoch gibt es ein Problem mit dieser Logik. Nehmen Sie die Zahl an, deren binäre Form, die wir finden wollen, 23 ist. Mit dieser Logik bekommen wir das Ergebnis als 11101, anstatt 10111 zu kommen.

Um dieses Problem zu beheben, verwenden wir einen Stapel. Wir machen vom LIFO Eigentum des Stapels Gebrauch. Am Anfang stoßen wir die binäre Ziffer, die in den Stapel gebildet ist, anstatt es direkt zu drucken. Nachdem die komplette Zahl in die binäre Form umgewandelt worden ist, lassen wir eine Ziffer auf einmal vom Stapel knallen und drucken es. Deshalb ließen wir die Dezimalzahl in seine richtige binäre Form umwandeln.

Algorithmus:

fungieren Sie outputInBinary (Ganze Zahl n)

Schobern Sie s = neuer Stapel auf

während n> 0 tun

Ganze Zahl hat = n modulo 2 gebissen

s.push (Bit)

wenn s dann voll

ist

geben Sie Fehler zurück

enden Sie wenn

n = Fußboden (n / 2)

enden Sie während

während s nicht leer ist, tun

Produktion (s.pop )

enden Sie während

beenden Sie Funktion

Türme Hanois

Eine der interessantesten Anwendungen von Stapeln kann im Lösen eines Rätsels genannt der Turm Hanois gefunden werden. Gemäß einer alten Brahmane-Geschichte wird die Existenz des Weltalls in Bezug auf die Zeit berechnet, die von mehreren Mönchen genommen ist, die die ganze Zeit arbeiten, um 64 Platten von einem Pol zu einem anderen zu bewegen. Aber es gibt einige Regeln darüber, wie das getan werden sollte, die sind:

1. bewegen Sie nur eine Platte auf einmal.
2. für die vorläufige Lagerung kann ein dritter Pol verwendet werden.
3. eine Platte des größeren Diameters darf auf einer Platte des kleineren Diameters nicht gelegt werden.

Weil der Algorithmus dieses Rätsels Turm Hanois sieht.

Nehmen Sie an, dass A der erste Turm ist, ist B der zweite Turm, & C ist der dritte Turm.

</br>

Produktion: (Wenn es 3 Platten gibt)

Lassen Sie 1 die kleinste Platte, 2 sein, die Platte der mittleren Größe und 3 sein, die größte Platte sein.

Der C ++ Code für diese Lösung kann auf zwei Weisen durchgeführt werden:

Die erste Durchführung (ohne Stapel zu verwenden)

leerer TowersofHanoi (interne Nummer n, interne Nummer a, interne Nummer b, interne Nummer c)

{\

wenn (n> 0)

{\

TowersofHanoi (n-1, a, c, b);//recursion

cout

Die zweite Durchführung (Stapel verwendend)

//Globale Variable, Turm [1:3] ist drei Türme

arrayStack

leerer TowerofHanoi (interne Nummer n)

{\

//Vorverarbeiter für moveAndShow.

für (interne Nummer d = n; d> 0; d-)//initialisieren

Turm [1].push (d);//fügen Platte d zum Turm 1 hinzu

moveAndShow (n, 1, 2, 3);/*move n Platten vom Turm 1 zum Turm das 3 Verwenden

Turm 2 als Zwischenglied tower*/

}\

Leere moveAndShow (interne Nummer n, interne Nummer a, interne Nummer b, interne Nummer c)

{\

//Bewegen Sie die Spitze n Platten vom Turm zum Turm b sich zeigende Staaten.

//Verwenden Sie Turm c für das Zwischenlager.

wenn (n> 0) {\

moveAndShow (n-1, a, c, b);//recursion

interne Nummer d = Turm [x].top ;//bewegen eine Scheibe von der Spitze des Turms x zur Spitze von

Turm [x].pop ;//Turm y

Turm [y].push (d);

showState ;//zeigen Staat von 3 Türmen

moveAndShow (n-1, c, b, a);//recursion

}\}\</Quelle>

Jedoch ist die Kompliziertheit für obengenannte schriftliche Durchführungen O . So ist es offensichtlich, dass Problem nur für kleine Werte von n behoben werden kann (allgemein n

Ausdruck-Einschätzung und Syntax-Syntaxanalyse

Rechenmaschinen, die polnische Rücknotation verwenden, verwenden eine Stapel-Struktur, um Werte zu halten. Ausdrücke können im Präfix, der postüblen Lage oder den klammerlosen Darstellungen vertreten werden, und die Konvertierung von einer Form bis einen anderen kann mit einem Stapel vollbracht werden. Viele Bearbeiter verwenden einen Stapel, für die Syntax von Ausdrücken, Programm-Blöcke usw. vor dem Übersetzen in den Code der niedrigen Stufe grammatisch zu analysieren. Die meisten Programmiersprachen sind Sprachen ohne Zusammenhänge, das Erlauben von sie, mit dem Stapel grammatisch analysiert zu werden, hat Maschinen gestützt.

Die Einschätzung eines Infix-Ausdrucks, der völlig parenthesized ist

Eingang: (((2 * 5) - (1 * 2)) / (11 - 9))

Produktion: 4

Analyse: Fünf Typen von Eingangscharakteren

1. Öffnende Klammer
2. Zahlen
3. Maschinenbediener
4. Schlussklammer
5. Neuer Liniencharakter

Datenstruktur-Voraussetzung: Ein Charakter-Stapel

Algorithmus

1. Lesen Sie Derjenige-Eingangscharakter

2. Handlungen am Ende jedes Eingangs

Öffnende Klammern (2.1) Stoß in den Stapel und Gehen dann zum Schritt (1)

Der Stoß Nummer (2.2) in den Stapel und Geht dann zum Schritt (1)

Maschinenbediener (2.3) Stoß in den Stapel und Geht dann zum Schritt (1)

Schlussklammern (2.4) Pop vom Charakter schobern auf

(2.4.1) wenn es Klammer schließt, dann verwerfen Sie es, Gehen Sie zum Schritt (1)

(2.4.2) Knall wird viermal verwendet

Das erste knallen gelassene Element wird op2 zugeteilt

Das zweite knallen gelassene Element wird op zugeteilt

Das dritte knallen gelassene Element wird op1 zugeteilt

Das vierte knallen gelassene Element ist die restliche öffnende Klammer, die verworfen werden kann

Bewerten Sie op1 op op2

Wandeln Sie das Ergebnis in den Charakter und um

stoßen Sie in den Stapel

Gehen Sie zum Schritt (2.4)

Neuer Liniencharakter (2.5) Pop vom Stapel und Druck die Antwort

HÖREN SIE AUF

Ergebnis: Die Einschätzung völlig parenthesized Infix-Ausdruck wird wie folgt gedruckt:

Eingangsschnur: (((2 * 5) - (1 * 2)) / (11 - 9))

Die Einschätzung des Infix-Ausdrucks, der nicht völlig parenthesized ist

Eingang: (2 * 5 - 1 * 2) / (11 - 9)

Produktion: 4

Analyse: Es gibt fünf Typen von Eingangscharakteren, die sind:

1. Öffnende Klammern

Zahlen Maschinenbediener

1. Schlussklammern
2. Neuer Liniencharakter (\n)

Wir wissen nicht, was man tut, wenn ein Maschinenbediener als ein Eingangscharakter gelesen wird.

Durch das Einführen des Vorrangs herrschen für Maschinenbediener, wir haben eine Lösung dieses Problems.

Die Vorzugsregel: Wir sollten eine vergleichende Vorzugskontrolle durchführen, wenn ein Maschinenbediener gelesen wird, und dann stoßen Sie sie. Wenn die Stapel-Spitze einen Maschinenbediener vom Vorrang höher enthält als oder gleich dem Vorrang des Eingangsmaschinenbedieners, dann lassen wir es knallen und drucken es. Wir setzen fort, die Vorzugskontrolle durchzuführen, bis die Spitze des Stapels entweder einen Maschinenbediener vom niedrigeren Vorrang enthält, oder wenn es keinen Maschinenbediener enthält.

Datenstruktur-Voraussetzung für dieses Problem: Ein Charakter-Stapel und eine ganze Zahl schobern auf

Algorithmus:

1. Lesen Sie einen Eingangscharakter

2. Handlungen, die am Ende jedes Eingangs durchgeführt werden

Öffnende Klammern (2.1) Stoß schobert es in den Charakter auf und Geht dann zum Schritt (1)

Stoß Nummer (2.2) in den Stapel der ganzen Zahl, Gehen Sie zum Schritt (1)

Maschinenbediener (2.3) Tut die vergleichende Vorzugskontrolle

(2.3.1) wenn die Charakter-Stapel-Spitze einen Maschinenbediener mit gleichem enthält

oder höherer Vorrang, dann lassen Sie es in op knallen

Lassen Sie eine Zahl vom Stapel der ganzen Zahl in op2 knallen

Lassen Sie eine andere Zahl vom Stapel der ganzen Zahl in op1 knallen

Berechnen Sie op1 op op2 und stoßen Sie das Ergebnis in die ganze Zahl

Stapel

Schlussklammern (2.4) Pop vom Charakter schobern auf

(2.4.1) wenn es eine öffnende Klammer ist, dann verwerfen Sie es und Gehen Sie zu

Schritt (1)

(2.4.2) Zu op, teilen Sie das knallen gelassene Element zu

Knallen Sie eine Zahl von der ganzen Zahl schobern auf und teilen es op2 zu

Knallen Sie eine andere Zahl von der ganzen Zahl schobern auf und teilen es zu

zu op1

Berechnen Sie op1 op op2 und stoßen Sie das Ergebnis in die ganze Zahl Stapel

Bekehrter in den Charakter und Stoß in den Stapel

Gehen Sie zum Schritt (2.4)

Neuer Liniencharakter (2.5) Druck das Ergebnis nach dem Knallen vom Stapel

HÖREN SIE AUF

Ergebnis: Die Einschätzung eines Infix-Ausdrucks, der nicht völlig parenthesized ist, wird wie folgt gedruckt:

Eingangsschnur: (2 * 5 - 1 * 2) / (11 - 9)

Einschätzung des Präfix-Ausdrucks

Eingang: / - * 2 5 * 1 2 - 11 9

Produktion: 4

Analyse: Es gibt drei Typen von Eingangscharakteren

Zahlen Maschinenbediener Neuer Liniencharakter (\n)

Datenstruktur-Voraussetzung: Ein Charakter-Stapel und eine ganze Zahl schobern auf

Algorithmus:

1. Lesen Sie einen Charakter-Eingang auf einmal und setzen Sie fort, ihn in den Charakter-Stapel bis zum neuen zu stoßen

Liniencharakter wird erreicht

2. Führen Sie Knall vom Charakter-Stapel durch. Wenn der Stapel leer ist, gehen Sie zum Schritt (3)

Stoß Nummer (2.1) in zur ganzen Zahl schobert auf und geht dann zum Schritt (1)

Maschinenbediener (2.2) Teilt den Maschinenbediener op Zu

Knallen Sie eine Zahl von der ganzen Zahl schobern auf und teilen es op1 zu

Knallen Sie eine andere Zahl von der ganzen Zahl schobern auf

und teilen Sie es op2 zu

Berechnen Sie op1 op op2 und stoßen Sie die Produktion in die ganze Zahl

Stapel. Gehen Sie zum Schritt (2)

3. Knallen Sie das Ergebnis von der ganzen Zahl schobern auf und zeigen das Ergebnis

Ergebnis: Die Einschätzung des Präfix-Ausdrucks wird wie folgt gedruckt:

Eingangsschnur: / - * 2 5 * 1 2 - 11 9

Einschätzung des Ausdrucks der postüblen Lage

Die Berechnung: 1 + 2 * 4 + 3 kann wie das in der Notation der postüblen Lage mit dem Vorteil keiner Prioritätsregeln und erforderlicher Parenthesen niedergeschrieben werden:

1 2 4 * + 3 +

Der Ausdruck wird vom links zum Recht mit einem Stapel bewertet:

wenn

1. man auf einen operand stößt: Stoßen Sie es

wenn

1. man auf einen Maschinenbediener stößt: Lassen Sie zwei operands knallen, bewerten Sie das Ergebnis und stoßen Sie es.

Wie der folgende Weg (wird der Stapel gezeigt, nachdem hat Operation stattgefunden):

Das Endresultat, 12, liegt auf der Spitze des Stapels am Ende der Berechnung.

Beispiel in C

1. einschließen

int Hauptsache

{\

interne Nummer [100], ich;

printf ("Um zu knallen, gehen in-1\n" ein);

für (ich = 0;)

{\

printf ("Stoß");

scanf (" %d", &a [ich]);

wenn ([ich] ==-1)

{\

wenn (ich == 0)

{\

printf ("Underflow\n");

}\

sonst

{\

printf ("knallen = %d\n", [-ich]);

}\

}\

sonst

{\

ich ++;

}\

}\

} </Quelle>

Einschätzung des Ausdrucks der postüblen Lage (Pascal)

Das ist eine Durchführung in Pascal, das Verwenden hat folgende Datei als Datenarchive gekennzeichnet.

{\

Programmierer: clx321

Datei: stack.pas

Einheit: Pstack.tpu

}\

Programm TestStack;

{verwendet dieses Programm ADT des Stapels, ich werde annehmen, dass die Einheit von ADT des Stapels bereits }\bestanden hat

Gebrauch

PStack; {ADT des STAPELS }\

{Wörterbuch }\

const

Zeichen ='.';

var

Daten: Stapel;

f: Text;

Cc: Rotforelle;

ccInt, cc1, cc2: ganze Zahl;

{Funktionen }\

IsOperand (Cc: Rotforelle): boolean; {GERADE Prototyp }\

{kehren WAHR zurück, wenn Cc operand }\ist

ChrToInt (Cc: Rotforelle): ganze Zahl; {GERADE Prototyp }\

{ändern Rotforelle zur ganzen Zahl }\

Maschinenbediener (cc1, cc2: ganze Zahl): ganze Zahl; {GERADE Prototyp }\

{bedienen zwei operands }\

{Algorithmen }\

beginnen Sie

teilen Sie (f, Cc) zu;

Rücksetzen (f);

lesen Sie (f, Cc); {der erste elmt }\

wenn (Cc = Zeichen) dann

beginnen Sie

writeln ('leere Archive!');

Ende

sonst

beginnen Sie

wiederholen Sie

wenn (IsOperand (Cc)) dann

beginnen Sie

ccInt: = ChrToInt (Cc);

stoßen Sie (ccInt, Daten);

Ende

sonst

beginnen Sie

Knall (cc1, Daten);

Knall (cc2, Daten);

stoßen Sie (Daten, Maschinenbediener (cc2, cc1));

Ende;

lesen Sie (f, Cc); {folgender elmt }\

bis (Cc = Zeichen);

Ende;

nah (f);

Ende

</Quelle>}\

Die Konvertierung eines Infix-Ausdrucks, der völlig parenthesized in einen Ausdruck der Postüblen Lage ist

Eingang: (((8 + 1) - (7 - 4)) / (11 - 9))

Produktion: 8 1 + 7 4 - - 11 9 - /

Analyse: Es gibt fünf Typen von Eingangscharakteren, die sind:

* Öffnende Klammern

* Zahlen

* Maschinenbediener

* Schlussklammern

* Neuer Liniencharakter (\n)

Voraussetzung: Ein Charakter-Stapel

Algorithmus:

1. Lesen Sie einen Charakter Eingang

2. Handlungen, die am Ende jedes Eingangs durchzuführen

sind Öffnende Klammern (2.1) Stoß in den Stapel und Gehen dann zum Schritt (1)

Druck Nummer (2.2) und Geht dann zum Schritt (1)

Maschinenbediener (2.3) Stoß in den Stapel und Geht dann zum Schritt (1)

Schlussklammern (2.4) Pop es vom Stapel

(2.4.1) Wenn es ein Maschinenbediener ist, drucken Sie es, Gehen Sie zum Schritt (2.4)

(2.4.2) Wenn das knallen gelassene Element eine öffnende Klammer, ist

verwerfen Sie es und gehen Sie zum Schritt (1)

Neuer Liniencharakter (2.5) HALT

Deshalb ist die Endproduktion nach der Konvertierung eines Infix-Ausdrucks zu einem Ausdruck der postüblen Lage wie folgt:

Umordnen von Gleise-Autos

Problem-Beschreibung

Das ist eine nützliche Anwendung von Stapeln. Denken Sie, dass ein Güterzug n Gleise-Autos, jeder hat, um an der verschiedenen Station verlassen zu werden. Sie werden 1 durch n gezählt, und Güterzug besucht diese Stationen im Auftrag n bis 1. Offensichtlich werden die Gleise-Autos durch ihren Bestimmungsort etikettiert. Um Eliminierung der Autos vom Zug zu erleichtern, müssen wir sie in aufsteigender Reihenfolge ihrer Zahl (d. h. 1 durch n) umordnen. Wenn Autos in dieser Ordnung sind, können sie an jeder Station losgemacht werden. Wir ordnen Autos an einem Verschiebebahnhof um, der Spur, Produktionsspur und k haltende Spuren zwischen dem Eingang & Produktionsspuren eingegeben hat (d. h. Spur haltend).

Lösungsstrategie

Um Autos umzuordnen, untersuchen wir die Autos auf dem Eingang von vorne nach hinten. Wenn das Auto, das wird untersucht, folgendes in der Produktionseinordnung ist, bewegen wir es direkt zur Produktionsspur. Wenn nicht, wir bewegen es zur haltenden Spur & verlassen es dort, bis es Zeit ist, um es zur Produktionsspur zu legen. Die haltenden Spuren funktionieren auf eine LIFO Weise, weil die Autos eingehen & diese Spuren von der Spitze verlassen. Wenn das Umordnen von Autos nur im Anschluss an Bewegungen erlaubt wird:

• Ein Auto kann von der Vorderseite (d. h. richtiges Ende) von der Eingangsspur zur Spitze von einer der haltenden Spuren oder zum linken Ende der Produktionsspur bewegt werden.
• Ein Auto kann von der Spitze der haltenden Spur zum linken Ende der Produktionsspur bewegt werden.

Die Zahl zeigt einen Verschiebebahnhof mit k = 3, Spuren H1, H2 & H3, auch n = 9 haltend. Die n Autos des Güterzugs beginnen im Eingang verfolgen & sollen in der Produktionsspur im Auftrag 1 durch n vom Recht bis linken enden. Die Autos sind am Anfang im Auftrag 5,8,1,7,4,2,9,6,3 von die Rückseite nach vorn. Spätere Autos werden in der gewünschten Ordnung umgeordnet.

Ein drei Spur-Beispiel

• Denken Sie die Eingangseinordnung von der Zahl, hier bemerken wir, dass das Auto 3 an der Vorderseite ist, so kann es nicht Produktion noch, als es sein, um durch Autos 1 & 2 vorangegangen zu werden. So wird Auto 3 losgemacht & zur haltenden Spur H1 bewegt.
• Das folgende Auto 6 kann nicht Produktion sein, & es wird zur haltenden Spur H2 bewegt. Weil wir zum Produktionsauto 3 vor dem Auto 6 haben & das nicht möglich wird, wenn wir Auto 6 zur haltenden Spur H1 bewegen.
• Jetzt ist es offensichtlich, dass wir Auto 9 zu H3 bewegen.

Die Voraussetzung der Neuordnung von Autos auf jeder haltenden Spur ist, dass die Autos bevorzugt werden sollten, um sich in aufsteigender Reihenfolge von oben bis unten zu einigen.

• So wird Auto 2 jetzt zur haltenden Spur H1 bewegt, so dass es die vorherige Behauptung befriedigt. Wenn wir Auto 2 zu H2 oder H3 bewegen, dann haben wir keinen Platz, Autos 4,5,7,8 zu bewegen. Kleinste Beschränkungen des zukünftigen Autostellens entstehen, wenn das neue Auto λ zur haltenden Spur bewegt wird, die ein Auto an seiner Spitze mit dem kleinsten Etikett Ψ solch dass λ hat

Das Zurückverfolgen

Eine andere wichtige Anwendung von Stapeln ist Rückverfolgung.

Denken Sie ein einfaches Beispiel, den richtigen Pfad in einem Irrgarten zu finden. </br> gibt Es eine Reihe von Punkten vom Startpunkt bis den Bestimmungsort. Wir fangen von einem Punkt an. Um den endgültigen Bestimmungsort zu erreichen, gibt es mehrere Pfade. Nehmen Sie an, dass wir einen zufälligen Pfad wählen. Nach dem Folgen einem bestimmten Pfad begreifen wir, dass der Pfad, den wir gewählt haben, falsch ist. So müssen wir einen Weg finden, durch den wir zurück zum Anfang dieses Pfads zurückkehren können. Das kann mit dem Gebrauch von Stapeln getan werden.

Mit der Hilfe von Stapeln erinnern wir uns an den Punkt, wo wir gereicht haben. </br> wird Das durch das Stoßen dieses Punkts in den Stapel getan. Im Falle dass wir auf dem falschen Pfad enden, können wir den letzten Punkt vom Stapel knallen lassen und so zurück zum letzten Punkt zurückkehren und unsere Suche fortsetzen, um den richtigen Pfad zu finden. Das wird genannt denselben Weg zurückverfolgend.

Schnellsortierung

Das Sortieren bedeutet, die Liste von Elementen in einer besonderen Ordnung einzuordnen. Im Falle Zahlen konnte es, oder im Fall von Briefen, alphabetischer Ordnung in aufsteigender Reihenfolge sein.

Schnellsortierung ist ein Algorithmus des Teilens, und überwinden Sie Typ. In dieser Methode, um eine Reihe von Zahlen zu sortieren, reduzieren wir es auf zwei kleinere Sätze, und sortieren dann diese kleineren Sätze.

Das kann mit der Hilfe des folgenden Beispiels erklärt werden:

Nehmen Sie an, dass A eine Liste der folgenden Zahlen ist:

Im Verminderungsschritt finden wir die Endposition von einer der Zahlen. Lassen Sie uns in diesem Fall annehmen, dass wir die Endposition 48 finden müssen, der die erste Zahl in der Liste ist.

Um das zu vollbringen, nehmen wir die folgende Methode an. Beginnen Sie mit der letzten Zahl, und bewegen Sie sich vom Recht bis linken. Vergleichen Sie jede Zahl mit 48. Wenn die Zahl kleiner ist als 48, halten wir an dieser Zahl an und tauschen sie mit 48.

In unserem Fall ist die Zahl 24. Folglich tauschen wir 24 und 48.

Die Nummern 96 und 72 rechts von 48, sind größer als 48. Jetzt mit 24 beginnend, scannen Sie die Zahlen in der entgegengesetzten Richtung, die vom linken bis Recht ist. Vergleichen Sie jede Zahl mit 48, bis Sie eine Zahl finden, die größer ist als 48.

In diesem Fall ist es 60. Deshalb tauschen wir 48 und 60.

Bemerken Sie, dass die Nummern 12, 24 und 36 links von 48 alle kleiner sind als 48. Fangen Sie jetzt an, Zahlen von 60, im Recht auf die linke Richtung zu scannen. Sobald Sie kleinere Zahl finden, sie mit 48 tauschen.

In diesem Fall ist es 44. Tauschen Sie es mit 48. Das Endresultat ist:

Jetzt, mit 44 beginnend, scannen Sie die Liste vom linken bis Recht, bis Sie eine Zahl größer finden als 48.

Solch eine Zahl ist 84. Tauschen Sie es mit 48. Das Endresultat ist:

Jetzt, mit 84 beginnend, überqueren Sie die Liste vom Recht bis linken, bis Sie eine Zahl erreichen, die kleiner ist als 48. Wir finden solch eine Zahl vor dem Erreichen 48 nicht. Das bedeutet, dass alle Zahlen in der Liste gescannt worden sind und im Vergleich zu 48. Außerdem bemerken wir, dass alle Zahlen, die weniger als 48 links davon, und alle Zahlen sind, die größer sind als 48, an seiner rechten Seite sind.

Die Endteilungen sehen wie folgt aus:

Deshalb, 48 ist in seine richtige Position gelegt worden, und jetzt wird unsere Aufgabe auf das Sortieren der zwei Teilungen reduziert.

Das über dem Schritt, Teilungen zu schaffen, kann mit jeder Teilung wiederholt werden, die 2 oder mehr Elemente enthält. Da wir nur eine einzelne Teilung auf einmal bearbeiten können, sollten wir im Stande sein, die anderen Teilungen für die zukünftige Verarbeitung nachzugehen.

Das wird durch das Verwenden von zwei Stapeln genannt LOWERBOUND und UPPERBOUND getan, um diese Teilungen provisorisch zu versorgen. Die Adressen vor allen Dingen Elemente der Teilungen werden in den LOWERBOUND und die UPPERBOUND-Stapel beziehungsweise gestoßen. Jetzt wird der obengenannte Verminderungsschritt auf die Teilungen nur angewandt, nachdem seine Grenzwerte vom Stapel knallen gelassen werden.

Wir können das vom folgenden Beispiel verstehen:

Nehmen Sie die obengenannte Liste mit 12 Elementen. Der Algorithmus fängt durch das Stoßen der Grenzwerte von A an, der 1 und 12 in den LOWERBOUND und die UPPERBOUND-Stapel beziehungsweise ist. Deshalb sehen die Stapel wie folgt aus:

LOWERBOUND: 1 UPPERBOUND: 12

Um den Verminderungsschritt durchzuführen, werden die Werte der Stapel-Spitze vom Stapel knallen gelassen. Deshalb werden beide die Stapel leer.

LOWERBOUND: {Leerer} UPPERBOUND: {Leerer }\

Jetzt veranlasst der Verminderungsschritt 48, zur 5. Position befestigt zu werden, und schafft zwei Teilungen, ein von der Position 1 bis 4 und anderer von der Position 6 bis 12. Folglich werden die Werte 1 und 6 in den LOWERBOUND-Stapel und 4 gestoßen, und 12 werden in den UPPERBOUND-Stapel gestoßen.

LOWERBOUND: 1, 6 UPPERBOUND: 4, 12

Für den Verminderungsschritt wieder anzuwenden, werden die Werte an der Stapel-Spitze knallen gelassen. Deshalb werden die Werte 6 und 12 knallen gelassen. Deshalb sind die Stapel ähnlich:

LOWERBOUND: 1 UPPERBOUND: 4

Der Verminderungsschritt wird jetzt auf die zweite Teilung angewandt, die vom 6. bis 12. Element ist.

Nach dem Verminderungsschritt, 98 wird in der 11. Position befestigt. Also, die zweite Teilung hat nur ein Element. Deshalb stoßen wir die oberen und niedrigeren Grenzwerte der ersten Teilung auf den Stapel. Also, die Stapel sind wie folgt:

LOWERBOUND: 1, 6 UPPERBOUND: 4, 10

Der in einer Prozession gehende Erlös folgendermaßen und Enden, wenn die Stapel keine oberen und niedrigeren Grenzen der Teilung enthalten, die, und die Liste zu bearbeiten ist, wird sortiert.

Das Aktienspanne-Problem

Im Aktienspanne-Problem werden wir ein Finanzproblem mit der Hilfe von Stapeln beheben.

Denken Sie für ein Lager, wir haben eine Reihe von n tägliche Preisangebote, die Spanne des Preises des Lagers an einem besonderen Tag wird als die maximale Zahl von Konsekutivtagen definiert, für die der Preis des Lagers am aktuellen Tag weniger ist als oder gleich seinem Preis an diesem Tag.

Ein Algorithmus, der Quadratische Zeitkompliziertheit hat

Eingang: Eine Reihe P mit n Elementen

Produktion: Eine Reihe S n solcher Elemente dass S bin [ich] die größte ganze Zahl k solch dass k

Beauftragen Sie Wert von k zu S [ich] damit, die Spanne des Lagers zu bekommen

4. Geben Sie Reihe S zurück

Jetzt, diesen Algorithmus für die Laufzeit analysierend, beobachten wir:

• Wir haben die Reihe S am Anfang initialisiert und es am Ende zurückgegeben. Das ist eine unveränderliche Zeitoperation, folglich nimmt O (n) Zeit
• Die mehrmalige Schleife wird innerhalb für die Schleife verschachtelt. Für die Schleife, deren Schalter ist, werde ich n Zeiten hingerichtet. Die Behauptungen, die nicht in der mehrmaligen Schleife, aber in für die Schleife sind, werden n Zeiten durchgeführt. Deshalb diese Behauptungen und das Erhöhen und die Bedingungsprüfung von nehme mir O (n) Zeit.
• In der Wiederholung von mir für den Außen-für die Schleife wird der Körper der inneren mehrmaligen Schleife Maximum i + 1mal durchgeführt. Im Grenzfall Element S bin [ich] größer als alle vorherigen Elemente. Also, für prüfend, wenn Bedingung die Behauptung nachdem das, sowie die Prüfung bis zur Bedingung, ich + 1mal während der Wiederholung i für den Außen-für die Schleife durchgeführt werden. Folglich ist die von der inneren Schleife genommene Gesamtzeit O (n (n + 1)/2), der O ist

Die Laufzeit aller dieser Schritte wird durch das Hinzufügen der von allen diesen drei Schritten genommenen Zeit berechnet. Die ersten zwei Begriffe sind O , während der letzte Begriff O ist. Deshalb ist die Gesamtlaufzeit des Algorithmus O .

Ein Algorithmus, der Geradlinige Zeitkompliziertheit hat

Um die Spanne effizienter zu berechnen, sehen wir, dass die Spanne an einem besonderen Tag leicht berechnet werden kann, wenn wir den nächsten Tag bevor ich, solch wissen, dass der Preis der Lager an diesem Tag höher war als der Preis der Lager am heutigen Tag. Wenn dort solch ein Tag besteht, können wir ihn durch h (i) vertreten und h (i) initialisieren, um-1 zu sein.

Deshalb wird die Spanne eines besonderen Tages durch die Formel, gegeben

s = ich - h (i).

Um diese Logik durchzuführen, verwenden wir einen Stapel als ein abstrakter Datentyp, um die Tage i, h (i), h (h (i)) und so weiter zu versorgen. Wenn wir vom Tag i-1 zu mir gehen, lassen wir die Tage knallen, als der Preis des Lagers weniger war als oder gleich p (i) und dann stoßen Sie den Wert des Tages, den ich in den Stapel unterstütze.

Hier nehmen wir an, dass der Stapel durch Operationen durchgeführt wird, die O (1) nehmen, der unveränderliche Zeit ist. Der Algorithmus ist wie folgt:

Eingang: Eine Reihe P mit n Elementen und einem leeren Stapel N

Produktion: Eine Reihe S n solcher Elemente dass P bin [ich] die größte ganze Zahl k solch dass k

Lassen Sie einen Wert vom Stapel N knallen

3.3.2 sonst

Getan mit der wahren Bedingung

3.4 wenn Stapel N leerer ist

3.4.1 Initialisieren Sie h zu-1

3.5 sonst

3.5.1 Initialisieren Sie Stapel-Spitze zu h

3.6 Legen Sie den Wert von h - ich in S [ich]

3.7 Stoßen Sie den Wert von mir in N

4. Geben Sie Reihe S zurückJetzt, diesen Algorithmus für die Laufzeit analysierend, beobachten wir:Wir haben die Reihe S am Anfang initialisiert und es am Ende zurückgegeben. Das ist eine unveränderliche Zeitoperation, folglich nimmt O (n) Zeit

• Während Schleife innerhalb für die Schleife verschachtelt wird. Für die Schleife, deren Schalter ist, werde ich n Zeiten hingerichtet. Die Behauptungen, die nicht in der mehrmaligen Schleife, aber in für die Schleife sind, werden n Zeiten durchgeführt. Deshalb diese Behauptungen und das Erhöhen und die Bedingungsprüfung von nehme mir O (n) Zeit.
• Beobachten Sie jetzt das innere während Schleife während meiner Wiederholungen für die Schleife. Die mit einer wahren Bedingung getane Behauptung wird höchstens einmal getan, da sie einen Ausgang von der Schleife verursacht. Lassen Sie uns sagen, dass t (i) die Zahl der Zeitbehauptung Pop ist, wird ein Wert vom Stapel N durchgeführt. So wird es klar, dass, während nicht (Schobern N auf, leer oder mit der Verarbeitung getan ist), Maximum t (i) + 1mal geprüft wird.
• Die Laufzeit aller Operationen in hinzufügend, während Schleife, wir kommen:

:

• Ein Element, das einmal vom Stapel N knallen gelassen ist, wird zurück darin nie gestoßen. Deshalb,

:

Also, die Laufzeit aller Behauptungen in, während Schleife O ist

Die Laufzeit aller Schritte im Algorithmus wird durch das Hinzufügen der von allen diesen Schritten genommenen Zeit berechnet. Die Durchlaufzeit jedes Schritts ist O . Folglich ist die Laufzeit-Kompliziertheit dieses Algorithmus O .

Laufzeitspeichermanagement

Mehrere Programmiersprachen werden Stapel-orientiert, bedeutend, dass sie die meisten grundlegenden Operationen (das Hinzufügen von zwei Zahlen, der Druck eines Charakters) als Einnahme ihrer Argumente vom Stapel und des Stellens irgendwelcher Rückwerte zurück auf dem Stapel definieren. Zum Beispiel hat PostScript einen Rückstapel und einen Operand-Stapel, und hat auch einen Grafikzustandstapel und einen Wörterbuch-Stapel.

Hervor Gebrauch zwei Stapel, ein für den Argument-Übergang und ein für Unterprogramm-Rücksprungadressen. Der Gebrauch eines Rückstapels ist äußerst gewöhnlich, aber der etwas ungewöhnliche Gebrauch eines Argument-Stapels für eine menschlich-lesbare Programmiersprache ist der Grund Hervor wird eine Stapel-basierte Sprache genannt.

Viele virtuelle Maschinen werden auch, einschließlich der P-Codemaschine und Javas Virtuelle Maschine Stapel-orientiert.

Fast die ganze rufende Vereinbarung - Computerlaufzeitspeicherumgebungen — verwenden einen speziellen Stapel (der "Anruf-Stapel"), um Information über das Benennen des Verfahrens/Funktion und Nisten zu halten, um auf den Zusammenhang der genannten Funktion umzuschalten und zur Anrufer-Funktion wieder herzustellen, wenn das Benennen fertig ist. Die Funktionen folgen einem Laufzeitprotokoll zwischen Anrufer und callee, um Argumente und Rückwert auf dem Stapel zu sparen. Stapel sind eine wichtige Weise, verschachtelte oder rekursive Funktionsanrufe zu unterstützen. Dieser Typ des Stapels wird implizit durch den Bearbeiter verwendet, um ANRUF- und RÜCK-Behauptungen (oder ihre Entsprechungen) zu unterstützen, und wird direkt vom Programmierer nicht manipuliert.

Einige Programmiersprachen verwenden den Stapel, um Daten zu versorgen, der zu einem Verfahren lokal ist. Der Raum für lokale Datensachen wird vom Stapel zugeteilt, wenn ins Verfahren eingegangen wird, und deallocated ist, wenn das Verfahren abgeht. Die C Programmiersprache wird normalerweise auf diese Weise durchgeführt. Das Verwenden desselben Stapels für beide Daten und Verfahren-Anrufe hat wichtige Sicherheitsimplikationen (sieh unten), deren ein Programmierer bewusst sein muss, um zu vermeiden, ernste Sicherheitsprogrammfehler in ein Programm vorzustellen.

Sicherheit

Einige Rechenumgebungen verwenden Stapel auf Weisen, die sie verwundbar für Sicherheitsbrüche und Angriffe machen können. Programmierer, die in solchen Umgebungen arbeiten, müssen spezielle Sorge nehmen, um die Fallen dieser Durchführungen zu vermeiden.

Zum Beispiel verwenden einige Programmiersprachen einen allgemeinen Stapel, um beide Daten zu versorgen, die zu einem genannten Verfahren und der sich verbindenden Information lokal sind, die dem Verfahren erlaubt, zu seinem Anrufer zurückzukehren. Das bedeutet, dass das Programm Daten in und aus demselben Stapel bewegt, der kritische Rücksprungadressen für die Verfahren-Anrufe enthält. Wenn Daten zur falschen Position auf dem Stapel bewegt werden, oder ein übergroßer Datenartikel zu einer Stapel-Position bewegt wird, die nicht groß genug ist, um es zu enthalten, zurückzukehren, kann die Information für Verfahren-Anrufe verdorben werden, das Programm veranlassend, zu scheitern.

Böswillige Parteien können einen Stapel-Zersplittern-Angriff versuchen, der diesen Typ der Durchführung durch die Versorgung übergroßen Dateneingangs einem Programm ausnutzt, das die Länge des Eingangs nicht überprüft. Solch ein Programm kann die Daten vollständig zu einer Position auf dem Stapel kopieren, und auf diese Weise kann es die Rücksprungadressen für Verfahren ändern, die es genannt haben. Ein Angreifer kann experimentieren, um einen spezifischen Typ von Daten zu finden, die solch einem solchem Programm zur Verfügung gestellt werden können, dass die Rücksprungadresse des aktuellen Verfahrens neu gefasst wird, um zu einem Gebiet innerhalb des Stapels selbst hinzuweisen (und innerhalb der Daten, die vom Angreifer zur Verfügung gestellt sind), der der Reihe nach Instruktionen enthält, die unerlaubte Operationen ausführen.

Dieser Typ des Angriffs ist eine Schwankung auf dem Pufferüberschwemmungsangriff und ist eine äußerst häufige Quelle von Sicherheitsbrüchen in der Software hauptsächlich, weil einige der populärsten Programmiersprachen (wie C) einen geteilten Stapel für beide Daten und Verfahren-Anrufe verwenden, und die Länge von Datensachen nicht nachprüfen. Oft schreiben Programmierer Code nicht, um die Größe von Datensachen nachzuprüfen, entweder, und wenn ein übergroßer oder Datenartikel unter Normalgröße zum Stapel kopiert wird, kann ein Sicherheitsbruch vorkommen.

Siehe auch

• Liste von Datenstrukturen
• Warteschlange
• Doppelstapel
• Nennen Sie Stapel
• Stapel-basierte Speicherzuteilung
• Stapel-Maschine
• Stapel-Durchführung auf goodsoft.org.ua
• Ein Templated-Stapel-Datenstruktur-Beispiel an AssignmentExpert.com

Weiterführende Literatur

• Donald Knuth. Die Kunst der Computerprogrammierung, Bands 1: Grundsätzliche Algorithmen, die Dritte Ausgabe. Addison-Wesley, 1997. Internationale Standardbuchnummer 0-201-89683-4. Abschnitt 2.2.1: Stapel, Warteschlangen und Deques, Seiten 238-243.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest und Clifford Stein. Einführung in Algorithmen, die Zweite Ausgabe. MIT Presse und McGraw-Hügel, 2001. Internationale Standardbuchnummer 0-262-03293-7. Abschnitt 10.1: Stapel und Warteschlangen, Seiten 200-204.

Links

• Stapel-Maschinen - die neue Welle
• Das Springen der Stapel-Tiefe
• Libsafe - Schutz kritischer Elemente von Stapeln
• VBScript Durchführung des Stapels, der Warteschlange, deque, und des Rot-schwarzen Baums
• Stapel-Größe-Analyse für geUnterbrechungssteuerte Programme (322 Kilobytes)
• Zeigestöcke, um Vergegenwärtigungen aufzuschobern