Hurtig guide til Java-stakken

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.

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

For de nye implementeringer bør vi favorisere Deque  grænseflade og dens implementeringer . Deque definerer et mere komplet og ensartet sæt LIFO-operationer. Vi skal dog muligvis stadig håndtere stakken klasse, især i ældre kode, så det er vigtigt at forstå det godt.

2. Opret en stak

Lad os starte med at oprette en tom forekomst af Stack , ved at bruge standard, no-argument constructor:

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

Dette vil oprette en stak med standardkapaciteten på 10. Hvis antallet af tilføjede elementer overstiger den samlede Stack størrelse, fordobles den automatisk. Dens størrelse vil dog aldrig krympe efter fjernelse af elementer.

3. Synkronisering for stak

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

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

4. Tilføj til en stak

Lad os starte med at tilføje et element til toppen af ​​stakken , med push() metode – som også returnerer det element, der blev tilføjet:

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

Brug af push() metode har samme effekt som at bruge addElement(). T den eneste forskel er, at 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
public void whenMultipleElementsArePushed_thenStackSizeIsIncreased() {
    Stack<Integer> intStack = new Stack<>();
    List<Integer> intList = Arrays.asList(1, 2, 3, 4, 5, 6, 7);
    
    boolean result = intStack.addAll(intList);
    
    assertTrue(result);
    assertEquals(7, intList.size());
}

5. Hent fra en stak

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

@Test
public void whenElementIsPoppedFromStack_thenElementIsRemovedAndSizeChanges() {
    Stack<Integer> intStack = new Stack<>();
    intStack.push(5);

    Integer element = intStack.pop();
    
    assertEquals(Integer.valueOf(5), element);
    assertTrue(intStack.isEmpty());
}

Vi kan også få det sidste element af Stak uden at fjerne det:

@Test
public void whenElementIsPeeked_thenElementIsNotRemovedAndSizeDoesNotChange() {
    Stack<Integer> 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øg efter et element i en stak

6.1. Søg

Stak giver os mulighed for at søge efter et element og få dens afstand fra toppen:

@Test
public void whenElementIsOnStack_thenSearchReturnsItsDistanceFromTheTop() {
    Stack<Integer> intStack = new Stack<>();
    intStack.push(5);
    intStack.push(8);

    assertEquals(2, intStack.search(5));
}

Resultatet er et indeks for et givet objekt. Hvis mere end ét element er til stede, indekset for det ene tættest på toppen returneres . Elementet, der er på toppen af ​​stakken, anses for at være på position 1.

Hvis objektet ikke findes, søg() vil returnere -1.

6.2. Få indeks over element

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

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

lastIndexOf() vil altid finde indekset for det element, der er tættest på toppen af ​​stakken . Dette fungerer meget på samme måde som search() – med den vigtige forskel, at det returnerer indekset, i stedet for afstanden fra toppen:

@Test
public void whenMultipleElementsAreOnStack_thenIndexOfReturnsLastElementIndex() {
    Stack<Integer> 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 at fjerne og hente elementer, vi kan også bruge flere operationer, der er arvet fra Vektoren 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
public void whenRemoveElementIsInvoked_thenElementIsRemoved() {
    Stack<Integer> 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 stakken:

    @Test
    public void whenRemoveElementAtIsInvoked_thenElementIsRemoved() {
        Stack<Integer> 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 ved hjælp af removeAll() API – som vil tage en samling som et argument og fjern alle matchende elementer fra stakken :

@Test
public void givenElementsOnStack_whenRemoveAllIsInvoked_thenAllElementsFromCollectionAreRemoved() {
    Stack<Integer> intStack = new Stack<>();
    List<Integer> 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 fjerne alle elementer fra stakken ved hjælp af clear() eller removeAllElements() metoder; begge disse metoder fungerer på samme måde:

@Test
public void whenRemoveAllElementsIsInvoked_thenAllElementsAreRemoved() {
    Stack<Integer> 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 til at fjerne elementer fra stakken. Lad os se, hvordan du gør dette ved hjælp af removeIf () , med et filterudtryk som argument:

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

8. Gentag over en stak

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

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

    assertThat(result, equalTo(intStack));
}

Alle Iteratorer returneret af Stack er fejlhurtige.

9. Stream API til Java-stakken

Stak er en samling, hvilket betyder, at vi kan bruge den med Java 8 Streams API. Brug af Stream med stakken svarer til at bruge det med enhver anden Samling:

@Test
public void whenStackIsFiltered_allElementsNotSatisfyingFilterConditionAreDiscarded() {
    Stack<Integer> intStack = new Stack<>();
    List<Integer> inputIntList = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 9, 10);
    intStack.addAll(inputIntList);

    List<Integer> filtered = intStack
      .stream()
      .filter(element -> element <= 3)
      .collect(Collectors.toList());

    assertEquals(3, filtered.size());
}

10. Resumé

Denne vejledning er en hurtig og praktisk guide til at forstå denne kerneklasse i Java – stakken .

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

Og som altid kan alle kodeeksempler findes på GitHub.