Java stack

Stack i Java betyr vanligvis klassen fra Collection Framework som implementerer List-grensesnittet. Den fungerer etter prinsippet om stakkdatastrukturen, som brukes til å organisere en av minnetypene. Det kan også være en del av minnet å beholde data. I denne artikkelen vil vi først og fremst ta hensyn til Stack- klassen , vurdere metodene og gi eksempler. Men vi skal også snakke om en slik datastruktur som Stack og hva den brukes til.

Hva er Stack Data Structure

Først av alt, la oss ta en rask titt på hva en stabeldatastruktur er. Det er en lineær datastruktur som er basert på Last-in-First-out (LIFO)-prinsippet. Det er en slags anti-kø. Se for deg en kortstokk eller en bunke bøker i en boks. Boken som du legger i stabelen først er nederst, og den første vi skal ta ut av esken er boken som var øverst - altså den som kom sist inn i esken. Her er et gif-bilde for å demonstrere dette prinsippet. Hva foregår her? Vi har en kolbe der bare én ball kan treffe om gangen. Den første i kolben er en oransje kule, deretter lilla og til slutt grønn (jeg beklager til de som kjenner de mer nøyaktige navnene på disse fargene). Men for å trekke ut en oransje kule fra kolbebunken vår, må vi først trekke ut ballen som kom sist (den grønne), deretter den som var den nest siste (men ved utvinningstidspunktet er det den siste) en). Stabeldatastrukturen i Java eller andre steder i programmering har de to viktigste operasjonene, push og pop . Skyveoperasjonen setter et element inn i stabelen og pop-operasjonen fjerner et element fra toppen av stabelen.

Hva er stackdatastrukturen for?

En av de viktigste bruksområdene til stabelen er å organisere subrutineanrop. Callpointet på stabelen lagrer returadressen fra subrutinen etter at den avsluttes (og muligens parametrene passerte). Med hvert nestede (inkludert rekursive) anrop av subrutiner, blir nye returadresser lagt til stabelen. Med hver returoperasjon fra subrutinen (retur), fjernes returadressen fra stabelen og kontrollen overføres til den. Denne applikasjonen er så viktig for programmering at i de fleste prosessorer er returstakken implementert i maskinvare i instruksjonssettet. I andre tilfeller må imidlertid stabelen modelleres etter mer generelle datastrukturer.

Java Stack Class of Collection Framework

I Java Stack Class er en klasse fra samlingsrammeverket som implementerer List-grensesnitt og utvider Vector-klassen. Den implementerer også grensesnittene Collection, Iterable, Cloneable, Serializable. Som du sikkert allerede har gjettet representerer denne klassen LIFO-stabelen med objekter. Her er oppfordringen til konstruktøren av Stack -klassen, det vil si opprettelsen av et objekt av denne klassen.

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

Hvor E er typen objekt.

Java stackmetoder

Denne klassen har bare én standardkonstruktør og alle metodene til Vector- klassen. I tillegg har Stack sine egne 5 metoder:

• boolean empty() metoden sjekker om stabelen er tom eller ikke. Returnerer sant hvis stabelen er tom, usann hvis ikke.

• Object peek() metoden returnerer elementet som er på toppen av stabelen.

• Objekt pop() metoden returnerer elementet som er på toppen av stabelen og fjerner det.

• Object push(Object element) metoden legger til det spesifiserte elementet til toppen av stabelen.

• int søk(Objektelement) metoden søker i stabelen etter det angitte elementet. Hvis det nødvendige elementet blir funnet, returneres dets "avstand" fra toppen (serienummeret). Hvis elementet ikke blir funnet, returneres -1.

Eksempel på stakkkode

La oss lage et programeksempel som fungerer som gif-bildet ovenfor. Vi legger tre "baller", oransje, lilla og grønne, på stabelen. La oss sjekke stabelen for tomhet. Deretter trekker vi ut baller fra stabelen til stabelen 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 resultatet av dette programmet: Siden Stack er arvet fra Vector Class og implementerer List- grensesnittet, har Stack , i tillegg til de klassiske push- og pop-operasjonene for denne datastrukturen for å legge til og trekke ut elementer, også standard for listestruktur add() og remove() operasjoner. I vårt eksempel kan det å legge til elementer implementeres på samme måte ved å bruke add() -metoden. Du kan imidlertid trekke ut ved å bruke remove() bare med et spesifisert element, noe som ikke gir mening for stabeldatastrukturen.

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 av programarbeidet blir selvsagt nøyaktig det samme.

Hva med din egen Stack-implementering?

Du kan lage din egen stackdatastruktur i Java ved å bruke arrays eller koblede listeklasser. I det første tilfellet er en kontinuerlig rekke celler tildelt for å lagre verdier i minnet, som brukes etter behov. I det andre, for hvert element i stabelen, blir en minneblokk bestilt, tilstrekkelig til å lagre verdien og referanser til de forrige og neste elementene i stabelen. Den array-baserte implementeringen er enklere, mer effektiv og mer minneeffektiv, men den krever forkunnskaper om stabelstørrelsesgrensen og kan føre til vanskelige å finne feil. Den listebaserte implementeringen er mer robust, men mindre effektiv. La oss lage en enkel array-basert implementering av stabelen. Det vil inneholde funksjoner.

• push — en metode som vil sikre tilsetning av et element (i toppposisjonen)

• pop - en metode som vil gi fjerning av et element (fra toppposisjonen)

• readTop - en metode som vil returnere verdien til elementet som er i posisjon øverst

• sEmpty - en metode som vil sjekke stabelen for tomhet

• isFull — en metode som vil sjekke om matrisen vår som vi lagrer stabelen i, ikke er full

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

La oss nå implementere et eksempel med tre baller basert på stabelen vår:

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

}

Utgangen er her: Hvis du ser nøye etter, inneholder den øverste variabelen faktisk indeksen til det siste elementet, og referansen til objektet forblir i matrisen. Så denne implementeringen trenger en viss forbedring. Tenk på den enkleste måten å gjøre dette på.

Bør vi bruke Java Stack?

Faktisk er Java Stack , i likhet med Vector- forelderen, en eldre klasse. I stedet brukes vanligvis ArrayList- klassen. ArrayList er ikke synkronisert mens Vector er synkronisert. Det betyr at med Vector kun én tråd om gangen kan få tilgang til koden, mens ArrayList kan fungere med flere tråder. ArrayList er også mer effektiv og raskere. Så du vil mest sannsynlig bare se denne klassen i eldre kode. Men Stack- datastrukturen brukes veldig ofte i programmering.