Java stak

Stack i Java betyder normalt klassen fra Collection Framework, der implementerer List-grænsefladen. Det fungerer efter princippet om stakdatastrukturen, som bruges til at organisere en af ​​hukommelsestyperne. Det kunne også være en del af hukommelsen at opbevare data. I denne artikel vil vi først og fremmest være opmærksomme på Stack- klassen , overveje dens metoder og give eksempler. Men vi vil også tale om sådan en datastruktur som Stack , og hvad den bruges til.

Hvad er stakdatastruktur

Først og fremmest, lad os tage et hurtigt kig på, hvad en stakdatastruktur er. Det er en lineær datastruktur, der er baseret på Last-in-First-out (LIFO) princippet. Det er en slags anti-kø. Forestil dig et sæt kort eller en stak bøger i en æske. Den bog, du lægger i stakken først, er nederst, og den første vi tager ud af kassen er den bog, der var øverst - altså den, der kom sidst i kassen. Her er et gif-billede for at demonstrere dette princip. Hvad sker der her? Vi har en kolbe, hvori kun én bold kan ramme ad gangen. Den første i kolben er en orange kugle, derefter lilla og til sidst grøn (jeg undskylder til dem, der kender de mere nøjagtige navne på disse farver). Men for at udtrække en orange bold fra vores kolbestak, skal vi først trække den bold, der kom der sidst (den grønne), derefter den, der var den næstsidste (men på udtrækningstidspunktet er det den sidste). en). Stakdatastrukturen i Java eller andre steder i programmering har de to vigtigste operationer, push og pop . Trykoperationen indsætter et element i stakken, og pop-operationen fjerner et element fra toppen af ​​stakken.

Hvad er stakdatastrukturen til?

En af de vigtigste anvendelser af stakken er at organisere subrutineopkald. Opkaldspunktet på stakken gemmer returadressen fra subrutinen, efter at den er afsluttet (og muligvis parametrene passeret). Med hvert indlejret (inklusive rekursivt) kald af subrutiner tilføjes nye returadresser til stakken. Ved hver returoperation fra subrutinen (return) fjernes returadressen fra stakken, og kontrollen overføres til den. Denne applikation er så vigtig for programmering, at returstakken i de fleste processorer er implementeret i hardware i instruktionssættet. I andre tilfælde skal stakken dog modelleres efter mere generelle datastrukturer.

Java Stack Class of Collection Framework

I Java Stack Class er en klasse fra Collection frameworket, der implementerer List interface og udvider Vector klasse. Det implementerer også grænseflader Collection, Iterable, Cloneable, Serializable. Som du sikkert allerede har gættet repræsenterer denne klasse LIFO-stakken af ​​objekter. Her er opfordringen til konstruktøren af ​​Stack -klassen, det vil sige oprettelsen af ​​et objekt af denne klasse.

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

Hvor E er typen af ​​objekt.

Java Stack metoder

Denne klasse har kun én standardkonstruktør og alle Vector- klassens metoder. Plus, Stack har sine egne 5 metoder:

• boolean empty() metoden kontrollerer om stakken er tom eller ej. Returnerer sand , hvis stakken er tom, falsk , hvis ikke.

• Object peek() metoden returnerer det element, der er øverst i stakken.

• Object pop() metoden returnerer det element, der er øverst i stakken, og fjerner det.

• Object push(Object element) metoden tilføjer det angivne element til toppen af ​​stakken.

• int search(Object element) metoden søger i stakken efter det angivne element. Hvis det nødvendige element findes, returneres dets "afstand" fra toppen (serienummer). Hvis elementet ikke findes, returneres -1.

Eksempel på stak kode

Lad os lave et programeksempel, der virker, såsom gif-billedet ovenfor. Vi lægger tre "bolde", orange, lilla og grønne, på stakken. Lad os tjekke stakken for tomhed. Derefter trækker vi bolde ud af stakken, indtil stakken er tom.

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

Her er output fra dette program: Da Stack er nedarvet fra Vector Class og implementerer List- grænsefladen, har Stack , ud over de klassiske push- og pop-operationer for denne datastruktur til tilføjelse og udtrækning af elementer, også standard for liststruktur add() og remove() operationer. I vores eksempel kan tilføjelse af elementer implementeres på samme måde ved hjælp af add() metoden. Du kan dog kun udtrække ved hjælp af remove() med et specificeret element, hvilket ikke giver nogen mening for stakdatastrukturen.

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

Resultatet af programarbejdet bliver naturligvis helt det samme.

Hvad med din egen Stack-implementering?

Du kan oprette din egen stakdatastruktur i Java ved hjælp af arrays eller sammenkædede listeklasser. I det første tilfælde er et kontinuerligt array af celler allokeret til at gemme værdier i hukommelsen, som bruges efter behov. I den anden, for hvert element i stakken, er der bestilt en hukommelsesblok, tilstrækkelig til at lagre værdien og referencer til de forrige og næste elementer i stakken. Den array-baserede implementering er enklere, mere effektiv og mere hukommelseseffektiv, men den kræver en forudgående viden om stakstørrelsesgrænsen og kan føre til svære at finde fejl. Den listebaserede implementering er mere robust, men mindre effektiv. Lad os lave en simpel array-baseret implementering af stakken. Det vil indeholde funktioner.

• push — en metode, der sikrer tilføjelsen af ​​et element (i den øverste position)

• pop — en metode, der vil sørge for fjernelse af et element (fra den øverste position)

• readTop — en metode, der returnerer værdien af ​​det element, der er i topposition

• sEmpty — en metode, der kontrollerer stakken for tomhed

• isFull — en metode, der vil kontrollere, om vores array, som vi gemmer stakken i, ikke er fuld

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

Lad os nu implementere et eksempel med tre bolde baseret på vores stak:

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

}

Output er her: Hvis du ser godt efter, indeholder den øverste variabel faktisk indekset for det sidste element, og referencen til objektet forbliver i arrayet. Så denne implementering skal forbedres. Tænk på den nemmeste måde at gøre dette på.

Skal vi bruge Java Stack?

Faktisk er Java Stack , ligesom dets Vector- forælder, en ældre klasse. I stedet bruges klassen ArrayList normalt. ArrayList er ikke synkroniseret, mens Vector er synkroniseret. Det betyder, at med Vector kun én tråd ad gangen kan få adgang til koden, mens ArrayList kan arbejde med flere tråde. ArrayList er også mere effektiv og hurtigere. Så du vil højst sandsynligt kun se denne klasse i ældre kode. Men stakdatastrukturen bruges meget ofte i programmering.