Snabbguide till Java Stack

1. Översikt

I den här snabba artikeln introducerar vi klassen java.util.Stack och börjar titta på hur vi kan använda den.

Stack är en generisk datastruktur som representerar en LIFO-samling (sista in, först ut) av objekt som möjliggör push / popping-element i konstant tid.

För de nya implementeringarna bör vi föredra ett Deque- gränssnitt och dess implementeringar . Deque definierar en mer komplett och konsekvent uppsättning LIFO-operationer. Vi kan dock fortfarande behöva hantera Stack- klassen, särskilt i äldre kod, är det viktigt att veta det bättre.

2. Skapa en stack

Låt oss börja med att skapa en tom instans av Stack genom att använda standardkonstruktören utan argument:

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

Detta skapar en stack med standardkapaciteten 10. Om antalet tillagda element överstiger den totala stackstorleken fördubblas den automatiskt. Men dess storlek kommer aldrig att krympa efter att element har tagits bort.

3. Synkronisering för Stack

Stack är en direkt underklass av Vector ; detta betyder att det på samma sätt som sin superklass är en synkroniserad implementering.

Synkronisering behövs dock inte alltid, i sådana fall rekommenderas det att du använder ArrayDeque .

4. Lägg i en stack

Låt oss börja med att lägga till ett element högst upp i stacken , med push () -metoden - som också returnerar det element som har lagts till:

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

Att använda push () -metoden har samma effekt som att använda addElement (). Den enda skillnaden är att addElement () returnerar resultatet av operationen istället för det element som lades till.

Vi kan också lägga till flera element samtidigt:

@Test public void whenMultipleElementsArePushed_thenStackSizeIsIncreased() { Stack intStack = new Stack(); List intList = Arrays.asList(1, 2, 3, 4, 5, 6, 7); boolean result = intStack.addAll(intList); assertTrue(result); assertEquals(7, intList.size()); }

5. Hämta från en stack

Låt oss sedan ta en titt på hur man tar bort och tar bort det sista elementet i en stack :

@Test public void whenElementIsPoppedFromStack_thenElementIsRemovedAndSizeChanges() { Stack intStack = new Stack(); intStack.push(5); Integer element = intStack.pop(); assertEquals(Integer.valueOf(5), element); assertTrue(intStack.isEmpty()); }

Vi kan också få det sista elementet i S tack utan att ta bort det:

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

6. Sök efter ett element i en stack

6.1. Sök

Stack låter oss söka efter ett elementoch få sitt avstånd från toppen:

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

Resultatet är ett index för ett visst objekt. Om mer än ett element finns, indexet för detnärmast toppen returneras . Föremålet som finns på toppen av stacken anses vara i läge 1.

Om objektet inte hittas kommer sökning () att returnera -1.

6.2. Få index över element

För att få ett index över ett element på S tack kan vi också använda indexOf () och lastIndexOf () :

@Test public void whenElementIsOnStack_thenIndexOfReturnsItsIndex() { Stack intStack = new Stack(); intStack.push(5); int indexOf = intStack.indexOf(5); assertEquals(0, indexOf); }

Den lastIndexOf () kommer alltid att hitta indexet för det element som är närmast till toppen av stacken . Detta fungerar mycket på samma sätt som sökning () - med den viktiga skillnaden att den returnerar indexet istället för avståndet från toppen:

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

7. Ta bort element från en stapel

Bortsett från pop () -operationen, som används både för att ta bort och hämta element, kan vi också använda flera operationer som ärvs från klassen Vector för att ta bort element.

7.1. Ta bort angivna element

Vi kan använda metoden removeElement () för att ta bort den första förekomsten av det angivna elementet:

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

Vi kan också använda removeElementAt () för att ta bort element under ett angivet index i stacken:

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

7.2. Ta bort flera element

Låt oss ta en snabb titt på hur man tar bort flera element från en stack med hjälp av removeAll () API - vilket tar en samling som ett argument och tar bort alla matchande element från stacken :

@Test public void givenElementsOnStack_whenRemoveAllIsInvoked_thenAllElementsFromCollectionAreRemoved() { Stack intStack = new Stack(); List 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 är också möjligt att ta bort alla element från stacken med hjälp av metoderna clear () eller removeAllElements () ; båda dessa metoder fungerar på samma sätt:

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

7.3. Ta bort element med filter

Vi kan också använda ett villkor för att ta bort element från stacken. Låt oss se hur man gör detta med removeIf () , med ett filteruttryck som argument:

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

8. Iterera över en stack

Stack allows us to use both an Iterator and a ListIterator. The main difference is that the first one allows us to traverse Stack in one direction and second allows us to do this in both directions:

@Test public void whenAnotherStackCreatedWhileTraversingStack_thenStacksAreEqual() { Stack intStack = new Stack(); List intList = Arrays.asList(1, 2, 3, 4, 5, 6, 7); intStack.addAll(intList); ListIterator it = intStack.listIterator(); Stack result = new Stack(); while(it.hasNext()) { result.push(it.next()); } assertThat(result, equalTo(intStack)); }

All Iterators returned by Stack are fail-fast.

9. Stream API for the Java Stack

Stack is a collection, which means we can use it with Java 8 Streams API. Using Stream with the Stack is similar to using it with any other Collection:

@Test public void whenStackIsFiltered_allElementsNotSatisfyingFilterConditionAreDiscarded() { Stack intStack = new Stack(); List inputIntList = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 9, 10); intStack.addAll(inputIntList); List filtered = intStack .stream() .filter(element -> element <= 3) .collect(Collectors.toList()); assertEquals(3, filtered.size()); }

10. Summary

This tutorial is a quick and practical guide to understand this core class in Java – the Stack.

Naturligtvis kan du utforska hela API: et i Javadoc.

Och som alltid kan alla kodprover hittas på GitHub.