Hurtig vejledning til Java Stack

1. Oversigt

I denne hurtige artikel introducerer vi java.util.Stack klasse og begynde at se på, hvordan vi kan gøre brug af det.

Stak er en generisk datastruktur, der repræsenterer en LIFO (sidste ind, først ud) samling af objekter, der giver mulighed for at skubbe / poppe elementer i konstant tid.

Til de nye implementeringer vi foretrækker en Deque interface og dets implementeringer. Deque definerer et mere komplet og konsistent sæt LIFO-operationer. Vi kan dog stadig have brug for at håndtere Stak klasse, især i ældre kode, er det vigtigt at kende det bedre.

2. Opret en stak

Lad os starte med at oprette en tom forekomst af Stakved hjælp af standardkonstruktøren uden argument:

@Test offentlig ugyldig nårStackIsCreated_thenItHasSizeZero () {Stack intStack = ny stak (); assertEquals (0, intStack.size ()); }

Dette vil lave en Stak med standardkapaciteten 10. Hvis antallet af tilføjede elementer overstiger det samlede antal Stak størrelse fordobles den automatisk. Imidlertid krymper dens størrelse aldrig efter fjernelse af elementer.

3. Synkronisering til stak

Stak er en direkte underklasse af Vektor; Det betyder at på samme måde som sin superklasse er det en synkroniseret implementering.

Imidlertid er synkronisering ikke altid nødvendig, i sådanne tilfælde tilrådes det at bruge ArrayDeque.

4. Tilføj i en stak

Lad os starte med at tilføje et element øverst på Stak, med skubbe() metode - som også returnerer det element, der blev tilføjet:

@Test offentlig ugyldig nårElementIsPushed_thenStackSizeIsIncreased () {Stack intStack = ny stak (); intStack.push (1); assertEquals (1, intStack.size ()); }

Ved brug af skubbe() metoden har samme virkning som at bruge addElement (). Than eneste forskel er det addElement () returnerer resultatet af operationen i stedet for det element, der blev tilføjet.

Vi kan også tilføje flere elementer på én gang:

@Test offentlig ugyldig nårMultipleElementsArePushed_thenStackSizeIsIncreased () {Stack intStack = new Stack (); Liste intList = Arrays.asList (1, 2, 3, 4, 5, 6, 7); boolsk resultat = intStack.addAll (intList); assertTrue (resultat); assertEquals (7, intList.size ()); }

5. Hent fra en stak

Lad os derefter se på, hvordan du får og fjerner det sidste element i en Stak:

@Test offentlig ugyldig nårElementIsPoppedFromStack_thenElementIsRemovedAndSizeChanges () {Stack intStack = new Stack (); intStack.push (5); Heltalselement = intStack.pop (); assertEquals (Integer.valueOf (5), element); assertTrue (intStack.isEmpty ()); }

Vi kan også få det sidste element i Stack uden at fjerne det:

@Test offentlig ugyldig nårElementIsPeeked_thenElementIsNotRemovedAndSizeDoesNotChange () {Stack intStack = new Stack (); intStack.push (5); Heltalselement = intStack.peek (); assertEquals (Integer.valueOf (5), element); assertEquals (1, intStack.search (5)); assertEquals (1, intStack.size ()); }

6. Søg efter et element i en stak

6.1. Søg

Stak giver os mulighed for at søge efter et elementog få afstanden fra toppen:

@Test offentlig ugyldig nårElementIsOnStack_thenSearchReturnsItsDistanceFromTheTop () {Stack intStack = new Stack (); intStack.push (5); intStack.push (8); assertEquals (2, intStack.search (5)); }

Resultatet er et indeks over et givet objekt. Hvis der er mere end et element til stede, indekset for den enetættest på toppen returneres. Elementet, der er øverst på stakken, anses for at være i position 1.

Hvis objektet ikke findes, Søg() returnerer -1.

6.2. Få indeks over element

For at få et indeks over et element på Stack, vi kan også bruge indeks af() og lastIndexOf () metoder:

@Test offentligt ugyldigt nårElementIsOnStack_thenIndexOfReturnsItsIndex () {Stack intStack = new Stack (); intStack.push (5); int indexOf = intStack.indexOf (5); assertEquals (0, indexOf); }

DetlastIndexOf () finder altid indekset for det element, der er tættest på toppen af ​​stakken. Dette fungerer meget ens Søg() - med den vigtige forskel, at det returnerer indekset i stedet for afstanden fra toppen:

@Test offentlig ugyldig nårMultipleElementsAreOnStack_thenIndexOfReturnsLastElementIndex () {Stack intStack = new Stack (); intStack.push (5); intStack.push (5); intStack.push (5); int lastIndexOf = intStack.lastIndexOf (5); assertEquals (2, lastIndexOf); }

7. Fjern elementer fra en stak

Bortset fra pop () operation, der bruges både til fjernelse og hentning af elementer, kan vi også bruge flere operationer nedarvet fra Vektor klasse for at fjerne elementer.

7.1. Fjernelse af specificerede elementer

Vi kan bruge removeElement () metode til at fjerne den første forekomst af det givne element:

@Test offentlig ugyldig nårRemoveElementIsInvoked_thenElementIsRemoved () {Stack intStack = new Stack (); intStack.push (5); intStack.push (5); intStack.removeElement (5); assertEquals (1, intStack.size ()); }

Vi kan også bruge removeElementAt () for at slette elementer under et specificeret indeks i Stak:

 @Test offentlig ugyldig nårRemoveElementAtIsInvoked_thenElementIsRemoved () {Stack intStack = new Stack (); intStack.push (5); intStack.push (7); intStack.removeElementAt (1); assertEquals (-1, intStack.search (7)); }

7.2. Fjernelse af flere elementer

Lad os se hurtigt på, hvordan du fjerner flere elementer fra en Stak bruger Fjern alt() API - som vil tage en Kollektion som et argument og fjern alle matchende elementer fra Stak:

@Test offentlig ugyldighed givenElementsOnStack_whenRemoveAllIsInvoked_thenAllElementsFromCollectionAreRemoved () {Stack intStack = new Stack (); Liste intList = Arrays.asList (1, 2, 3, 4, 5, 6, 7); intStack.addAll (intList); intStack.add (500); intStack.removeAll (intList); assertEquals (1, intStack.size ()); assertEquals (1, intStack.search (500)); }

Det er også muligt at Fjern alle elementer fra Stak bruger klar() eller removeAllElements () metoder; begge disse metoder fungerer det samme:

@Test offentlig ugyldig nårRemoveAllElementsIsInvoked_thenAllElementsAreRemoved () {Stack intStack = new Stack (); intStack.push (5); intStack.push (7); intStack.removeAllElements (); assertTrue (intStack.isEmpty ()); }

7.3. Fjernelse af elementer ved hjælp af filter

Vi kan også bruge en betingelse for at fjerne elementer fra Stak. Lad os se, hvordan du gør dette ved hjælp af fjerneHvis(), med et filterudtryk som argument:

@Test offentlig ugyldig nårRemoveIfIsInvoked_thenAllElementsSatysfyingConditionAreRemoved () {Stack intStack = new Stack (); Liste intList = Arrays.asList (1, 2, 3, 4, 5, 6, 7); intStack.addAll (intList); intStack.removeIf (element -> element <6); assertEquals (2, intStack.size ()); }

8. Iterer over en stak

Stak giver os mulighed for at bruge både en Iterator og en ListIterator. Hovedforskellen er, at den første giver os mulighed for at krydse Stak i en retning og anden giver os mulighed for at gøre dette i begge retninger:

@Test offentlig ugyldig nårAnotherStackCreatedWhileTraversingStack_thenStacksAreEqual () {Stack intStack = new Stack (); Liste intList = Arrays.asList (1, 2, 3, 4, 5, 6, 7); intStack.addAll (intList); ListIterator it = intStack.listIterator (); Stakresultat = ny stak (); mens (it.hasNext ()) {result.push (it.next ()); } assertThat (resultat, equalTo (intStack)); }

Alle Iteratorer returneret af Stak er fail-hurtige.

9. Stream API til Java Stack

Stak er en samling, hvilket betyder, at vi kan bruge den med Java 8 Strømme API. Ved brug af Strøm med Stak svarer til at bruge det med andre Kollektion:

@Test offentlig ugyldig nårStackIsFiltered_allElementsNotSatisfyingFilterConditionAreDiscarded () {Stack intStack = new Stack (); Liste inputIntList = Arrays.asList (1, 2, 3, 4, 5, 6, 7, 9, 10); intStack.addAll (inputIntList); Liste filtreret = intStack .stream () .filter (element -> element <= 3) .collect (Collectors.toList ()); assertEquals (3, filtered.size ()); }

10. Resume

Denne tutorial er en hurtig og praktisk guide til at forstå denne kerneklasse i Java - Stak.

Selvfølgelig kan du udforske den fulde API i Javadoc.

Og som altid kan alle kodeeksempler findes på GitHub.