Java Stack 101: Dykning i stakklassen

Stakken i Java er en datastruktur, ligesom en kø, et array, en sammenkædet liste eller et træ . Hvor den adskiller sig fra de andre er, at Java Stack er baseret på Last In, First Out (LIFO) princippet. Hvad dette betyder er, at når du bruger de to kommandoer til at tilføje og fjerne et element fra stakken, vil den første, du fjerner, altid være den sidste, du tilføjede. Lad os se nærmere på Java Stack Class

Udforskning af Java Stack Class

Java Stack Class er en udvidelse af Vector- klassen, som selv udvider List- klassen. Fordi vektorer er mutable og kan vokse og skrumpe med kravene fra elementerne indeni, kan Stack s også ændre størrelse efter behov. Udvidelsen af ​​Vector- klassen tilføjer fem operationer, der transformerer en Vector til en stak . Disse fem operationer er:

• .push(E item) – placerer et element på toppen af ​​stakken
• .pop() – fjerner elementet øverst i stakken og returnerer det som værdien af ​​funktionen
• .peek() – ser på elementet øverst i stakken uden at fjerne det
• .empty() – boolesk funktion til at teste, om stakken er tom eller ej. Returnerer 0 eller 1.
• .search(Object o) – Søger efter o og returnerer dens position. Værdien er 1-baseret, ikke 0-baseret

Stack arver også alle de metoder, der er en del af Vector , inklusive, men ikke begrænset til, toString() , contains() , indexOf() og lastElement() .

Eksempel på kodning af en Java-stak

Nu hvor vi kender funktionerne for stakken , lad os kode et java-stakeksempel. Stack s er meget nyttige til at håndtere data, der skal gemmes midlertidigt og hentes hurtigt. Fordi stakken er LIFO, er den usædvanlig nyttig til knudegennemgang, når man udforsker en trædatastruktur. Før vi kommer ind på alt det, lad os skabe en grundlæggende stak. Koden til at implementere en stak er som følger:

import java.util.*;

class Main {
  public static void main(String[] args) {
    Stack<Integer> stackExample = new Stack<Integer>();

Det er alt, du skal gøre for at oprette en tom stak . Du kan også blot erklære det uden at angive en datatype ved at bruge:

Stack example = new Stack();

Husk, at fordi stakke kan ændres, når vi skubber elementer ind på stakken, justeres den automatisk i størrelse. Lad os nu se på, hvordan du bruger Stack- funktionerne.

Java Stack Implementering

Lad os se på, hvordan man bruger de fem metoder, vi kort udforskede tidligere. Java-stackimplementering er let at huske, hvis du tænker på det som en stak plader. Du lægger plader på stakken, men for at få en tallerken, går du ikke til bunden, du får en fra toppen. Den sidste du tager på er den første du tager af. Udvider vores tidligere eksempel med stackExample , funktionerne er som følger:

Skubbe

// pushing integers onto the Stack
    stackExample.push(5);
    stackExample.push(10);

På dette tidspunkt vil vi vise de andre funktioner, som om vi har skubbet disse to heltal ind på Java-stakeksemplet hver gang.

Pop

//popping integers off of the Stack
System.out.println(stackExample.pop());
System.out.println(stackExample.pop());

Produktion:

10
5

Er tom

Lad os nu sige, at du vil fjerne alle elementerne fra en stak , men du er ikke sikker på, hvor mange elementer der er. Du kan kombinere Boolean.isEmpty() -funktionen med en forudsætning, mens loop for at pop alle elementerne fra stakken . Se på, hvordan denne java-stack-implementering udføres.

while(!stackExample.isEmpty()) {      
  System.out.println(stackExample.pop());
}

Produktion

10
5

Kig

Vi kan bruge .peek() som stakimplementering i Java for at se på det næste element på stakken uden at fjerne det.

System.out.println(stackExample.peek());

Produktion

10

Hvis vi springer og udskriver stakken , vil den returnere 10 og 5, fordi 10'eren stadig er på stakken. Vi kiggede lige på det, vi fjernede det ikke med pop-funktionen. Peek-funktionen er et fantastisk værktøj til Stack s i java.

Søg

Hvis vi ønsker at finde et specifikt element, bruger stakimplementeringen i Java .search(e); at finde den.

System.out.println(stackExample.search(5));

Produktion

2

Husk, at dette er fordi vi tæller fra toppen af ​​stakken , og Java -stakken starter ved 1, ikke 0 som et array . Så ser man på stakken, er den (10) --> (5), og 5 er på nummer 2-pladsen. Hvis du forsøger at finde et element, der ikke er i stakken , får du en -1 som output.

Iteration

Når du arbejder med enhver samling, kan der være tidspunkter, hvor du skal lede efter flere elementer. For at spare kompleksitet og at skulle søge gennem stakken flere gange, kan du bruge iteration. Fordi Stack in Java udvider List- klassen, er der flere muligheder for iteration. En af de nemmeste er bare at bruge ListIterator- funktionen. ListIterator er rart, fordi den lader dig krydse en stak fra top til bund eller fra bund til top ved hjælp af .hasPrevious() eller .hasNext() . Sådan ser det ud:

ListIterator<Integer> exampleIterator = stackExample.listIterator(stackExample.size());

  while (exampleIterator.hasPrevious()) {
    int iteration = exampleIterator.previous();
    System.out.println(iteration);
  }

Produktion

10
5

Husk, at når du itererer gennem Stack s i Java, fjerner du ikke nogen elementer i den. Iteration giver dig i det væsentlige mulighed for at kigge på hvert element i stakken i rækkefølge. Når du gør dette, kan du lede efter steder, hvor visse elementer er, og derefter gå igennem og manipulere dem. Du kan tælle, slette eller endda ændre dem, hvis det er nødvendigt.