Beknopte handleiding voor de Java-stack

1. Overzicht

In dit korte artikel introduceren we de java.util.Stack les en ga kijken hoe we er gebruik van kunnen maken.

Stapel is een generieke datastructuur die een LIFO (last in, first out) verzameling objecten vertegenwoordigt die het mogelijk maken om elementen in constante tijd te pushen / popping.

Voor de nieuwe implementaties, we zouden de voorkeur moeten geven aan een Deque interface en de implementaties ervan. Deque definieert een meer complete en consistente set van LIFO-bewerkingen. Het is echter mogelijk dat we nog moeten afrekenen met de Stapel class, vooral in legacy-code, is het belangrijk om het beter te kennen.

2. Maak een stapel

Laten we beginnen met het maken van een leeg exemplaar van Stapel, door de standaard constructor zonder argument te gebruiken:

@Test openbare leegte whenStackIsCreated_thenItHasSizeZero () {Stack intStack = new Stack (); assertEquals (0, intStack.size ()); }

Dit zal Maak een Stapel met de standaardcapaciteit van 10. Als het aantal toegevoegde elementen het totaal overschrijdt Stapel grootte, wordt deze automatisch verdubbeld. Het formaat zal echter nooit krimpen na het verwijderen van elementen.

3. Synchronisatie voor Stack

Stapel is een directe subklasse van Vector; Dit betekent dat net als zijn superklasse is het een gesynchroniseerd implementatie.

Synchronisatie is echter niet altijd nodig, in dergelijke gevallen wordt aangeraden om ArrayDeque.

4. Voeg toe aan een stapel

Laten we beginnen met het toevoegen van een element bovenaan het Stapel, met de Duwen() methode - die ook het element retourneert dat is toegevoegd:

@Test openbare leegte whenElementIsPushed_thenStackSizeIsIncreased () {Stack intStack = new Stack (); intStack.push (1); assertEquals (1, intStack.size ()); }

Gebruik makend van Duwen() methode heeft hetzelfde effect als gebruiken addElement (). Thet enige verschil is dat addElement () geeft het resultaat van de bewerking terug, in plaats van het element dat is toegevoegd.

We kunnen ook meerdere elementen tegelijk toevoegen:

@Test openbare leegte whenMultipleElementsArePushed_thenStackSizeIsIncreased () {Stack intStack = new Stack (); Lijst intList = Arrays.asList (1, 2, 3, 4, 5, 6, 7); booleaans resultaat = intStack.addAll (intList); assertTrue (resultaat); assertEquals (7, intList.size ()); }

5. Haal uit een stapel

Laten we vervolgens eens kijken hoe we het laatste element in een Stapel:

@Test openbare leegte whenElementIsPoppedFromStack_thenElementIsRemovedAndSizeChanges () {Stack intStack = new Stack (); intStack.push (5); Geheel getal element = intStack.pop (); assertEquals (Integer.valueOf (5), element); assertTrue (intStack.isEmpty ()); }

We kunnen ook het laatste element van de S krijgenoverstag zonder het te verwijderen:

@Test openbare leegte whenElementIsPeeked_thenElementIsNotRemovedAndSizeDoesNotChange () {Stack intStack = new Stack (); intStack.push (5); Geheel getal element = intStack.peek (); assertEquals (Integer.valueOf (5), element); assertEquals (1, intStack.search (5)); assertEquals (1, intStack.size ()); }

6. Zoek naar een element in een stapel

6.1. Zoeken

Stapel stelt ons in staat om naar een element te zoekenen zoek de afstand vanaf de top:

@Test openbare leegte whenElementIsOnStack_thenSearchReturnsItsDistanceFromTheTop () {Stack intStack = new Stack (); intStack.push (5); intStack.push (8); assertEquals (2, intStack.search (5)); }

Het resultaat is een index van een bepaald object. Als er meer dan één element aanwezig is, de index van de enehet dichtst bij de bovenkant wordt geretourneerd. Het item dat zich bovenaan de stapel bevindt, wordt geacht zich op positie 1 te bevinden.

Als het object niet wordt gevonden, zoeken() zal -1 teruggeven.

6.2. Index van element ophalen

Om een ‚Äč‚Äčindex van een element op de S te krijgenoverstag, we kunnen ook de index van() en lastIndexOf () methoden:

@Test openbare leegte whenElementIsOnStack_thenIndexOfReturnsItsIndex () {Stack intStack = nieuwe Stack (); intStack.push (5); int indexOf = intStack.indexOf (5); assertEquals (0, indexOf); }

DelastIndexOf () vindt altijd de index van het element dat zich het dichtst bij de bovenkant van de stapel bevindt. Dit werkt op dezelfde manier als zoeken() - met het belangrijke verschil dat het de index retourneert in plaats van de afstand vanaf de bovenkant:

@Test openbare leegte whenMultipleElementsAreOnStack_thenIndexOfReturnsLastElementIndex () {Stack intStack = new Stack (); intStack.push (5); intStack.push (5); intStack.push (5); int lastIndexOf = intStack.lastIndexOf (5); assertEquals (2, lastIndexOf); }

7. Elementen uit een stapel verwijderen

Los van de knal() bewerking, die zowel wordt gebruikt voor het verwijderen als voor het ophalen van elementen, we kunnen ook meerdere bewerkingen gebruiken die zijn overgenomen van de Vector class om elementen te verwijderen.

7.1. Opgegeven elementen verwijderen

We kunnen de removeElement () methode om het eerste exemplaar van het gegeven element te verwijderen:

@Test openbare leegte whenRemoveElementIsInvoked_thenElementIsRemoved () {Stack intStack = new Stack (); intStack.push (5); intStack.push (5); intStack.removeElement (5); assertEquals (1, intStack.size ()); }

We kunnen ook de removeElementAt () om elementen onder een opgegeven index in het Stapel:

 @Test openbare leegte whenRemoveElementAtIsInvoked_thenElementIsRemoved () {Stack intStack = new Stack (); intStack.push (5); intStack.push (7); intStack.removeElementAt (1); assertEquals (-1, intStack.search (7)); }

7.2. Meerdere elementen verwijderen

Laten we snel kijken hoe u meerdere elementen uit een Stapel de ... gebruiken Verwijder alles() API - waarvoor een Verzameling als argument en verwijder alle overeenkomende elementen uit de Stapel:

@Test openbare leegte gegevenElementsOnStack_whenRemoveAllIsInvoked_thenAllElementsFromCollectionAreRemoved () {Stack intStack = nieuwe Stack (); Lijst 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)); }

Het is ook mogelijk om verwijder alle elementen uit de Stapel de ... gebruiken Doorzichtig() of removeAllElements () methoden; beide methoden werken hetzelfde:

@Test openbare leegte whenRemoveAllElementsIsInvoked_thenAllElementsAreRemoved () {Stack intStack = new Stack (); intStack.push (5); intStack.push (7); intStack.removeAllElements (); assertTrue (intStack.isEmpty ()); }

7.3. Elementen verwijderen met filter

We kunnen ook een voorwaarde gebruiken om elementen uit het Stapel. Laten we eens kijken hoe we dit kunnen doen met de removeIf(), met een filteruitdrukking als argument:

@Test openbare leegte whenRemoveIfIsInvoked_thenAllElementsSatysfyingConditionAreRemoved () {Stack intStack = new Stack (); Lijst intList = Arrays.asList (1, 2, 3, 4, 5, 6, 7); intStack.addAll (intList); intStack.removeIf (element -> element <6); assertEquals (2, intStack.size ()); }

8. Itereer over een stapel

Stapel stelt ons in staat om zowel een Iterator en een ListIterator. Het belangrijkste verschil is dat we met de eerste kunnen doorkruisen Stapel in één richting en in de tweede richting kunnen we dit in beide richtingen doen:

@Test openbare leegte whenAnotherStackCreatedWhileTraversingStack_thenStacksAreEqual () {Stack intStack = nieuwe Stack (); Lijst intList = Arrays.asList (1, 2, 3, 4, 5, 6, 7); intStack.addAll (intList); ListIterator het = intStack.listIterator (); Stack resultaat = nieuwe Stack (); while (it.hasNext ()) {resultaat.push (it.next ()); } assertThat (resultaat, gelijk aan (intStack)); }

Alle Iteratoren geretourneerd door Stapel zijn fail-fast.

9. Stream API voor de Java Stack

Stapel is een verzameling, wat betekent dat we deze kunnen gebruiken met Java 8 Streams API. Gebruik makend van Stroom met de Stapel is vergelijkbaar met het gebruik met andere Verzameling:

@Test openbare leegte whenStackIsFiltered_allElementsNotSatisfyingFilterConditionAreDiscarded () {Stack intStack = nieuwe Stack (); Lijst inputIntList = Arrays.asList (1, 2, 3, 4, 5, 6, 7, 9, 10); intStack.addAll (inputIntList); Lijst gefilterd = intStack .stream () .filter (element -> element <= 3) .collect (Collectors.toList ()); assertEquals (3, gefilterde.size ()); }

10. Samenvatting

Deze tutorial is een snelle en praktische gids om deze kernklasse in Java - het Stapel.

Natuurlijk kunt u de volledige API verkennen in de Javadoc.

En, zoals altijd, zijn alle codevoorbeelden te vinden op GitHub.