Was ist eine Stack-Datenstruktur?
Schauen wir uns zunächst einmal kurz an, was eine Stack-Datenstruktur ist. Es ist eine lineare Datenstruktur, die auf dem Last-in-First-out-Prinzip (LIFO) basiert. Es ist eine Art Anti-Warteschlange. Stell dir ein Kartenspiel oder einen Stapel Bücher in einer Kiste vor. Das Buch, das du zuerst auf den Stapel gelegt hast, liegt unten, und das erste Buch, das wir aus der Kiste nehmen, ist das Buch, das oben lag – also das Buch, das zuletzt in die Kiste gelegt wurde. Hier ist ein Gif-Bild, das dieses Prinzip veranschaulicht.
Wofür wird die Stack-Datenstruktur verwendet?
Eine der wichtigsten Anwendungen des Stacks ist die Organisation von Unterprogrammaufrufen. Die Aufrufstelle auf dem Stack speichert die Rücksprungadresse des Unterprogramms nach dessen Beendigung (und gegebenenfalls die übergebenen Parameter). Bei jedem verschachtelten (auch rekursiven) Aufruf von Unterprogrammen werden dem Stack neue Rücksprungadressen hinzugefügt. Bei jedem Rücksprung aus dem Unterprogramm (return) wird die Rücksprungadresse vom Stapel entfernt und die Kontrolle dorthin übertragen. Diese Anwendung ist so wichtig für die Programmierung, dass der Aufrufstapel bei den meisten Prozessoren in Hardware im Befehlssatz implementiert ist. In anderen Fällen muss der Stack jedoch auf allgemeineren Datenstrukturen modelliert werden.Java Stack-Klasse im Collection-Framework
In Java ist die Stack-Klasse eine Klasse aus dem Collection-Framework, die das List-Interface implementiert und die Vector-Klasse erweitert. Sie implementiert auch die Interfaces Collection, Iterable, Cloneable und Serializable. Wie du wahrscheinlich schon vermutet hast, repräsentiert diese Klasse den LIFO-Stack von Objekten. Hier ist der Aufruf des Konstruktors der Klasse Stack, d. h. die Erstellung eines Objekts dieser Klasse.
Stack<E> stack = new Stack<E>();
Dabei ist E der Typ des Objekts.
Java Stack-Methoden
Diese Klasse hat nur einen Standardkonstruktor und alle Methoden der Vector-Klasse. Außerdem hat Stack seine eigenen 5 Methoden:boolean empty(): Die Methode prüft, ob der Stapel leer ist oder nicht. Gibt true zurück, wenn der Stapel leer ist, und false, wenn nicht.
Object peek(): Die Methode gibt das Element zurück, das sich oben auf dem Stapel befindet.
Objekt pop(): Die Methode gibt das Element zurück, das sich oben auf dem Stapel befindet, und entfernt es.
Object push(Object element): Die Methode fügt das angegebene Element oben auf dem Stapel hinzu.
int search(Object element): Die Methode sucht im Stapel nach dem angegebenen Element. Wenn das gesuchte Element gefunden wird, wird sein „Abstand“ von oben (Seriennummer) zurückgegeben. Wenn das Element nicht gefunden wird, wird -1 zurückgegeben.
Beispiel eines Stack-Codes
Lass uns ein Programmbeispiel erstellen, das so funktioniert wie das gif-Bild oben. Wir legen drei „Kugeln“, orange, lila und grün, auf den Stapel. Lass uns den Stapel auf Leere überprüfen. Dann entnehmen wir Kugeln aus dem Stapel, bis der Stapel leer ist.
import java.util.Stack;
public class myStackTest2 {
public static void main(String[] args)
{
Stack myStack= new Stack<>();
System.out.println("Is my stack empty? " + myStack.empty());
// pushing elements into stack
myStack.push("Orange Ball");
myStack.push("Violet Ball");
myStack.push("Green Ball");
//prints elements of the stack
System.out.println("Elements in Stack: " + myStack);
System.out.println("Is my stack empty? " + myStack.empty());
while (!myStack.isEmpty()) {
myStack.pop();
System.out.println("Elements in Stack: " + myStack);
System.out.println("Is my stack empty? " + myStack.empty());
}
}
}
Hier ist die Ausgabe dieses Programms:
import java.util.Stack;
public class myStackTest2 {
public static void main(String[] args)
{
Stack myStack= new Stack<>();
System.out.println("Is my stack empty? " + myStack.empty());
// pushing elements into stack
myStack.add("Orange Ball");
myStack.add("Violet Ball");
myStack.add("Green Ball");
//prints elements of the stack
System.out.println("Elements in Stack: " + myStack);
System.out.println("Is my stack empty? " + myStack.empty());
while (!myStack.isEmpty()) {
myStack.pop();
System.out.println("Elements in Stack: " + myStack);
System.out.println("Is my stack empty? " + myStack.empty());
}
}
}
Das Ergebnis des Programms wird natürlich genau dasselbe sein.
Was ist mit deiner eigenen Stack-Implementierung?
Du kannst deine eigene Stack-Datenstruktur in Java mit Arrays oder verketteten Listen erstellen. Im ersten Fall wird ein kontinuierliches Array von Zellen zugewiesen, um Werte im Speicher zu speichern, die nach Bedarf verwendet werden. Im zweiten Fall wird für jedes Element des Stapels ein Speicherblock angelegt, der ausreicht, um den Wert und die Verweise auf das vorherige und das nächste Element des Stapels zu speichern. Die Array-basierte Implementierung ist einfacher, effizienter und speichereffizienter, aber sie erfordert eine vorherige Kenntnis der Stack-Größenbegrenzung und kann zu schwer zu findenden Fehlern führen. Die listenbasierte Implementierung ist robuster, aber weniger effizient. Lass uns eine einfache Array-basierte Implementierung des Stacks erstellen. Sie wird Funktionen enthalten.push – eine Methode, die dafür sorgt, dass ein Element hinzugefügt wird (an der obersten Position)
pop – eine Methode, die das Entfernen eines Elements (von der obersten Position) ermöglicht
readTop – eine Methode, die den Wert des Elements zurückgibt, das sich an der obersten Position befindet
sEmpty – eine Methode, die den Stapel darauf überprüft, ob er leer ist
isFull – eine Methode, die überprüft, ob unser Array, in dem wir den Stapel speichern, nicht voll ist
import java.util.Arrays;
public class MyStack {
private int maxSize;
private String[] stackArray;
private int top;
public MyStack(int size) {
this.maxSize = size;
stackArray = new String[maxSize];
top = -1;
}
public String push (String element) {
return stackArray[++top] = element;
}
public String pop (String element) {
if (isEmpty())
{
System.out.println("Underflow\nProgram Terminated");
System.exit(-1);
}
System.out.println("Removing " + readTop());
return stackArray[top--];
}
public String readTop() {
return stackArray[top];
}
public boolean isEmpty() {
return (top == -1);
}
public boolean isFull() {
return (top == maxSize - 1);
}
public void printStack(){
System.out.println(Arrays.toString(stackArray));
}
}
Jetzt wollen wir ein Beispiel mit drei Kugeln auf der Grundlage unseres Stapels implementieren:
public class myStackTest {
public static void main(String[] args) {
MyStack myStack = new MyStack(3);
System.out.println("Is my stack empty? " + myStack.isEmpty());
myStack.push("Orange Ball");
myStack.push("Violet Ball");
myStack.push("Green Ball");
myStack.printStack();
System.out.println("Is my stack empty? " + myStack.isEmpty());
while (!myStack.isEmpty()) {
myStack.pop(myStack.readTop());
System.out.println("Is my stack empty? " + myStack.isEmpty());
}
}
}
Die Ausgabe ist hier:

GO TO FULL VERSION