Pile Java

Stack en Java signifie généralement la classe de Collection Framework qui implémente l'interface List. Il fonctionne sur le principe de la structure de données Stack, qui sert à organiser l'un des types de mémoire. Cela pourrait également être la partie de la mémoire pour conserver les données. Dans cet article, nous nous intéresserons tout d'abord à la classe Stack , examinerons ses méthodes et donnerons des exemples. Mais nous parlerons également d'une structure de données telle que Stack et de son utilisation.

Qu'est-ce que la structure de données de pile

Tout d'abord, examinons rapidement ce qu'est une structure de données de pile. Il s'agit d'une structure de données linéaire basée sur le principe du dernier entré, premier sorti (LIFO). C'est une sorte d'anti-file d'attente. Imaginez un jeu de cartes ou une pile de livres dans une boîte. Le livre que vous placez en premier dans la pile est en bas, et le premier que nous sortirons de la boîte est le livre qui était en haut, c'est-à-dire celui qui est entré en dernier dans la boîte. Voici une image gif pour démontrer ce principe. Que se passe t-il ici? Nous avons un ballon dans lequel une seule balle peut frapper à la fois. La première dans le flacon est une boule orange, puis violette et enfin verte (je m'excuse auprès de ceux qui connaissent les noms plus précis de ces couleurs). Cependant pour extraire une boule orange de notre pile de flacons, il faut d'abord extraire la boule arrivée en dernier (la verte), puis celle qui était l'avant-dernière (mais au moment de l'extraction c'est la dernière un). La structure de données de la pile en Java ou ailleurs dans la programmation comporte les deux opérations les plus importantes, push et pop . L'opération push insère un élément dans la pile et l'opération pop supprime un élément du haut de la pile.

A quoi sert la structure de données Stack?

L'une des utilisations les plus importantes de la pile est d'organiser les appels de sous-programmes. Le point d'appel sur la pile stocke l'adresse de retour du sous-programme après sa fin (et éventuellement les paramètres passés). A chaque appel imbriqué (y compris récursif) de sous-programmes, de nouvelles adresses de retour sont ajoutées à la pile. A chaque opération de retour du sous-programme (retour), l'adresse de retour est retirée de la pile et le contrôle lui est transféré. Cette application est si importante pour la programmation que dans la plupart des processeurs, la pile de retour est implémentée dans le matériel du jeu d'instructions. Cependant, dans d'autres cas, la pile doit être modélisée sur des structures de données plus générales.

Java Stack Classe de Collection Framework

Dans Java Stack Class est une classe du framework Collection qui implémente l'interface List et étend la classe Vector. Il implémente également les interfaces Collection, Iterable, Cloneable, Serializable. Comme vous l'avez probablement déjà deviné, cette classe représente la pile d'objets LIFO. Voici l'appel au constructeur de la classe Stack , c'est-à-dire la création d'un objet de cette classe.

Stack<E> stack = new Stack<E>();

Où E est le type d'objet.

Méthodes de pile Java

Cette classe n'a qu'un seul constructeur par défaut et toutes les méthodes de la classe Vector . De plus, Stack a ses propres 5 méthodes :

• boolean empty() la méthode vérifie si la pile est vide ou non. Renvoie vrai si la pile est vide, faux sinon.

• Object peek() la méthode renvoie l'élément qui se trouve en haut de la pile.

• Object pop() la méthode renvoie l'élément qui se trouve en haut de la pile et le supprime.

• Object push(Object element) la méthode ajoute l'élément spécifié en haut de la pile.

• int search(Object element) la méthode recherche dans la pile l'élément spécifié. Si l'élément recherché est trouvé, sa « distance » par rapport au sommet (numéro de série) est renvoyée. Si l'élément n'est pas trouvé, -1 est retourné.

Exemple de code de pile

Créons un exemple de programme qui fonctionne comme l'image gif ci-dessus. Nous allons mettre trois "boules", orange, violette et verte, sur la pile. Vérifions que la pile n'est pas vide. Ensuite, nous allons extraire des boules de la pile jusqu'à ce que la pile soit vide.

import java.util.Stack;

public class myStackTest2 {

       public static void main(String[] args)
       {

           Stack myStack= new Stack<>();

           System.out.println("Is my stack empty? " + myStack.empty());
// pushing elements into stack
           myStack.push("Orange Ball");
           myStack.push("Violet Ball");
           myStack.push("Green Ball");

//prints elements of the stack
           System.out.println("Elements in Stack: " + myStack);
           System.out.println("Is my stack empty? " + myStack.empty());
           while (!myStack.isEmpty()) {
               myStack.pop();
               System.out.println("Elements in Stack: " + myStack);
               System.out.println("Is my stack empty? " + myStack.empty());
           }
       }
   }

Voici la sortie de ce programme: Étant donné que Stack est hérité de Vector Class et implémente l' interface List , Stack , en plus des opérations push et pop classiques pour cette structure de données pour l'ajout et l'extraction d'éléments, a également une norme pour les opérations add() et remove() de la structure de liste. Dans notre exemple, l'ajout d'éléments peut être implémenté de la même manière en utilisant la méthode add() . Cependant, vous pouvez extraire en utilisant remove() uniquement avec un élément spécifié, ce qui n'a aucun sens pour la structure de données de la pile.

import java.util.Stack;

public class myStackTest2 {

       public static void main(String[] args)
       {

           Stack myStack= new Stack<>();

           System.out.println("Is my stack empty? " + myStack.empty());
// pushing elements into stack
           myStack.add("Orange Ball");
           myStack.add("Violet Ball");
           myStack.add("Green Ball");

//prints elements of the stack
           System.out.println("Elements in Stack: " + myStack);
           System.out.println("Is my stack empty? " + myStack.empty());
           while (!myStack.isEmpty()) {
               myStack.pop();
               System.out.println("Elements in Stack: " + myStack);
               System.out.println("Is my stack empty? " + myStack.empty());
           }
       }
   }

Le résultat du travail du programme, bien sûr, sera exactement le même.

Qu'en est-il de votre propre implémentation Stack ?

Vous pouvez créer votre propre structure de données de pile en Java à l'aide de tableaux ou de classes de listes chaînées. Dans le premier cas, un tableau continu de cellules est alloué pour stocker des valeurs en mémoire, qui sont utilisées au besoin. Dans le second, pour chaque élément de la pile, un bloc de mémoire est ordonné, suffisant pour stocker la valeur et les références aux éléments précédents et suivants de la pile. L'implémentation basée sur la baie est plus simple, plus efficace et plus économe en mémoire, mais elle nécessite une connaissance préalable de la taille limite de la pile et peut entraîner des bogues difficiles à trouver. L'implémentation basée sur des listes est plus robuste mais moins efficace. Faisons une implémentation simple basée sur un tableau de la pile. Il comprendra des fonctions.

• push — une méthode qui assurera l'ajout d'un élément (en position haute)

• pop - une méthode qui fournira la suppression d'un élément (de la position supérieure)

• readTop - une méthode qui renverra la valeur de l'élément qui est en position supérieure

• sEmpty — une méthode qui vérifiera si la pile est vide

• isFull — une méthode qui vérifiera si notre tableau dans lequel nous stockons la pile n'est pas plein

import java.util.Arrays;

public class MyStack {

   private int maxSize;
   private String[] stackArray;
   private int top;

   public MyStack(int size) {
       this.maxSize = size;
       stackArray = new String[maxSize];
       top = -1;
   }

   public String push (String element) {
       return stackArray[++top] = element;

   }

   public String pop (String element) {

       if (isEmpty())
       {
           System.out.println("Underflow\nProgram Terminated");
           System.exit(-1);
       }

       System.out.println("Removing " + readTop());

       return stackArray[top--];

   }

   public String readTop() {
       return stackArray[top];

   }

   public boolean isEmpty() {
       return (top ==  -1);
   }

   public boolean isFull() {
       return (top == maxSize - 1);
   }

   public void printStack(){
       System.out.println(Arrays.toString(stackArray));
   }
}

Implémentons maintenant un exemple avec trois balles basées sur notre pile:

public class myStackTest {
   public static void main(String[] args) {
       MyStack  myStack = new MyStack(3);
       System.out.println("Is my stack empty? " + myStack.isEmpty());

       myStack.push("Orange Ball");
       myStack.push("Violet Ball");
       myStack.push("Green Ball");

      myStack.printStack();

       System.out.println("Is my stack empty? " + myStack.isEmpty());
       while (!myStack.isEmpty()) {
           myStack.pop(myStack.readTop());
           System.out.println("Is my stack empty? " + myStack.isEmpty());
       }
   }

}

La sortie est ici: Si vous regardez attentivement, la variable top contient en fait l'index du dernier élément, et la référence à l'objet reste dans le tableau. Cette implémentation nécessite donc quelques améliorations. Réfléchissez à la manière la plus simple de procéder.

Doit-on utiliser Java Stack ?

En fait, Java Stack , comme son parent Vector , est une classe héritée. Au lieu de cela, la classe ArrayList est généralement utilisée. ArrayList n'est pas synchronisé alors que Vector est synchronisé. Cela signifie qu'avec Vector, un seul thread à la fois peut accéder au code, tandis qu'ArrayList peut fonctionner avec plusieurs threads. De plus, ArrayList est plus efficace et plus rapide. Vous ne verrez donc probablement cette classe que dans le code hérité. Mais la structure de données Stack est très souvent utilisée en programmation.