Définition d'une pile de caractères en Java

1. Vue d'ensemble

Dans ce tutoriel, nous allons discuter comment créer un omble pile en Java. Nous verrons d'abord comment nous pouvons le faire en utilisant l'API Java, puis nous examinerons quelques implémentations personnalisées.

Stack est une structure de données qui suit le principe LIFO (Last In First Out). Certaines de ses méthodes courantes sont:

  • push (élément E) - pousse un élément vers le haut de la pile
  • pop () - supprime et renvoie l'objet en haut de la pile
  • peek () - renvoie l'objet en haut de la pile sans le retirer

2. Char Stack Utilisation de l' API Java

Java possède une API intégrée nommée java.util.Stack . Puisque char est un type de données primitif , qui ne peut pas être utilisé dans les génériques, nous devons utiliser la classe wrapper de java.lang.Character pour créer une pile :

Stack charStack = new Stack();

Maintenant, nous pouvons utiliser les méthodes push , pop et peek avec notre Stack .

D'un autre côté, on peut nous demander de construire une implémentation personnalisée d'une pile. Par conséquent, nous examinerons quelques approches différentes.

3. Implémentation personnalisée à l'aide de LinkedList

Implémentons un omble pile à l' aide d' une LinkedList que notre structure de données back-end:

public class CharStack { private LinkedList items; public CharStack() { this.items = new LinkedList(); } }

Nous avons créé une variable d' éléments qui est initialisée dans le constructeur.

Maintenant, nous devons fournir une implémentation des méthodes push , peek et pop :

public void push(Character item) { items.push(item); } public Character peek() { return items.getFirst(); } public Character pop() { Iterator iter = items.iterator(); Character item = iter.next(); if (item != null) { iter.remove(); return item; } return null; }

Les méthodes push et peek utilisent les méthodes intégrées d'un LinkedList . Pour la pop , nous avons d'abord utilisé un itérateur pour vérifier s'il y a un élément en haut ou non. S'il est là, nous supprimons l'élément de la liste en appelant la méthode remove .

4. Implémentation personnalisée à l'aide d'une baie

Nous pouvons également utiliser un tableau pour notre structure de données:

public class CharStackWithArray { private char[] elements; private int size; public CharStackWithArray() { size = 0; elements = new char[4]; } }

Ci-dessus, nous créons un tableau char , que nous initialisons dans le constructeur avec une capacité initiale de 4. De plus, nous avons une variable de taille pour garder une trace du nombre d'enregistrements présents dans notre pile.

Maintenant, implémentons la méthode push :

public void push(char item) { ensureCapacity(size + 1); elements[size] = item; size++; } private void ensureCapacity(int newSize) { char newBiggerArray[]; if (elements.length < newSize) { newBiggerArray = new char[elements.length * 2]; System.arraycopy(elements, 0, newBiggerArray, 0, size); elements = newBiggerArray; } }

En poussant un élément vers la pile, nous devons d'abord vérifier si notre baie a la capacité de le stocker. Sinon, nous créons un nouveau tableau et doublons sa taille. Nous copions ensuite les anciens éléments dans le tableau nouvellement créé et l'affectons à notre variable elements .

Remarque: pour une explication des raisons pour lesquelles nous voulons doubler la taille du tableau, plutôt que simplement augmenter la taille d'un, veuillez vous référer à cet article de StackOverflow.

Enfin, implémentons les méthodes peek et pop :

public char peek() { if (size == 0) { throw new EmptyStackException(); } return elements[size - 1]; } public char pop() { if (size == 0) { throw new EmptyStackException(); } return elements[--size]; }

Pour les deux méthodes, après avoir validé que la pile n'est pas vide, on retourne l'élément à la position size - 1. Pour pop , en plus de renvoyer l'élément, on décrémente la taille de 1.

5. Conclusion

Dans cet article, nous avons appris comment faire un omble pile en utilisant l'API Java, et nous avons vu un couple de mise en œuvre personnalisée.

Le code présenté dans cet article est disponible à l'adresse over sur GitHub.