Kurzanleitung zum Java-Stack

1. Übersicht

In diesem kurzen Artikel stellen wir die Klasse java.util.Stack vor und untersuchen, wie wir sie nutzen können.

Stack ist eine generische Datenstruktur, die eine LIFO-Sammlung (last in, first out) von Objekten darstellt, mit der Elemente in konstanter Zeit verschoben / verschoben werden können.

Für die neuen Implementierungen sollten wir eine Deque- Schnittstelle und ihre Implementierungen bevorzugen . Deque definiert einen vollständigeren und konsistenteren Satz von LIFO-Operationen. Möglicherweise müssen wir uns jedoch noch mit der Stack- Klasse befassen , insbesondere mit Legacy-Code. Ist es wichtig, sie besser zu kennen?

2. Erstellen Sie einen Stapel

Beginnen wir mit der Erstellung einer leeren Instanz von Stack unter Verwendung des Standardkonstruktors ohne Argumente:

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

Dadurch wird ein Stapel mit der Standardkapazität von 10 erstellt. Wenn die Anzahl der hinzugefügten Elemente die Gesamtgröße des Stapels überschreitet , wird dieser automatisch verdoppelt. Die Größe wird jedoch nach dem Entfernen von Elementen niemals kleiner.

3. Synchronisation für Stack

Stack ist eine direkte Unterklasse von Vector . Dies bedeutet, dass es sich ähnlich wie bei seiner Oberklasse um eine synchronisierte Implementierung handelt.

Eine Synchronisierung ist jedoch nicht immer erforderlich. In solchen Fällen wird empfohlen, ArrayDeque zu verwenden .

4. In einen Stapel legen

Beginnen wir mit dem Hinzufügen eines Elements am oberen Rand des Stapels mit der push () -Methode, die auch das hinzugefügte Element zurückgibt:

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

Die Verwendung der push () -Methode hat den gleichen Effekt wie die Verwendung von addElement (). Der einzige Unterschied besteht darin, dass addElement () anstelle des hinzugefügten Elements das Ergebnis der Operation zurückgibt.

Wir können auch mehrere Elemente gleichzeitig hinzufügen:

@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. Von einem Stapel abrufen

Als nächstes schauen wir uns an, wie das letzte Element in einem Stapel abgerufen und entfernt wird :

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

Wir können auch das letzte Element der S- Wende erhalten, ohne es zu entfernen:

@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. Suchen Sie nach einem Element in einem Stapel

6.1. Suche

Mit Stack können wir nach einem Element suchenund erhalten Sie seinen Abstand von oben:

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

Das Ergebnis ist ein Index eines bestimmten Objekts. Wenn mehr als ein Element vorhanden ist, der Index des einenam nächsten an der Spitze wird zurückgegeben . Der Gegenstand, der sich oben auf dem Stapel befindet, befindet sich an Position 1.

Wenn das Objekt nicht gefunden wird, gibt search () -1 zurück.

6.2. Index des Elements abrufen

Um einen Index eines Elements auf dem S- Tack zu erhalten, können wir auch die Methoden indexOf () und lastIndexOf () verwenden:

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

Das lastIndexOf () findet immer den Index des Elements, das dem oberen Rand des Stapels am nächsten liegt . Dies funktioniert sehr ähnlich wie search () - mit dem wichtigen Unterschied, dass der Index anstelle des Abstands von oben zurückgegeben wird:

@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. Entfernen Sie die Elemente von einem Stapel

Abgesehen von der pop () -Operation, die sowohl zum Entfernen als auch zum Abrufen von Elementen verwendet wird, können wir auch mehrere Operationen verwenden, die von der Vector- Klasse geerbt wurden , um Elemente zu entfernen.

7.1. Bestimmte Elemente entfernen

Wir können die removeElement () -Methode verwenden, um das erste Vorkommen des angegebenen Elements zu entfernen:

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

Wir können auch removeElementAt () verwenden , um Elemente unter einem angegebenen Index im Stapel zu löschen :

 @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. Mehrere Elemente entfernen

Lassen Sie uns einen kurzen Blick darauf werfen, wie Sie mehrere Elemente mithilfe der removeAll () -API aus einem Stapel entfernen. Dabei wird eine Sammlung als Argument verwendet und alle übereinstimmenden Elemente aus dem Stapel entfernt :

@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)); }

Es ist auch möglich , alle Elemente mit den Methoden clear () oder removeAllElements () aus dem Stapel zu entfernen . Beide Methoden funktionieren gleich:

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

7.3. Elemente mit Filter entfernen

Wir können auch eine Bedingung zum Entfernen von Elementen aus dem Stapel verwenden. Mal sehen, wie das mit removeIf () gemacht wird , mit einem Filterausdruck als 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. Über einen Stapel iterieren

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.

Natürlich können Sie die vollständige API im Javadoc erkunden.

Und wie immer finden Sie alle Codebeispiele auf GitHub.