Java Stack

Mit Stack ist in Java normalerweise die Klasse aus dem Collection Framework gemeint, die das List-Interface implementiert. Es funktioniert nach dem Prinzip der Stack-Datenstruktur, die zur Organisation eines der Speichertypen verwendet wird. In diesem Artikel werden wir uns zunächst mit der Klasse Stack beschäftigen, ihre Methoden betrachten und Beispiele geben. Wir werden aber auch über eine Datenstruktur wie Stack sprechen und wofür sie verwendet wird.

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. Was passiert hier? Wir haben einen Behälter, in den immer nur eine Kugel passt. Die erste Kugel im Behälter ist orangefarben, dann lila und schließlich grün (ich entschuldige mich bei denen, die die genaueren Namen dieser Farben kennen). Um jedoch eine orangefarbene Kugel aus unserem Behälter zu entnehmen, müssen wir zuerst die Kugel entnehmen, die zuletzt dorthin hineingelegt wurde (die grüne Kugel), dann die vorletzte Kugel (zum Zeitpunkt der Entnahme ist sie jedoch die letzte). Die Stack-Datenstruktur in Java oder anderswo in der Programmierung hat die zwei wichtigsten Operationen Push und Pop. Die Push-Operation fügt ein Element in den Stapel ein und die Pop-Operation entfernt ein Element von der Spitze des Stapels.

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: Da Stack von der Klasse Vector geerbt wurde und das List-Interface implementiert, verfügt Stack zusätzlich zu den klassischen Push- und Pop-Operationen für diese Datenstruktur zum Hinzufügen und Entnehmen von Elementen auch über die Standardoperationen add() und remove() für Listenstrukturen. In unserem Beispiel kann das Hinzufügen von Elementen auf die gleiche Weise mit der Methode add() umgesetzt werden. Allerdings kannst du mit remove() nur dann etwas entnehmen, wenn ein Element angegeben ist, was für die Stack-Datenstruktur keinen Sinn macht.

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: Wenn du genau hinsiehst, enthält die oberste Variable tatsächlich den Index des letzten Elements, und der Verweis auf das Objekt bleibt im Array. Diese Umsetzung muss also noch verbessert werden. Überlege dir, wie du das am einfachsten machen kannst.

Sollten wir Java Stack verwenden?

Tatsächlich ist der Java Stack, wie sein Vector-Elternteil, eine veraltete Klasse. Stattdessen wird normalerweise die Klasse ArrayList verwendet. ArrayList ist nicht synchronisiert, während Vector synchronisiert ist. Das bedeutet, dass bei Vector nur ein Thread zur gleichen Zeit auf den Code zugreifen kann, während ArrayList mit mehreren Threads arbeiten kann. Außerdem ist ArrayList effizienter und schneller. Du wirst diese Klasse also höchstwahrscheinlich nur in altem Code sehen. Aber die Stack-Datenstruktur wird in der Programmierung sehr oft verwendet.