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.
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:
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:
GO TO FULL VERSION