Beste Antwort
In Informatik wird ein abstrakter Datentyp ( ADT ) ist ein mathematisches Modell für Datentypen , bei denen ein Datentyp durch sein Verhalten ( Semantik ) aus der Sicht eines Benutzer der Daten, insbesondere in Bezug auf mögliche Werte, mögliche Operationen an Daten dieses Typs und das Verhalten dieser Operationen. Dies steht im Gegensatz zu Datenstrukturen , die konkrete Darstellungen von Daten sind und die Sichtweise eines Implementierers und nicht eines Benutzers darstellen.
Aus Datenstruktur :
In Informatik wird ein Datenstruktur ist eine besondere Methode, um Daten in einem Computer so zu organisieren, dass sie effizient .
Datenstrukturen können einen oder mehrere bestimmte abstrakte Datentypen implementieren (ADT), mit denen der Betriebsvertrag und seine Komplexität
Eine Datenstruktur ist eine konkrete Implementierung des Vertrags, der von einem ADT bereitgestellt wird.
Das bedeutet:
1. ADT ist aus Anwendersicht eine abstrakte Darstellung
2. DS ist eine konkrete Darstellung, nicht aus Anwendersicht
In einfachen Worten:
1. Der Stapel ist ADT . Er gibt nur an, dass der Benutzer einen Push, Pop usw. verwenden soll.
2. Stack (wie andere ADTs wie Queue) wird mit DS wie Array oder Liste (verknüpfte Liste usw.)
Zusammenfassung:
Der Stapel ist kein DS, sondern ADT und wird mithilfe von implementiert andere DS.
Hoffe, das hat geholfen.
Viel Glück
Antwort
Stapel
Ein Stapel ist ein Container mit Objekten, die nach dem LIFO-Prinzip (Last-In First-Out) eingefügt und entfernt werden. In den Pushdown-Stapeln sind nur zwei Operationen zulässig: schieben das Element in den Stapel und pop das Objekt aus dem Stapel. Ein Stapel ist eine Datenstruktur mit eingeschränktem Zugriff. Elemente können nur oben zum Stapel hinzugefügt und daraus entfernt werden. push fügt ein Element oben im Stapel hinzu. pop entfernt das Element von oben . Eine hilfreiche Analogie besteht darin, an einen Stapel Bücher zu denken. Sie können nur das oberste Buch entfernen und oben ein neues Buch hinzufügen.
Ein Stapel ist eine rekursive -Datenstruktur. Hier ist eine strukturelle Definition eines Stapels:
Anwendungen
- Die einfachste Anwendung eines Stapels besteht darin, ein Wort umzukehren. Sie verschieben ein bestimmtes Wort – Stapel für Buchstabe – in den Stapel und fügen dann Buchstaben aus dem Stapel hinzu.
- Eine andere Anwendung ist ein „Rückgängig“ -Mechanismus in Texteditoren. Dieser Vorgang wird ausgeführt, indem alle Textänderungen in einem Stapel gespeichert werden. Backtracking . Dies ist ein Prozess, wenn Sie auf das neueste Datenelement in einer Reihe von Elementen zugreifen müssen. Denken Sie an ein Labyrinth oder ein Labyrinth – wie finden Sie einen Weg von einem Eingang zu einem Ausgang? Sobald Sie eine Sackgasse erreicht haben, müssen Sie zurückgehen. Aber zurück zu wo? zum vorherigen Auswahlpunkt. Daher speichern Sie an jedem Auswahlpunkt alle möglichen Auswahlmöglichkeiten auf einem Stapel. Backtracking bedeutet dann einfach, eine nächste Auswahl aus dem Stapel zu entfernen.
- Sprachverarbeitung: Der Speicherplatz für Parameter und lokale Variablen wird intern mithilfe eines Stapels erstellt. Die Syntaxprüfung des Compilers für übereinstimmende geschweifte Klammern wird mithilfe von stack.support implementiert für die Rekursion
Implementierung
In der Standardbibliothek von Klassen ist der Datentypstapel ein Adapter -Klasse, was bedeutet, dass ein Stapel auf anderen Datenstrukturen aufgebaut ist. Die zugrunde liegende Struktur für einen Stapel kann ein Array, ein Vektor, eine ArrayList, a sein verknüpfte Liste oder eine andere Sammlung. Unabhängig vom Typ der zugrunde liegenden Datenstruktur muss ein Stack dieselbe Funktionalität implementieren.Dies wird durch die Bereitstellung einer eindeutigen Schnittstelle erreicht:
public interface StackInterface
{
public void push(AnyType e);
public AnyType pop();
public AnyType peek();
public boolean isEmpty();
}
Die Das folgende Bild zeigt die Idee der Implementierung nach Zusammensetzung .
Eine weitere Implementierungsanforderung (zusätzlich zu der obigen Schnittstelle) besteht darin, dass alle Stapeloperationen in
konstanter Zeit O (1) ausgeführt werden müssen
. Konstante Zeit bedeutet, dass es eine Konstante k gibt, so dass eine Operation unabhängig von der Stapelgröße k Nanosekunden Rechenzeit benötigt.
Array-basierte Implementierung
In einer Array-basierten Implementierung werden die folgenden Felder verwaltet: ein Array A mit einer Standardgröße (≥ 1) ), die Variable top , die sich auf das oberste Element im Stapel bezieht, und die Kapazität bezieht sich auf die Arraygröße. Die Variable top ändert sich von -1 zu capacity - 1. Wir sagen, dass ein Stapel leer ist, wenn top = -1, und der Stapel voll ist, wenn top = capacity-1.
In einem festen Bei der Stapelabstraktion bleibt die Kapazität unverändert. Wenn also top Kapazität erreicht, wird der Stapel Objekt löst eine Ausnahme aus.
In einer dynamischen Stapelabstraktion, wenn top Kapazität
Implementierung auf der Basis einer verknüpften Liste
Auf der Basis einer verknüpften Liste Die Implementierung bietet die beste (aus Sicht der Effizienz) dynamische Stack-Implementierung.
Quelle – Stapel und Warteschlangen