Guide rapide de la pile Java

1. Vue d'ensemble

Dans cet article rapide, nous présenterons la classe java.util.Stack et commencerons à voir comment nous pouvons l'utiliser.

Stack est une structure de données générique qui représente une collection LIFO (dernier entré, premier sorti) d'objets permettant de pousser / sauter des éléments en temps constant.

Pour les nouvelles implémentations, nous devrions préférer une interface Deque et ses implémentations . Deque définit un ensemble plus complet et cohérent d'opérations LIFO. Cependant, il se peut que nous ayons encore besoin de gérer la classe Stack , en particulier dans le code hérité, s'il est important de mieux la connaître.

2. Créez une pile

Commençons par créer une instance vide de Stack , en utilisant le constructeur par défaut sans argument:

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

Cela créera une pile avec la capacité par défaut de 10. Si le nombre d'éléments ajoutés dépasse la taille totale de la pile , elle sera automatiquement doublée. Cependant, sa taille ne diminuera jamais après la suppression d'éléments.

3. Synchronisation pour la pile

Stack est une sous-classe directe de Vector ; cela signifie qu'à l' instar de sa superclasse, c'est une implémentation synchronisée .

Cependant, la synchronisation n'est pas toujours nécessaire, dans de tels cas, il est conseillé d'utiliser ArrayDeque .

4. Ajouter dans une pile

Commençons par ajouter un élément en haut de la pile , avec la méthode push () - qui retourne également l'élément qui a été ajouté:

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

L'utilisation de la méthode push () a le même effet que l'utilisation de addElement (). La seule différence est que addElement () renvoie le résultat de l'opération, au lieu de l'élément qui a été ajouté.

Nous pouvons également ajouter plusieurs éléments à la fois:

@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. Récupérer à partir d'une pile

Ensuite, voyons comment obtenir et supprimer le dernier élément d'une pile :

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

Nous pouvons également obtenir le dernier élément de l' amure S sans le retirer:

@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. Rechercher un élément dans une pile

6.1. Chercher

Stack nous permet de rechercher un élémentet obtenez sa distance du haut:

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

Le résultat est un index d'un objet donné. Si plusieurs éléments sont présents, l'index de celuile plus proche du sommet est renvoyé . L'élément qui se trouve en haut de la pile est considéré comme étant à la position 1.

Si l'objet n'est pas trouvé, search () retournera -1.

6.2. Obtenir l'index de l'élément

Pour obtenir un index d'un élément sur le point S , nous pouvons également utiliser les méthodes indexOf () et lastIndexOf () :

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

Le lastIndexOf () trouvera toujours l'index de l'élément le plus proche du haut de la pile . Cela fonctionne de manière très similaire à search () - avec la différence importante qu'il renvoie l'index, au lieu de la distance par rapport au sommet:

@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. Supprimer des éléments d'une pile

Outre l' opération pop () , utilisée à la fois pour supprimer et récupérer des éléments, nous pouvons également utiliser plusieurs opérations héritées de la classe Vector pour supprimer des éléments.

7.1. Suppression d'éléments spécifiés

Nous pouvons utiliser la méthode removeElement () pour supprimer la première occurrence de l'élément donné:

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

Nous pouvons également utiliser le removeElementAt () pour supprimer des éléments sous un index spécifié dans la pile:

 @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. Suppression de plusieurs éléments

Voyons rapidement comment supprimer plusieurs éléments d'une pile à l'aide de l' API removeAll () - qui prendra une collection comme argument et supprimera tous les éléments correspondants de la pile :

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

Il est également possible de supprimer tous les éléments de la pile en utilisant les méthodes clear () ou removeAllElements () ; ces deux méthodes fonctionnent de la même manière:

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

7.3. Suppression d'éléments à l'aide d'un filtre

Nous pouvons également utiliser une condition pour supprimer des éléments de la pile. Voyons comment faire cela en utilisant la méthode removeIf () , avec une expression de filtre comme 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. Itérer sur une pile

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.

Bien sûr, vous pouvez explorer l'API complète dans Javadoc.

Et, comme toujours, tous les exemples de code peuvent être trouvés sur GitHub.