Java-stack

Stack in Java betekent meestal de klasse van Collection Framework die de List-interface implementeert. Het werkt volgens het principe van de Stack-gegevensstructuur, die wordt gebruikt om een ​​van de soorten geheugen te organiseren. Het zou ook het deel van het geheugen kunnen zijn om gegevens te bewaren. In dit artikel zullen we allereerst aandacht besteden aan de klasse Stack , de methoden ervan bekijken en voorbeelden geven. Maar we zullen het ook hebben over zo'n datastructuur als Stack en waar deze voor wordt gebruikt.

Wat is Stack Data Structure

Laten we eerst eens kijken wat een stapelgegevensstructuur is. Het is een lineaire gegevensstructuur die is gebaseerd op het Last-in-First-out (LIFO)-principe. Het is een soort anti-wachtrij. Stel je een kaartspel of een stapel boeken in een doos voor. Het boek dat je als eerste in de stapel legt, ligt onderaan, en het eerste dat we uit de doos halen, is het boek dat bovenaan lag - dat wil zeggen, het boek dat als laatste in de doos kwam. Hier is een gif-afbeelding om dit principe te demonstreren. Wat is hier aan de hand? We hebben een fles waarin slechts één bal tegelijk kan raken. De eerste in de kolf is een oranje bal, dan paars en uiteindelijk groen (mijn excuses aan degenen die de meer accurate namen van deze kleuren kennen). Om echter een oranje bal uit onze kolfstapel te halen, moeten we eerst de bal eruit halen die daar als laatste aankwam (de groene), daarna de bal die de voorlaatste was (maar op het moment van extractie is het de laatste een). De stapelgegevensstructuur in Java of elders in de programmering heeft de twee belangrijkste bewerkingen, push en pop . De push-bewerking voegt een element in de stapel en de pop-bewerking verwijdert een element van de bovenkant van de stapel.

Waar is de Stack-gegevensstructuur voor?

Een van de belangrijkste toepassingen van de stapel is het organiseren van subroutineoproepen. Het oproeppunt op de stapel slaat het retouradres van de subroutine op nadat deze is beëindigd (en mogelijk de doorgegeven parameters). Bij elke geneste (inclusief recursieve) aanroep van subroutines worden nieuwe retouradressen aan de stapel toegevoegd. Bij elke retourbewerking van de subroutine (retour) wordt het retouradres van de stapel verwijderd en wordt de besturing ernaar overgedragen. Deze toepassing is zo belangrijk voor het programmeren dat in de meeste processors de retourstack in hardware is geïmplementeerd in de instructieset. In andere gevallen moet de stapel echter worden gemodelleerd op meer algemene gegevensstructuren.

Java Stack Class of Collection Framework

In Java is Stack Class een klasse uit het Collection-framework die de List-interface implementeert en de Vector-klasse uitbreidt. Het implementeert ook interfaces Collection, Iterable, Cloneable, Serializable. Zoals je waarschijnlijk al geraden hebt, vertegenwoordigt deze klasse de LIFO-stapel objecten. Hier is de oproep aan de constructor van de Stack- klasse, dat wil zeggen de creatie van een object van deze klasse.

Stack<E> stack = new Stack<E>();

Waar E het type object is.

Java Stack-methoden

Deze klasse heeft slechts één standaardconstructor en alle methoden van de klasse Vector . Bovendien heeft Stack zijn eigen 5 methoden:

• boolean empty() de methode controleert of de stapel leeg is of niet. Retourneert true als de stapel leeg is, false als dat niet het geval is.

• Object peek() de methode retourneert het element dat bovenaan de stapel staat.

• Object pop() de methode retourneert het element dat bovenaan de stapel staat en verwijdert het.

• Object push(Object element) de methode voegt het opgegeven element toe aan de bovenkant van de stapel.

• int search(Object element) de methode zoekt in de stapel naar het gespecificeerde element. Als het vereiste element is gevonden, wordt de "afstand" vanaf de bovenkant (serienummer) geretourneerd. Als het element niet wordt gevonden, wordt -1 geretourneerd.

Stapelcode voorbeeld

Laten we een programmavoorbeeld maken dat werkt zoals de gif-afbeelding hierboven. We leggen drie 'ballen', oranje, paars en groen, op de stapel. Laten we de stapel controleren op leegte. Vervolgens halen we ballen uit de stapel totdat de stapel leeg is.

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 is de uitvoer van dit programma: Omdat Stack is geërfd van Vector Class en de List- interface implementeert , heeft Stack , naast de klassieke push- en pop-bewerkingen voor deze gegevensstructuur voor het toevoegen en extraheren van elementen, ook standaard voor lijststructuur add() en remove()- bewerkingen. In ons voorbeeld kan het toevoegen van elementen op dezelfde manier worden geïmplementeerd met behulp van de methode add() . U kunt echter alleen extraheren met remove() als er een element is opgegeven, wat geen zin heeft voor de stapelgegevensstructuur.

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());
           }
       }
   }

Het resultaat van het programmawerk zal natuurlijk precies hetzelfde zijn.

Hoe zit het met uw eigen Stack-implementatie?

U kunt uw eigen stapelgegevensstructuur in Java maken met behulp van arrays of gekoppelde lijstklassen. In het eerste geval wordt een continue reeks cellen toegewezen om waarden in het geheugen op te slaan, die naar behoefte worden gebruikt. In de tweede wordt voor elk element van de stapel een geheugenblok geordend, voldoende om de waarde en verwijzingen naar de vorige en volgende elementen van de stapel op te slaan. De op arrays gebaseerde implementatie is eenvoudiger, efficiënter en geheugenefficiënter, maar vereist voorkennis van de limiet voor de stapelgrootte en kan leiden tot moeilijk te vinden bugs. De op lijsten gebaseerde implementatie is robuuster maar minder efficiënt. Laten we een eenvoudige array-gebaseerde implementatie van de stapel maken. Het zal functies bevatten.

• push — een methode die zorgt voor de toevoeging van een element (in de bovenste positie)

• pop — een methode die zorgt voor het verwijderen van een element (vanaf de bovenste positie)

• readTop — een methode die de waarde retourneert van het element dat zich in positie bovenaan bevindt

• sEmpty — een methode die de stapel controleert op leegheid

• isFull — een methode die controleert of onze array waarin we de stapel opslaan niet vol is

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));
   }
}

Laten we nu een voorbeeld implementeren met drie ballen op basis van onze stapel:

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());
       }
   }

}

De uitvoer is hier: Als je goed kijkt, bevat de bovenste variabele eigenlijk de index van het laatste element en blijft de verwijzing naar het object in de array. Deze implementatie behoeft dus enige verbetering. Denk na over de gemakkelijkste manier om dit te doen.

Moeten we Java Stack gebruiken?

In feite is de Java Stack , net als zijn Vector- ouder, een verouderde klasse. In plaats daarvan wordt meestal de klasse ArrayList gebruikt. ArrayList wordt niet gesynchroniseerd terwijl Vector wordt gesynchroniseerd. Dat betekent dat met Vector slechts één thread tegelijk toegang heeft tot de code, terwijl ArrayList met meerdere threads kan werken. ArrayList is ook efficiënter en sneller. U zult deze klasse dus hoogstwaarschijnlijk alleen in verouderde code zien. Maar de Stack- gegevensstructuur wordt heel vaak gebruikt bij het programmeren.